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 wordsized
integers on a unitcost 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.
 Give a short description of the unitcost RAM model and
explain how the wordsize w gives an upper bound
on the number of integers n in the sorting problem above. (5p)
 If the maximum element m is O(n) you may 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 a 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 a formula describing the timespace
tradeoff. (5p)