Description
The Assignment Start by downloading the Assignment 2 Zip File, which contains a skeleton of the code you need to write. The Tester class, included in the zip file gives a very basic demonstration of the code. As is, Tester throws an exception when it tries to test FastMinStack and FastMinDeque because they’re not implemented yet. Despite the name, Tester does not do thorough testing. The submission server will do thorough testing. 1. [5 marks] A MinStack supports three main operations: the standard Stack operations push(x) and pop() and the non-standard min() operation which returns the minimum value stored on the stack. The zip file gives an implementation SlowMinStack that implements these operations so that push(x) and pop() each run in time, but min() runs in time. For this question, you should complete the implementation of FastMinStack that implements all three operations in time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don’t forget to also implement the size() and iterator()* methods. Think carefully about your solution before you start coding. Here are two hints: (i) don’t use any kind of SortedSet or SortedMap, These all require time per operation; (ii) take a look at the sample solution for Part 10 of Assignment 1. Really O(1) Θ(n) O(1) Ω(log n) Assignment 2: Min-Stacks and Min-Deques 2020-12-12, 3:02 PM https://cglab.ca/~morin/teaching/2402/assn/assn2.html Page 3 of 4 understanding this solution will help you design your data structure. 2. [5 marks] A MinDeque supports five operations: The standard Deque operations addFirst(x), removeFirst(), addLast(x), and removeLast() and the nonstandard min() operation that returns the minimum value stored in the Deque. Again, the zip file provides an implementation SlowMinDeque that supports each of the first four operation in time per operation but requires time for the min() operation. For this question, you should complete the implementation of FastMinDeque that implements all five operations in (amortized) time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don’t forget to also implement the size() and iterator()* methods. Think carefully about your solution before you start coding. Here are two hints: (i) don’t use any kind of SortedSet or SortedMap, These all require time per operation; (ii) consider using one of the techniques we’ve seen in class for implementing the Deque interface. *You can still get part marks without correctly implementing the iterator() method. But for full marks, the iterator() method needs to return an Object that supports the next() and hasNext() methods from the Iterator interface. For a MinStack, the iterator should output the elements at the bottom of the stack first (the elements that have been in the stack the longest), finishing with the element at the top of the stack (the element that would be returned by a call to pop()). For a MinDeque, the iterator should output the elements beginning with the first element (the one that would be returned by removeFront()) and finishing with the last element (the one that would be returned by removeLast()). Hint: There’s no need to build your iterators from scratch. The collections in java.util all have iterators. O(1) Ω(n) O(1) Ω(log n) Assignment 2: Min-Stacks and Min-Deques 2020-12-12, 3:02 PM https://cglab.ca/~morin/teaching/2402/assn/assn2.html Page 4 of 4
