Problem 1 (5.1 from text)
Draw all possible binary search trees containing the four elements 1, 2, 3, 4.
Problem 2 (5.2 from text)
Insert the integers 7, 2, 9, 0, 5, 6, 8, 1 into a binary search tree by
repeated application of the procedure INSERT of Fig. 5.3.
Problem 3 (5.3 from text)
Show the result of deleting 7, then 2 from the final tree of Exercise 5.2.
Problem 4 (5.4 from text)
When deleting two elements from a binary search tree using the procedure of Fig. 5.5, does the final tree ever depend on the order in which you delete them?
Problem 5
See the programming portion below. Provide your observed behavior of the make_heap() algorithm.
Problem 6
One way to sort numbers is to build a heap and then pop the numbers off the heap. Since each element is the least element left on the heap when you pop it, the stream of numbers popped off must be in sorted order. Analyze the time and space complexity of this method of sorting numbers. (Don't forget to include the time it takes to build the heap!) How does this compare to merge sort (O(n lg n) time and O(n) space)?
Problem 7
Describe an algorithm (pseudo-code and high-level description, not C) that uses first and next, the above structure definition, and the function impressive_A() to fill in the computed value members. Analyze the time and space complexity of your algorithm, including the fact that your algorithm must call impressive_A().
*More details about problem on course website
Problem 8
Design a queue using only two stacks. What is the time complexity for insert? For remove()? What is the space complexity?
Problem 9
Design an algorithm, given the above two lists of blocks, that comes up with a list of blocks on the server for which no block on the client can possibly match. (We are not asking you to describe how rsync actually works, only to describe an algorithm that could work.)
