Office Hours: M/W 8:00--9:00AM

Folks:

 I will have my regular office hours from 8:00--9:00AM on M/W. You can either come to my office or meet with me by video skype (subbarao2z is the username) or google mail video chat (subbarao2z2 is the username).   If you cannot  make it for regular office hours, you can meet me by appointment. 

rao

Complexity of Bogosort...

The really inefficient sorting program we discussed in the class--the one where you find all permutations of n numbers and see if any of them are sorted--is also called

"Bogosort" (or monkeysort etc..)   http://en.wikipedia.org/wiki/Bogosort 

As we saw, it does N* N! comparisons.

We saw that the CS folks' nightmare is exponential complexity, and I mentioned that N*N! is basically exponential complexity. 

To see why this is true, you need to remember Stirling's approximation, which says that for large N, N! is approximatly O(sqrt(N))* (N/e)^N  

(where e is the base of natural logarithms).   See http://en.wikipedia.org/wiki/Stirling's_approximation

honors students in ASU101 section..

If you are an honors student (i.e., admitted to Barretts honor college), please let me know.

Rao

[ASU 101] Questions on Complexity...

Consider answering the following questions:

0. Write a brief summary of what you understood from today's class. [Each of you are encouraged to answer this--so I get an idea what is getting through]

1. There was a factual inaccuracy when I discussed Knuth. See if you can find what it is.

2. How long will it take for the world to end if the priests working in the Tower of Hanoi have been working out on the sly and are ready to do this problem round the clock, with 1 sec per move. 

3. For a given problem, your friend wrote an algorithm with 2^n steps (of unit time each). You wrote one with 4000*(n^5) steps  (where n is the problem size). Up to what input size is your friend going to beat you (alternately, beyond what input size are you going to cream your friend?)

4. In problem 3, suppose your friend, with his 2^n algorithm was able to solve instances of size up to n=K (K is some constant) in "reasonable time". His boss feels sorry for him and buys him a machine that is twice as fast. Now, what is the size of the largest instance that your friend can solve in reasonable time?

Rao

Milo, the virtual boy

Found this:

http://www.ted.com/talks/lang/eng/peter_molyneux_demos_milo_the_virtual_boy.html

I was really amazed that the Kinect Camera finally had some thing worth while developed for it.

Well before the last few days I may have known why I was going CSE. Now I have doubts. I have transferred in from Community College. I take the shuttle into ASU each day.
Well it seems I may be living on campus now.
I always thought of CSE as more of they lock you in a room and slip pizza under the door to feed you. Nope four of my classes have group projects worth up to 40% of the grade. Now of course being new to ASU even though somewhere between a freshman and junior I feel out of touch already. Some already know others in the classes and most likely have teams picked out before the classes started.
I guess I had thought or more going information assurance and CSE with some telecom and becoming self employed at the end even if not highly paid. Some nice little niche to get away from the corporate grind. Now I hope to make it through the next weeks. It feels now as if my niche will not fit in. I need to go to the Intel, Microsoft, and Google dream of teamwork.
I know mostly rant on my first post. ;) Maybe things will look better by Friday.
just seems I will have to rethink if what I was looking for actually fits in.

Links from today's class plus *Thinking Cap* Questions (that you should respond to if you can)

The "Harvard Guide to Happiness"   http://www.physics.ohio-state.edu/~wilkins/physics/College-happiness.html

It is equally relevant to any university..

Questions from the class that you can comment on (comment on all or some or none. If you have nothing to say this time, I am sure you will have opportunities later in the semester. I would only be worried if you never had anything to say... The following link from Love and Death has some insightful comments on the quantity vs. quality tradeoff: expounded in the context of a slightly different situation (start at min 3:30)

1. What is i^i  

2. If we have access to a program that tests a sequence of numbers to see if they are sorted or not (and returns yes if they are and no if they aren't), we can use it to *make* a sequence sorted by 

  

   Loop

       Generate each permutation of the sequence

       Test if the sequence is sorted; if it is, exit loop and return the sequence

   end Loop

What do you think of this as a sorting algorithm?

3. What is the "famous" CS theorem that someone claimed to have proved recently and why is that theorem famous to begin with?

regards

Rao

[ASU101] Blog Introductions (Response on blog required)

Folks:

 Each of you should "comment" on the following blog message and write your introductions 

1. Your name

2. Why you chose CS or Computer Systems major

3. What ares of CS/Computer systems seem to be of particular interest to you right now

4. Something interesting about yourself

regards

Rao

ps: This message is going both as an email to you and will be archived on the blog. Your responses have to be entered on the blog. 

Welcome to the ASU 101 Fall 2010 (Rao's section) Blog

Folks:

 This is a generic welcome message. A more emotional, no holds-barred,  full-throated welcome shall be given in class come Friday ;-)

Rao