Midnight, 23 March 2004 for full credit,
Midnight, 25 March 2004 for part (75%) credit
Non-Programming Exercises:
Show that you can create an algorithm for the
Integer Knapsack Optimization Problem (IKO) using an algorithm
for the Integer Knapsack Decision Problem (IKD).
In other words, if we have a "black box" program that will
solve IKD, then we can use it to create a program to solve IKO.
(Also, if we have an efficient algorithm for IKD, we can use
it to obtain an efficient algorithm for IKO.)
Modify and extend the specific algorithm for IKD
presented in the lectures and in class, so that this
algorithm will yield the specific knapsack solution
obtained during the progress of the algorithm.
This must be a completely different approach from the
previous problem.
[Hint: there are several ways to do this.
If you want to, you can save extra information in the main table,
although you can also solve this just from the main table
itself.]
Work Problem 1 on page 294 of the text.
This is simply to finish the calculations to fill in the
entries in the tables of Example 1, which finds the optimal
binary search tree in a simple case.
Work Problem 5 on page 294 of the text.
Explain what the book means in the hint to this
exercise on page 466. (What would the "simple algorithm"
for constructing an optimal binary search tree be?
Does the optimal tree in Example 1 obey this simpler
algorithm? (Not just yes or no, but explain.)
Show that the result of this "simple algorithm" is obtained by
inserting the keys into a binary search tree in
decreasing order of frequency.