Problem Set 6

Part 1

Part 1 is due in one week on 17 October.

Complete the following problems.

1. Do problem 7 on page 515 of Sahni. Note that you are not writing any code for this problem.

2. A weight-balanced leftist tree (WBLT) is defined on page 519 of Sahni. Read this page and answer the following questions about WBLTs.
   • Answer question 24 on page 527 of Sahni. You do not have to write any code for questions 24 c and d. Instead just provide an algorithm (you can use pseudo-Java or pseudo-C++ if you like). Note that you cannot use recursion in method meld.

   • Prove that the complexity of your meld algorithm is O(log mn) where m and n are the number of nodes in the trees being melded.

   • Prove that the complexity of your initialize algorithm is O(n).

Part 2

Part 2 is due on 24 October.

Write the code for the following problem. Turn your solution into the class server in the ps6 folder. You must follow all of the programming guidlines given in the Program Format Guide .

1. A 3-heap is a complete tree whose degree is 3. Write a program that implements a max 3-heap. You must use arrays to implement the heap itself. Hint: consider the relationship between a parent and it's children in the array.

2. The heap must store items of type comparable.

3. You must supply a test file that provides statement coverage. This file should supply the initial values of the max 3-heap and then perform a number of operations on that heap. You may use any type of symbol in the file to indicate the end of the initialization input and the start of the heap operations.

4. You must have a driver program that creates the heap and tests it.

5. On the due date you must hand in a written analysis of your programs running time. You must include an analysis of every operation.

Last Modified: 5 October 2001

THIS PAGE MAINTAINED BY: John Barr, Ithaca College