●    Do not rename or change the visibility of any methods already present. If a method or class is public leave it that way.

●    Submit early and often. The submission server compiles and runs your code and gives you a      mark. You can submit as often as you like and only your best submission will count. There is no excuse for submitting code that does not compile or does not pass tests.

●    Write efficient code. The submission server places a limit on how much time it will spend             executing your code, even on inputs with a million lines. For some questions it also places a limit on how much memory your code can use. If you choose and use your data structures correctly,  your code will easily execute within the time limit. Choose the wrong data structure, or use it      the wrong way, and your code will be too slow for the submission server to grade (resulting in a grade of 0).

Submitting and Testing

The submission server will become availablehere. If you have issues, please post to Discord to the teaching team (or the class) and we’ll see if we can help.

Warning: Do not wait until the last minute to submit your assignment. There is a hard 6 second limit on the time each test has to complete. For the largest tests, even an optimal implementation takes 5          seconds, and may take longer if the server is heavily loaded.

Start by downloading and decompressing the Assignment 2 Zip File (comp2402a2.zip), which contains a skeleton of the code you need to write. The skeleton code in the zip file compiles fine. Here's what it     looks like when you unzip and compile it from the command line:

alina@euclid:~$ unzip comp2402a2.zip

Archive:  comp2402a2.zip

inflating: comp2402a2/CapnStackSparrow.java

inflating: comp2402a2/FastSparrow.java

inflating: comp2402a2/SlowSparrow.java

inflating: comp2402a2/Tester.java

inflating: comp2402a2/WhatTheDeque.java

inflating: comp2402a2/WhatTheFast.java

inflating: comp2402a2/WhatTheSlow.java

alina@euclid:~$ javac comp2402a2/*.java

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. To run the Tester from the command line:

alina@euclid:~$ java comp2402a2.Tester

The Assignment

This assignment contains two main parts:

Part 1 [50 marks]: A CapnStackSparrow 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 SlowSparrow that implements these operations so that push(x) and pop() each run in 0(1) time, but max() and ksum(k) run in 0(n) time. For this question, you      should complete the implementation of FastSparrow that implements all four operations in 0(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 n) 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 WhatTheDeque 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 WhatTheSlow that supports each of addLast(x) and removeLast() operations in 0(1) time per operation but requires Ω(n) time for the other                 operations.

For this question, you should complete the implementation of WhatTheFast that implements all seven operations in 0(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 ofthe 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 n) 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.