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.