**Problem 1: Sorting in Linear Time **

- Given the sequence
*<*9*,*1*,*6*,*7*,*6*,*2*,*1*>*, sort the sequence by Counting Sort. - Given the sequence
*<*0*.*9*,*0*.*1*,*0*.*6*,*0*.*7*,*0*.*6*,*0*.*2*,*0*.*1*>*, sort the sequence by Bucket Sort. - Given
*n*integers in the range 0 to*k*, design an algorithm (only pseudocode) with pre-processing time (*n*+*k*) that counts in*O*(1) how many of the integers fall into the interval [*a,b*]. - Given a sequence of
*n*English words of length*k*,*implement*an algorithm that sorts them in (*n*). Let*k*and*n*be flexible, i.e., automatically determined when reading the input sequence. - Given any input sequence of length
*n*, determine the worst-case time complexity for Bucket Sort. Explain your answer! - Given
*n*2D points that are uniformly randomly distributed within the unit circle, design an algorithm (only pseudocode) that sorts the points by increasing Euclidean distance to the circles origin.

**Problem 2: Radix Sort **

Consider Holleriths version of the Radix Sort, i.e., a Radix Sort that starts with the most significant bit and propagates iteratively to the least significant bit (instead of vice versa).

*Implement*Holleriths version of the Radix Sort.- Derive the asymptotic time complexity and the asymptotic storage space required for your implementation.
- * Show how to sort
*n*integers in the range 0 to*n*^{3}1 in*O*(*n*)

## Reviews

There are no reviews yet.