COS 226 PROBLEM SET 3

1. [Exercise 9.18] The largest element in a heap must appear in position 1, and the second largest element must be in position 2 or position 3. Give the list of positions in a heap of size 15 where the k-th largest element (i) can appear, and (ii) cannot appear, for k = 2, 3, 4.






2. [Exercise 9.22] Using the conventions of Exercise 9.1, give the sequence of heaps produced when the operations P R I O * R * * I * T * Y * * * Q U E * * * U * E are performed on an initially empty heap.






3. [Exercise 9.56] Give the binomial queue that results when the keys E A S Y Q U E S T I O N are inserted into an intially empty binomial queue.






4. [Exercise 10.5] Generate a set of N random decimal numbers (R=10) uniformly distributed between 0 and 1, and compute the number of digit comparisons necessary to sort them, in the sense illustrated in Figure 10.1, for N=1000, 10,000, 100,000, and 1,000,000. Use sort if you wish.






5. [Exercise 10.35] Show the result of using LSD radix sort on the first two characters for the set of keys now is the time for all good people to come to the aid of their party






Due: in precept on February 23 or 24.

Do your work on this page (use the back if you must)