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.
- [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
- [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?
- [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.]
- Exercise 9.18 on page 383 in the textbook.
- Exercise 9.25 on page 389 in the textbook.
annaing (hja) hi.is / hh (hja) hi.is, April 1th, 2005.