Download the Provided Files

The base code for this assignment consists of one zip file, which you can download from Brightspace:

comp$2402$a$4.$zip $-$ source code. This file contains a folder named comp$2402$a$4$ with four $.$java files:

UltraFast.java $-$ add your code here

UltraSlow.java

UltraStack.java

Tester.java $-$ use this class to design your tests and debug$/$test your code

Grading

This assignment will be tested and graded by a computer program also known as an auto$-$grader. You

can submit as many times as you like; your highest grade is recorded. For this to work, there are some

important rules you must follow:

Keep the directory structure of the provided comp$2402$a$4.$zip file. If you find a file in the

subdirectory comp$2402$a$4$ leave it there.

Keep the package structure of the provided zip file. If you find a package comp$2402$a$4$;

directive at the top of a $.$java file, leave it there.

Keep the interfaces as they are. You may add internal methods to your implementation, but do

not introduce any new methods to the interfaces.

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 auto$-$grader will compile and run your code, providing you with

instant feedback and a grade. You can submit as many times as you like $-$ your final grade will

reflect your last submission. Alternatively, you can choose to activate your highest$-$graded

submission as your final score. With this flexibility, there's no excuse for submitting code that

doesn't compile or fails the tests.

Similarly to the previous assignments, your methods are not independent and cannot be tested

independently.

Start by exploring the skeleton code $-$ it includes implementations for all the required methods

but is based on a slower model.

The Assignment

This assignment contains only one part worth $100$ marks.

The data values we will maintain are integers, both negative and positive.

An UltraStack is an extended stack that supports eight main operations: the standard Stack

operations push $($ x $)$ and pop$()$ and the following non$-$standard operations:

get$($i$)$: returns the i$-$th element $($from the bottom$)$ on the Stack.

set$($i$,$x$)$ : sets the value of the i$-$th element $($from the bottom$)$ on the Stack to x$,$ and

returns the element that was previously stored at the same position.

doubleTop$()$: reads the top element x from the Stack and adds a new element $2^(**)$x to the top

of the Stack.

swapTop$()$: swaps the top two elements of the Stack.

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 of UltraSlow, which correctly implements these operations so

that push$($x$),$ pop$(),$ get$($i$),$ doubleTop$(),$ swapTop$(),$ and set $($i$,$ x$)$ each run in O $(1)$ time,

but max $()$ and ksum$($k$)$ run in O$($n$)$ time. The provided implementation of the UltraFast is just a

copy of UltraSlow implementation.

You must complete the implementation of UltraFast by correctly coding all eight operations and

optimizing their efficiency. For UltraFast, the running time for get $($i$)$ and max $()$ must be O$(1),$ and

for push$($x$),$ pop$(),$ set $($i$,$ x$),$ doubleTop$(),$ swapTop$(),$ and ksum$($k$)$ running time must not

exceed O$($log n$).$

You may assume that the Stack elements will be in the range $[-3000000,3000000].$

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 ODS textbook.

Remember to implement both the size$()$ and iterator$()$ methods. The iterator$()$ method

should return an Iterator that iterates over the values in order, starting from the bottom

and ending at the top of the Stack. Your iterator must support the following two methods:

next $()-$ that returns the next element in the iteration.

hasNext $()-$ that returns true if this list iterator has more elements when traversing the list in the forward direction. $($In other words, returns true if next $()$ would return an element rather than throwing an exception.$)$

Tips, Tricks, and FAQs

Take time to plan your solution carefully before starting to code. Here are two hints to guide you:

Storing partial sums and partial maximums can significantly reduce computation when updating an element in the stack. Refer to the figure below for a visual aid. Complete binary trees can be efficiently stored using arrays. Heaps leverage this approach to organize their elements. This means you do NOT need to rely on pointer$-$based DSs$.$ For additional insights on index$-$based parent$/$child access, refer to Lecture $13.$ The Stack elements will be in the range $[-3000000,3000000].$ You can leverage this by initializing the max data structure with Integer. MIN$\_$VALUE to help implement the max$()$ efficiently.