Description
Problem 1: Sorting in Linear Time (3+3+4+6+2+4 = 22 points)
- 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 circle’s origin.
Problem 2: Radix Sort (8+4+2* = 12+2* points))
Consider Hollerith’s 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 Hollerith’s 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 n3− 1 in O(n)
