SOLVED COMP 2402AB Assignment #2

The Assignment This assignment contains two main parts: Part 1 [50 marks]: A SuperStack is an extended stack that supports four main operations: the standard Stack operations push(x) and pop() and the following non-standard operations: • max(): returns the maximum value stored on the Stack. • ksum(k): returns the sum of the top k elements on the Stack. The zip file gives an implementation SuperSlow that implements these operations so that push(x) and pop() each run in 𝑂(1) time, but max() and ksum(k) run in 𝑂(𝑛) time. For this question, you should complete the implementation of SuperFast that implements all four operations in 𝑂(1) (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: 1. don't use any kind of SortedSet or SortedMap, these all require Ω(log 𝑛) time per operation. 2. think about how the maximum on the stack changes as new elements are pushed. Understanding this will help you design your data structure. Part 2 [50 marks]: A DuperDeque is an extended Deque that supports seven operations: The standard Deque operations addFirst(x), removeFirst(), addLast(x), and removeLast() and the following non-standard operations: • max(): returns the maximum value stored on the Deque. • ksumFirst(k): returns the sum of the first k elements on the Deque. • ksumLast(k): returns the sum of the last k elements on the Deque. Again, the zip file provides an implementation DuperSlow that supports each of addLast(x) and removeLast() operations in 𝑂(1) time per operation but requires Ω(𝑛) time for the other operations. For this question, you should complete the implementation of DuperFast that implements all seven operations in 𝑂(1) (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: 1. don't use any kind of SortedSet or SortedMap, these all require Ω(log 𝑛) time per operation; 2. you can write additional functions to support your design choices; consider using one of the techniques we've seen in class for implementing the Deque interface.   Abstract Data Types and Algorithms Assignment 2 Tips, Tricks, and FAQs How should I approach each problem? • Make sure you understand it. Construct small examples, and compute (by hand) the expected output. If you aren’t sure what the output should be, go no further until you get clarification. • Now that you understand what you are supposed to output, and you’ve been able to solve it by hand, think about how you solved it and whether you could explain it to someone. How about explaining it to a computer? • If it still seems challenging, what about a simpler case? Can you solve a similar or simplified problem? Maybe a special case? If you were allowed to make certain assumptions, could you do it then? Try constructing your code incrementally, solving the smaller or simpler problems, then, only expanding scope once you’re sure your simplified problems are solved. How should I test my code? • You can modify the Tester class. For example you can change the “20” in superTest(new SuperFast(), 20); to a smaller/bigger number to test less/more operations. • The Tester class provided with the assignment does a sequence of adds, followed by a sequence of removes. This is a very basic test and far from an exhaustive one. It is strongly recommended to modify the tester and design your own test cases. For starters, you can interleave the add and remove operations. Take it even further by making the operation sequence entirely random. This will help you to discover the weaknesses in your solution. • You should be testing your code as you go along. • Beware of integer overflow. Note that ksum is of type long - not int. • Think about tricky cases. For instance, how do the operations behave when the stack/deque is empty, or k > n or k <= 0? You can always refer to the slow implementations to answer these questions. Although they are slow, they are correct implementations. They can also be useful if you want to test your implementation against a reference one. • int and Integer are not the same. Do not use them interchangeably. • Use small tests first so that you can compute the correct solution by hand. • Test for speed.