Due: Monday, June 2
Work the following exercises in the text.
p. 194, 9-1. Be sure to express the time of each algorithm in terms of both n and i. Compare them assuming that i might be as large as n, but might also be substantially smaller than n.
A max-priority-queue is a data structure that holds a collection of values. (A value can occur more than once in the collection.) This data structure supports operations BUILD-PRIORITY-QUEUE that takes a list of values and makes a max-priority-queue holding those values, taking time O(n) if there are n values in the list. It also has an operation EXTRACT-MAX that removes the largest value in the collection and returns that value, taking time O(log(n)) if there are n values in the queue.
p. 964, 33-5. Think of the divide-and-conquer algorithm.