Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2440 / avalg09 / Homework / Homework A

# Avalg homework A, fall 2009

This homework is due 7/10. It should be done individually and handed in at 13.15 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 model 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. Give a short description of the unit-cost RAM model and explain how the word-size w gives an upper bound on the number of integers n in the sorting problem above. (5p)
2. If the maximum element m is O(n) you may 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(nk), where k is a 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 a formula describing the time-space tradeoff. (5p)