## CS 327, Spring 2013 Homework 7

Homework 7 is due on Friday, March 29. One of the assignments is a programming assignment; however, it will be graded as part of the homework set rather than as a separate programming assignment. Turn in your answers to the written exercises at the beginning of class on Friday, March 29. Turn in the programming exercise to your homework folder in /classes/cs327/homework no later than noon on Saturday, March 30.

## Homework 7

A) Do Exercise 6.4.2, page 233.

B) Do Exercise 6.1.2, page 205. (Note that the term "set" implies that there are no repeated elements in A, and similarly there are no repeated elements in B.)

C) Do Exercise 6.1.5, page 206.

D) Build a 2-3 tree by inserting the following numbers in the order shown, starting with an empty tree. Draw the tree as it appears after each insertion:

```            71  44  35  32  48  57  29  7  92  41
```

E) Programming Exercise: In class, we looked at deleting an item from a heap using the "heapify" operation. We also used heapify to transform an unordered array into a heap. We talked about adding an item to a heap, but did not implement it for the array representation of a heap. For this exercise, you should implement the add operation for a heap, and you should use it to implement an alternative algorithm for Heapsort. Start with a copy of /classes/cs327/Heapsort.java. Add a method

```           private static void heapInsert( double[] A, int size, double newItem )
```

that adds a new item to an existing heap. (Assume that there is room in the array for the new item.) Note that adding an item increases the size of the heap by one. Then, write an alternative Heapsort method that builds the heap by repeatedly performing the heapInsert operation. The book refers to this (p. 230) as "top-down heap construction." (You can do this in-place, in the array.) The second part of the Heapsort method -- repeatedly deleting items from the heap -- remains unchanged.

You might want to compare the performance of the two versions of Heapsort on the same large array. Supposedly, the version that uses heapify should be faster.