Homework 0

Assignment Due 11 April 2007

NOTE: Partial credit is easier to give if your answers are verbose. Show lots of math and don't be afraid of using sentences.

1. What are three cases of interest in asymptotic analysis? Which one do we tend to ignore and why? Why do we need the other two?
2. Exercise 2.7 from the book. Only do items 1-4 and just tell me the big-oh. I recommend that you do the analysis for the tougher ones as we did the analysis for selection sort (ie: first time it runs n-1 times, then n-2, etc. So we get 1,2,3...n-1 which becomes the formula n(n+2)/2 ). A handy list of formulas can be found on pages 3 and 4.
3. Exercise 2.8, just give me the big-oh complexity of the three algorithms listed.
4. Exercise 2.25.
5. Devise an algorithm that takes as input a random array of integers ( of size N ) and returns true if there are any duplicate integers in the array. This algorithm must run in O(n log n) time. (Hint: Where else have we seen an algorithm that runs in O(n log n) time. You don't need to turn in code for this one, a description in English would work just fine.