600.226 Assignment 3

Solution is now online.

(Do any 10. Do all 11 to get 5 extra points.)

1. [5] Give the array representation of the tree in Fig 6.6. (old book Fig 5.16b)

2. [5  points] R6.9 (old book R-5.7)

3. [5 points] R6.19 (old book R-5.13)

4. [5 points] C6.3 (old book C-5.7, only preOrderNext,inorderNext,postOrderNext)

5. [5 points] C6.28 (old book: no equivalent)		

Let T be a binary tree with n nodes.  Define the
lowest common ancestor (LCA) between two nodes v and
w as the lowest node in T that has both v and 
w as descendents (where we allow a node to be a descendent of
itself).  Given two nodes v and w, describe an efficient
algorithm for finding the LCA of v and w.  What is the
running time of your method?


6. [5 points] R7.4  (old book: no equivalent)

The implementation of a priority queue using a sequence S that is in turn
implemented as an array only allows constant-time performance for the
removeMin method if S's array is implemented in a circular fashion, s as
to support constant time removal of the first element.  Describe an
alternative approach that involves having the removeMin method always
remove the last element in S, so that it runs in constant time even if S's
array is not circular.

7. [5 points] R7.7  (old book: R-6.2)

8. [5 points] R7.9 (old book: no equivalent)

Illustrate the performance of the heap-sort algorithm on the following
input sequence: (2,5,16,4,10,23,39,18,26,25)

9. [5 points] R7.16 (old book: no equivalent)

A certain Professor Amongus claims that a preorder traversal of a heap
will list out its keys in sorted order. Draw a small example of a heap
that proves him wrong.

10. [5 points] C7.9  (old book: no equivalent)

Show that for any n, there is a sequence of insertions in a heap
that requres Theta(nlog n) time to process


11. [5 points] C7.14 (old book: C-6.4)