CSE 5311 Fall 1999
- (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
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).
- (4 points.)
Describe the two properties that characterize a good dynamic programming
prpoblem (do not just name the properties).
- Optimal Substructure. An optimal solution to the problem contains
optimal solutions to the subproblems.
- 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).