Suppose that we have a data structure called reversing stack. This data structure supports only one operation called REVERSING-PUSH. In each REVERSING-PUSH, an object is first pushed onto the stack, and then we check if the number of items in the stack is a power of 2. If it is not, we terminate the REVERSING-PUSH. If it is, then we reverse the content of the stack, that is, we swap the object on the top of the stack with the object on the bottom, the second topmost object with the second bottommost object, and so on. For example, if we use REVERSING-PUSH to push objects 1, 2, 3, 4, 5, 6, 7, 8, 9 onto the stack, the stack contents, when listed from bottom to top, after each operation are (1), (2, 1), (2, 1, 3), (4, 3, 1, 2), (4, 3, 1, 2, 5), (4, 3, 1, 2, 5, 6), (4, 3, 1, 2, 5, 6, 7), (8, 7, 6, 5, 2, 1, 3, 4), (8, 7, 6, 5, 2, 1, 3, 4, 9) Use all the three methods for amortized analysis taught in class (aggregate, ac- counting and potential) to show that REVERSE-PUSH runs in O(1) amortized time. In your analysis, you can assume that the cost of reversing the content of the stack is equal to the number of objects currently in the stack (think about why this is a valid assumption).
Time to preview question:
00:08:29
Suppose that we have a data structure called reversing stack. This data
structure supports only one operation called REVERSING-PUSH. In each REVERSING-PUSH,
an object is first pushed onto the stack, and then we check if the number of items in
the stack is a power of 2. If it is not, we terminate the REVERSING-PUSH. If it is,
then we reverse the content of the stack, that is, we swap the object on the top of
the stack with the object on the bottom, the second topmost object with the second
bottommost object, and so on. For example, if we use REVERSING-PUSH to push objects
1, 2, 3, 4, 5, 6, 7, 8, 9 onto the stack, the stack contents, when listed from bottom to top,
after each operation are
(1), (2, 1), (2, 1, 3), (4, 3, 1, 2), (4, 3, 1, 2, 5), (4, 3, 1, 2, 5, 6),
(4, 3, 1, 2, 5, 6, 7), (8, 7, 6, 5, 2, 1, 3, 4), (8, 7, 6, 5, 2, 1, 3, 4, 9)
Use all the three methods for amortized analysis taught in class (aggregate, ac-
counting and potential) to show that REVERSE-PUSH runs in O(1) amortized time. In
your analysis, you can assume that the cost of reversing the content of the stack is
equal to the number of objects currently in the stack (think about why this is a valid
assumption).
Hint: It may be helpful to think of the largest power of 2 that is less than or equal to
n
Step by step
Solved in 2 steps
