Avalg homework C fall 2006
This homework is due 23/11.
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
- 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) -
If the maximum element
*m*is O(*n*) you may also sort in linear time using a simple algorithm. Describe how. (5p) -
Give an algorithm that sorts in linear time when the maximum
element
*m*is O(*n*^{k}), where*k*is any positive constant. (5p) - 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)
- 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)
Stefan Nilsson 2006-11-15 |