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?