CS410, Summer 1998
Quiz #11
July 29

Consult no sources.				Name:

1. Give an asymptotic lower bound for the problem of finding the kth
smallest element in a set.  Explain in one sentence why your lower
bound is correct.  Do we know an algorithm that achieves this lower
bound?

2. What is the asymptotic running time of counting sort?

3. Give the radix sort algorithm.


ANSWERS
=======

1. Omega(n).							1.5 points
   Have to look each element once.				1.5 points
   Yes. (quick-select, "median of medians")			1 point

2. O(n+k)							2 points
   n = # of elements						1 points
   k = # of distinct keys


3. for i = least significant part to most significant part	1.5 points
     stable sort all elements on i				1.5 points (stable)