Description
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.
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.
