Homework 9

CS409 - Spring 2000

Due: Thursday, Apr 13

(10 pts) You are given a set of boxes to be packed into bins. All the boxes have the same width and depth (the same as the width and depth of the bins), but they have different heights. The heights are given in a list H=(h₁,...,h_n). The goal is to pack the boxes in bins using as few bins as possible. Consider the following greedy algorithm for this problem:
```
FirstFit (H):
	Sort H from largest to smallest;
	for i = 1 to n do
		Find the first bin that has enough room for H[i];
		Place box i in this bin;
end FirstFit.
```
Does this algorithm always use the minimum number of bins? Either prove the algorithm produces an optimal solution or give an example to show that it does not.
(10 pts) In class we used dynamic programming to design an O(n³) time algorithm for determining the best way to multiply n matrices.
1. A possible greedy strategy for the same problem is to always do the most expensive multiplication first. Give an example to show that this strategy does not necessarily give the optimal multiplication pattern.
2. Another possible greedy strategy is to first do the multiplication that eliminates the largest value. (If we multiply an m-by-n matrix by an n-by-p matrix then the result is an m-by-p matrix and n has been eliminated.) Give an example to show that this strategy also fails to produce the optimal multiplication pattern.
(10 pts) [From CLR] A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations.
(10 pts) Describe how two Stacks (operations = push and pop) can be used to implement a Queue (operations = put and get) in such a way that the amortized time per Queue operation is O(1). Provide a clear explanation of why the amortized time per Queue operation is O(1).