Grading

This assignment will be tested and graded by a computer program (and you can submit as many times as you like). For this to work, there are some important rules you must follow:

• Keep the directory structure of the provided zip file. If you find a file in the subdirectory comp2402a4 leave it there.
• Keep the package structure of the provided zip file. If you find a package comp2402a4; directive at the top of a file, leave it there.
• 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 when performing millions of operations. An $O(\log n)$ time implementation will be able to pass most of the tests, but may not pass some of the largest tests. If this happens to you, remember that looking things up in an array of primitive types is significantly faster than following references to objects.

Submitting and Testing

The submission server is now accepting submissions. Please try it out.

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

The Assignment

Start by downloading the Assignment 4 Zip File, which contains a skeleton of the code you need to write.

Complete the implementation of the RyabkoTree class. This class implements the PrefixStack interface. The PrefixStack interface represents a stack of int values $x_0,\ldots,x_{n-1}$. The value $x_{n-1}$ is at the top of the stack and the value $x_0$ is at the bottom of the stack. supports the following operations on int values:

1. push(x): push the value x onto the top of the stack (i.e., set $x_n$ equal to x and increment $n$).
2. pop(): remove the top value $x=x_{n-1}$ from the stack, decrement $n$ and return $x$.
3. get(i): return the value of $x_i$.
4. set(i,x): set the value of $x_i$ equal to x
5. size(): return the size of the stack (the value of $n$)
6. iterator(): return an Iterator<Integer> that iterates over the values $x_0,\ldots,x_{n-1}$ in that order.
7. prefixSum(i): return a long value that is equal to the sum $x_0+x_1+\cdots+x_i$.

If you are confused about what any of these operations does, see the SlowPrefixStack class, included with assignment zip file, that includes a correct (but slow) implementation of the PrefixStack interface.

Your RyabkoTree implementation should implement these operations so that each operation runs in $O(\log n)$ time. (Remember that $O$ represents an upper bound, some operations may be faster.) Part of the work in this assignment is for you to figure out how to accomplish this using the ideas seen in this course. There is more than one way to do it and some ways are simpler to implement than others.

Software Engineering Note: A more generic PrefixStack implementation would not be restricted to int values but would instead store values of a generic type T and also include an AssociativeOperator that operates on two variables of type T and returns another variable of type T. Here we're restricting T to be int and AssociativeOperator to be +. Extending this to the general case is just an exercise is working with Java classes but wouldn't change any of the underlying principles.

For those doubting whether it's possible to pass all tests in the allotted time, here is an example of what it looks like.

Moving old submission out of the way
***************************************************************************
* Unzipping a4.zip
***************************************************************************
Archive:  a4.zip
   creating: comp2402a4/
  inflating: comp2402a4/SlowPrefixStack.java  
  inflating: comp2402a4/PrefixStack.java  
  inflating: comp2402a4/RyabkoTree.java


***************************************************************************
* Compilation
***************************************************************************
Executing: javac -encoding utf8 Tester.java
Executing: javac -encoding utf8 SlowPrefixStack.java
Executing: javac -encoding utf8 RyabkoTree.java
Executing: javac -encoding utf8 comp2402a4/SlowPrefixStack.java
Executing: javac -encoding utf8 comp2402a4/PrefixStack.java
Executing: javac -encoding utf8 comp2402a4/RyabkoTree.java
**********************************************************************
Tester
**********************************************************************
Running: java Tester -Xmx4m 80
Testing with N=80
Op counts: 99 push(x), 53 pop(x), 62 get(i), 57 set(i, x), 49 prefixSum(i)
Test succeeded in 0.007624023000000001 seconds

Test passed after 0.10624456405639648 seconds

Running: java Tester -Xmx4m 5000
Testing with N=5000
Op counts: 6672 push(x), 3275 pop(x), 3396 get(i), 3249 set(i, x), 3408 prefixSum(i)
Test succeeded in 0.06519058400000001 seconds

Test passed after 0.1666429042816162 seconds

Running: java Tester -Xmx34m 250000
Testing with N=250000
Op counts: 334368 push(x), 166248 pop(x), 166863 get(i), 166486 set(i, x), 166035 prefixSum(i)
Test succeeded in 0.292894967 seconds

Test passed after 0.38661932945251465 seconds

Running: java Tester -Xmx124m 1000000
Testing with N=1000000
Op counts: 1333874 push(x), 666663 pop(x), 666908 get(i), 666500 set(i, x), 666055 prefixSum(i)
Test succeeded in 1.086526691 seconds

Test passed after 1.1844408512115479 seconds

Running: java Tester -Xmx244m 2000000
Testing with N=2000000
Op counts: 2667923 push(x), 1333393 pop(x), 1333012 get(i), 1333529 set(i, x), 1332143 prefixSum(i)
Test succeeded in 2.229143161 seconds

Test passed after 2.3287928104400635 seconds

Running: java Tester -Xmx484m 4000000
Testing with N=4000000
Op counts: 5334404 push(x), 2668354 pop(x), 2665749 get(i), 2666473 set(i, x), 2665020 prefixSum(i)
Test succeeded in 4.745669695 seconds

Test passed after 4.845250606536865 seconds



***************************************************************************
* Mark: 10/10
***************************************************************************