Homework 9 Solution

CS409 - Spring 2000

Due: Thursday, Apr 13

  1. (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=(h1,...,hn).  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.

    No this algorithm does not always find the optimum.  Here's one example: H=(7,6,5,4,3,3) with bins of height 14.  The greedy solution produces {7,6}, {5,4,3}, and {3} using 3 bins.  The optimal solution is {7,4,3} and {6,5,3} taking just 2 bins.

     

  2. (10 pts) In class we used dynamic programming to design an O(n3) 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. 

      Here's one such example: (1x10)(10x1)(1x3).  The most expensive multiplication is the last one, requiring 30 multiplication operations.  If that multiply is done first then the total cost for multiplying all 3 matrices is 30+30 or 60.  But if the first pair of matrices is multiplied first then the total cost is 10+3 = 13.

       

    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.

      Here's one such example: (5x10)(10x5)(5x1).  The largest value is 10 which can be eliminated by the first multiply.  If we do the first multiply first then the total cost is 250+25 = 275.   If we do the second multiply first then the total cost is 50+50 = 100.

     

  3. (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.

    Assign two credits to each push-operation and 2 credits to each pop-operation.   One credit is used to complete the given operation; the other credit is stored with the stack.  After k operations the stack has accumulated k credits.  These k credits can be used to pay for making the backup copy of the stack (note that we need O(k) credits to make a k-size copy).  Thus,  the worst-case time for n operations, equal to the number of credits used, is O(n).

     

  4. (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).

    Use one Stack as the putStack and the other Stack as the getStack.  When we do a put() operation, we actually push() the item onto the putStack. When we do a get() operation, we pop() the getStack, but if the getStack is empty, we first copy the entire contents of the putStack to the getStack using pop() and push(). Note that items are removed from the Queue in the proper order (i.e., the bottom of the putStack becomes the top of the getStack when the items are moved from one stack to the other).

    For the analysis, we charge 2 credit for each put() operation and 1 credit for each pop() operation.  For put(), we pay one credit to push() the item onto the putStack; the other credit is stored with the item on the Stack.  For get(), we use the 1 credit to pop() the getStack; any copying needed is paid for with the credit residing with the items on the putStack.  The amortized time for each operation is clearly O(1).