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.

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