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