University of Illinois, Urbana Champaign - CS 473hw5sol University of Illinois, Urbana Champaign - CS 473hw5sol ALL ANSWERS CORRECT

Document Content and Description Below

CS 473 Homework 5 Solutions Spring 2010 1. (a) In the worst case, how long does it take to push one more element onto a multistack containing n elements? Solution: Every element already in the mult... istack is popped and pushed at most once when a new element is introduced. On the other hand, if every stack is full, every element will be moved at least once on the next push. Thus, the worst-case time for a push is Θ(n). „ Rubric: 2 points max: 1 point for answer + 1 point for proof. (b) Prove that if the user never pops anything from the multistack, the amortized cost of a push operation is O(log n), where n is the maximum number of elements in the multistack during its lifetime. Solution: A multistack containing n elements has at most log3 n non-empty stacks. Elements move to later stacks only as new elements are added, so each of the n elements is moved O(log n) times over the lifetime of the data structure. Thus, the total cost of n pushes is O(nlog n). The aggregate method implies that the amortized time per push is at most O(nlog n)=n = O(log n). „ Rubric: 3 points max: 2 for recognizing an element only moves forward + 1 for remaining details. This is not the only correct proof. Full credit for referring to part (c) is the given solution to part (c) is correct. (c) Prove that in any intermixed sequence of pushes and pops, each push or pop operation takes O(log n) amortized time, where n is the maximum number of elements in the multistack during its lifetime. Solution: Consider a single stack Si in the multistack. Say that a MPUSH or MPOP operation is relevant if the largest stack modified by the operation is Si. Each relevant MPUSH operation moves Pij−=10 3j = (3i − 1)=2 elements up to the next stack, and each relevant MPOP moves Pij−=10 3j(3i − 1)=2 elements down to the previous stack. Thus, each relevant operation runs in O(3i) time. Just before any relevant MPUSH, every smaller stack Sj with j < i is full, but Si is at most two-thirds full. Just after any relevant MPUSH, each smaller stack Sj (except S0) is exactly two-thirds full, and Si is at least one-third full. Just before any relevant MPOP, every smaller stack Sj with j < i is empty, and Si is at least one-third full. Just after any relevant MPOP, every smaller stack Sj (except S0) is exactly one-third full, and Si is at most two-thirds full. The first relevant operation must be an MPUSH, which must be preceded by at least Pij−=10 3j = (3i − 1)=2 irrelevant MPUSHes to fill all the smaller stacks. Between any two relevant operations, there must be either Pij−=11 3j−1 = (3i−1 − 1)=2 MPUSHes or MPOPs, to either fill up or empty all the smaller stacks. Thus, every relevant operation is preceded by Ω(3i) irrelevant operations. Thus, if we pay a tax of Θ(1) to Si at every operation, we save enough income to completely pay for each relevant operation. Since there are O(log n) stacks, and every operation is relevant for exactly one stack, we conclude that the total amortized cost of each operation is O(log n). „ Rubric: 5 points max: 3 points for bounding number of rounds needed to perform an expensive operation on a stack + 1 point for taxation scheme + 1 point for remaining details. This is not the only correct proof [Show More]

Last updated: 1 year ago

Preview 1 out of 4 pages