Homework 5

Details

The following problems are from pages 139-144 of ADM.

Problem	Notes
4-12	Prove that your algorithm has the specified complexity.
4-18	You should be able to do this in place (i.e. with a constant amount of extra memory). Prove that your algorithm has the specified complexity.
4-28
4-32	In both cases, specify how many questions are necessary as a function of n. Give the exact number and not just a bound.