This homework is due 10/12. It should be done individually and handed in at the beginning of the homework session. You should be prepared to present your homework orally in class. This is part of the examination and you have to attend the homework session to get credit for your homework. Solutions handed in late are not accepted and will not be graded.

In the lectures you've seen how to sort n word-sized integers on a unit-cost RAM in O(n log log n) time. In this homework you will study special cases where it's possible to find easier algorithms or better time bounds.

• 1. If there are many elements - i.e. if n is close to 2^w, where w is the word length - you may sort in linear time using bucket sort. Describe the algorithm and discuss how large n needs to be. (5p)
• 2. If the maximum element m is O(n) you may also sort in linear time using a simple algorithm. Describe how. (5p)
• 3. Give an algorithm that sorts in linear time when the maximum element m is O(n^k), where k is any positive constant. (5p)
• 4. Describe an algorithm that sorts in linear time if there are many repeated elements. How many distinct elements can your algorithm handle and how fast is it? (5p)
• 5. The algorithm discussed in class uses large amounts of memory. How much? By doing the radix sorting phase in more than two steps you may reduce the memory requirements while increasing the running time. Explain how to do this and give formulas describing the time-space tradeoff. (5p)