Introduction to Algorithms October 17, 2005 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik D. Demaine and Charles E. Leiserson Handout 15 Problem Set 4 MIT students: This problem set is due in lecture on Monday, October 24, 2005. The homework lab for this problem set will be held 24 P.M. on Sunday, October 23, 2005. Reading: Chapters 1213, 18 Both exercises and problems should be solved, but only the problems should be turned in. Exercises are intended to help you master the course material. Even though you should not turn in the exercise solutions, you are responsible for material covered in the exercises. Mark the top of each sheet with your name, the course number, the problem number, your recitation section, the date and the names of any students with whom you collaborated. Please staple and turn in your solutions on 3-hole punched paper. You will often be called upon to “give an algorithm” to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of the essay should provide the following: 1. A description of the algorithm in English and, if helpful, pseudo-code. 2. At least one worked example or diagram to show more precisely how your algorithm works. 3. A proof (or indication) of the correctness of the algorithm. 4. An analysis of the running time of the algorithm. Remember, your goal is to communicate. Full credit will be given only to correct solutions which are described clearly. Convoluted and obtuse descriptions will receive low marks. Exercise 4-1. Do Exercise 12.1-5 on page 256 of CLRS. Exercise 4-2. Do Exercise 12.2-4 on page 260 of CLRS. Exercise 4-3. Do Exercise 12.4-3 on page 268 of CLRS. Exercise 4-4. Do Exercise 13.1-6 on page 277 of CLRS. Exercise 4-5. Do Exercise 13.3-1 on page 287 of CLRS. Exercise 4-6. Do Exercise 18.2-6 on page 449 of CLRS. 2 Handout 15: Problem Set 4 Problem 4-1. Treaps If we insert a set of n items into a binary search tree using TREE-INSERT, the resulting tree may be horribly unbalanced. As we saw in class, however, we expect randomly built binary search trees to be balanced. (Precisely, a randomly built binary search tree has expected height O(lg n).) Therefore, if we want to build an expected balanced tree for a fi xed set of items, we could randomly permute the items and then insert them in that order into the tree. What if we do not have all the items at once? If we receive the items one at a time, can we still randomly build a binary search tree out of them? We will examine a data structure that answers this question in the affi rmative. A treap is a binary search tree with a modifi ed way of ordering the nodes. Figure 1 shows an example of a treap. As usual, each item x in the tree has a key keyx. In addition, we assign priorityx, which is a random number chosen independently for each x. We assume that all priorities are distinct and also that all keys are distinct. The nodes of the treap are ordered so that (1) the keys obey the binary-search-tree property and (2) the priorities obey the min-heap order property. In other words, if v is a left child of u, then keyv keyu; and if v is a child of u, then priority(v) priority(u). (This combination of properties is why the tree is called a “treap”: it has features of both a binary search tree and a heap.) G: B: H: E: 7 K: 5 6523 4 73 I: A: 10 Figure 1: A treap. Each node x is labeled with keyx : priorityx. For example, the root has key G and priority 4. It helps to think of treaps in the following way. Suppose that we insert nodes x1,x2,.,xn, each with an associated key, into a treap in arbitrary order. Then the resulting treap is the tree that would have been formed if the nodes had been inserted into a normal binary search tree in the order given by their (randomly chosen) priorities. In other words, priorityxi priorityx, (2) keyy keyx, and (3) for every z such that keyy keyz keyx, we have priorityy 0 such that, for each node of the tree, the size of the smaller child subtree of this node is at least c times the size of the larger child subtree. (d) There is a constant c such that, for each node of the tree, the heights of its children subtrees differ by at most c. (e) The average depth of a node is O(lg n). (Recall that the depth of a node x is the number of edges along the path from the root of the tree to x.)