Heap algorithm implementation

CSC320 Final Exam
50 points (10 pts/question, 10 points extra credit)

Open book/notes/library/internet, but work is to be completed independently. Feel free
to e-mail me for clarifications, but remember that I will be out of town 6/14-6/23.

You have two options for turning in your exam:

1. You may give me hardcopy. Hardcopy is due by 6:30pm on the last day of class
(June 25).

2. You may e-mail me an electronic copy. Your work must be formatted as either a
Microsoft Word document (a .DOC file) or a .PDF file. I must receive your e-mail by
1:00pm on June 25. I will acknowledge all the assignments I receive; if you don't get
a response then it is your responsibility to follow up promptly.



Question 1

Consider a ternary tree, in which each node has three children. What are the maximum
and minimum number of nodes in a ternary tree of height h? (Show your reasoning.)


Question 2

Now consider a ternary search tree with the following ordering property: If a node A has
children X, Y, and Z, then
Key[X] < Key[Y] < Key[A] < Key[Z]
(for simplicity, we use < instead of <= ; this means that no tree can have duplicate
values).

Write the pseudocode TREE-SEARCH, TREE-INSERT and TREE-DELETE functions
for a ternary search tree of this type.


Question 3

Write the pseudocode for a recursive function TERNARY-TO-BINARY that will convert
a ternary search tree into a binary search tree.
Question 4

A heap efficiently supports the operations MAKE-HEAP, EXTRACT-MIN, and
INSERT. However the same operations can be implemented, possibly less efficiently,
using other data structures. For example if a simple unsorted array is used then we may
write EXTRACT-MIN as a simple linear search followed by deletion:
EXTRACT-MIN( A )
IF Len[A]<1 THEN RETURN NIL
MINPOS = 1
FOR I = 2 to Len[N]
IF A[I] < A[MINPOS]
MINPOS = I
END IF
NEXT
RESULT = A[MINPOS]
A[MINPOS] = A[Len[A]]
Len[A] = Len[A] ­ 1
RETURN RESULT

Show how to implement the operations MAKE-HEAP, EXTRACT-MIN, and INSERT
using a sorted array. Make each operation as (asymptotically) efficient as possible.


Question 5

Give the asymptotic complexity (using Theta) of the three functions you wrote in
question 4. (Show your reasoning.)


Question 6

In the greedy algorithm for constructing Huffman codes, a priority queue (implemented
using a heap) is used to hold intermediate subtrees of the tree that will eventually be
returned. The heap operations used are just MAKE-HEAP, EXTRACT-MIN and
INSERT. If these operations were implemented using a sorted array, as in the last two
questions, instead of using a heap, what would the asymptotic complexity of the
HUFFMAN algorithm be? (Show your reasoning.)