T÷lvunarfrŠ­i 2

Weekly note 13

This week we will finish up with heaps and then Anna will take over and talk about symbol tables and binary search trees from Chapter 12 of the textbook.

In the sections this week we will go over Programming project 2.

Problem set 10

Solve the following problems and put the solutions into your section teacher's box before noon monday April 18th. They will not accept solutions that arrive later.

  1. [Exam 2004] Below you are given the results of an inorder, a preorder, and a postorder traversal of a 9 node binary tree, where the nodes have the values A thru I. Unfortunately some of the values have been lost in transmission (denoted by ?). Try to construct the binary tree from this incomplete information and describe your reasoning at each step. If the information is not sufficient to construct a unique binary tree, describe the trees that are possible.
          Inorder: IC?HBE?DA
          Preoder: ?C???H?D?
          Postorder: IHGB??DAE

  2. [Makeup exam 2004] One way to choose the partitioning element in Quicksort is to pick it at random. Then we call a random number generator to choose a number k between l and r, and use the item in location a[k] as the partitioning element. The problem is that good random number generators can take a long time. Calculate how often the generator would be called in Quicksort in the worst case. How about the best case?

  3. [Makeup exam 2004] Implement in C++ a new version of the heap function getmax. In this new version the hole that forms in the root is pushed down to the leaves by always moving up the child with the larger value. Then the last item in the heap (i.e. the item in pq[N]) is put into the hole and it moved upwards until the tree is heap ordered again.
    Compare this method with the getmax function on page 386 in the textbook. Which method do you think is faster and why?
    [As this is now a homework problem and you have access to computers, you should measure the time taken by these two different methods by inserting into a heap some large enough number of elements and take them out with the two different getmax's.]

  4. Exercise 9.18 on page 383 in the textbook.

  5. Exercise 9.25 on page 389 in the textbook.

annaing (hja) hi.is / hh (hja) hi.is, April 1th, 2005.