CSE 5311 Fall 1999

Quiz #6

1.

(16 points.) 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 and performing an amortized analysis using the accounting method.

We assign the following amortized costs: Push 4, Pop 0, Multipop 0, Stackcopy 0.

As in the textbook, we use a dollar bill to represent each unit of cost. Every time we do a Push operation, we pay a dollar to perform the actual operation and put one dollar into credit. That leaves us with two dollars, which is placed on that element. When we Pop that element, one of the two dollars is used to pay for the Pop operation and the other dollar is again saved into credit. Credit is used to pay for the Stackcopy operation. Since after every k operations, there are at least k dollars in credit, and the stack size is never more than k, there is enough money in credit to pay for the Stackcopy operations. The cost of n stack operations, including copying the stack, is thus O(n).

2.

(4 points.) Describe the two properties that characterize a good dynamic programming prpoblem (do not just name the properties).

(a)

Optimal Substructure. An optimal solution to the problem contains optimal solutions to the subproblems.

(b)

Overlapping Subproblems. The number of unique subproblems is small enough to make a dynamic programming solution efficient (usually a low-order polynomial number of unique subproblems).