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.

**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.

You are required to do at least one more presentation in this course. The
second presentation should be more formal than the first. **It must be about
ten minutes long** (minimum five minutes; maximum fifteen minutes). The presentation
will most likely cover some particular algorithm, but I will consider requests to
present some other topic related to the course, if they are particularly interesting.
For an algorithm, you should discuss the problem that is solved, present the algorithm
and probably some examples of its application, and say whatever you can about its
run-time or space efficiency.

You should be looking for topics and thinking about what you might want to talk about. You can select one of the algorithms from the textbook that we do not cover in class. Perhaps you can find algorithms mentioned in the news -- for example, there are sometimes stories that involve large-scale data processing, cryptography, or web search. Hopefully, we can get started with the new series of presentations next week.