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
2w, 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(nk), 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)