Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COMP 2402 ABC - Fall 2024
Assignment 4
Submit early and often. Late submissions (up to 12 hours after the deadline) will be accepted without penalty. The auto-grader stops at noon on Wednesday, November 20. No late submissions will be accepted after that. Assignments sent to the teaching team by email will be ignored.
Academic Integrity Guidelines
You are encouraged to:
- Discuss general approaches and concepts with the teaching team and classmates.
- Use code and ideas from the course textbook (with proper citation in comments).
- Use internet searches to clarify basic Java syntax or concepts.
However, you may not:
- Share or exchange code, code snippets, or solutions with classmates.
- Use code not written by you unless it’s from the course textbook (and you should cite it in comments).
- Search the internet for specific solutions or approaches to the assignment.
- Reuse code from previous course iterations, unless it was entirely your own work.
- Seek external source code, videos, or online solutions that directly address the assignment.
If you ever have any questions about what is or is not allowable regarding academic integrity, please do not hesitate to reach out to course staff. We will be happy to answer. Sometimes it is difficult to determine the exact line, but if you cross it the punishment is severe and out of our hands. Any student caught violating academic integrity, whether intentionally or not, will be reported to the Dean and be penalized. Please see Carleton University's Academic Integrity page.
Remember: While collaboration and discussions can enhance learning, your submitted work must reflect your own effort and understanding. Always cite any external sources you reference.
Copyright
All assignment materials (including this pdf, source code, input/output files, workshop materials, and solutions videos) are protected by copyright. These materials are provided for your personal educational use only. Reproducing, reposting, or redistributing any course materials, in part or in whole, without the written consent of the instructor is a copyright violation and is strictly prohibited. Posting your assignment solutions on GitHub or any other public website violates copyright and is strictly disallowed.
Download the Provided Files
Grading
- Keep the directory structure of the provided comp2402a4.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 .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 goal for this assignment is to write efficient code. If you select and implement your data structures correctly, your code will execute efficiently within the time and memory limits. However, if you choose inappropriate data structures or misuse them, your code may run too slow to be graded by the auto-grader, resulting in a grade of 0.
- The auto-grader places a time limit on how long it will be executing your code, often testing with over a million elements and operations.
- Memory usage is also capped.
Submitting and Testing
Submitting to the Gradescope is easy – drag and drop ALL your .java files in the provided submission window. If you have issues, please post them on Discord so the teaching team (or the class) can try to help you. Including screenshots is a good idea.
When you submit your code, the auto-grader runs numerous tests on your code. These are bigger and better tests than the small number of tests provided in the Tester.java file. We will not disclose the tests used by the auto-grader, because you should try to find exhaustive tests of your own code. You are encouraged to add your tests to the Tester.java file and test locally before trying your submission on Gradescope.
The auto-grader has a strict time limit for each test case. Your code must complete each test within 5 seconds. Any test that exceeds this limit will be marked as failed, and no further tests for this part will be run if the current test fails. For the largest tests, even an optimal implementation takes 3 seconds, and might take longer if the server is under heavy load. To avoid issues, please start submitting your assignment well in advance.
Start by downloading and decompressing the Assignment 4 Zip File (comp2402a4.zip), which contains a skeleton of the code you need to write. Be patient with yourself, and make sure you read the specifications carefully.
The skeleton code in the zip file compiles fine. You can unzip the file (extract its content) in numerous ways, such as by drag-and-drop or right-mouse-click “Extract all”. Here's what it looks like when you unzip, compile, and run the Tester class from the command line (the commands that you type are highlighted in yellow):
For this assignment, you only need to implement one data structure: the Ultra Stack. Please add your code to the UltraFast.java file. The Tester class, included in the zip file, gives a very basic demonstration of the code. Despite the name, Tester does not do thorough testing. The auto-grader will do thorough testing.
If you are having trouble running these programs, figure this out first before attempting to do the assignment. If you are stuck, ask on Discord, and our teaching team or another student will likely help you fairly quickly.
The Assignment
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, andreturns 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 topof 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 onerations 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(logn).
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<Integer> 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
- 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.
How should I test my code?
For this assignment, you will have to test your own code thoroughly. The auto-grader will perform a range of tests on your implementation. In case your code throws an exception, the auto-grader will tell you which method threw the exception and what kind of exception it was. Other than that, the auto grader will consume anything that you try to print to System.out or System.err, so the testing done on the auto-grader will be almost completely opaque. It will only give you a generic error of the form "get(i) returns incorrect value", or "Program timed out". On the positive side, testing is something you can do easily because UltraSlow is a correct implementation that you can use to test against. Be sure to test a good mix of operations that includes and interleaves push(x), pop(), get(i), set(i, x),doubleTop(), swapTop(), max(), ksum(k), and size().
Please remember that the auto-grader does not give much information when things go wrong. The autograder cannot determine logical errors from crash reports and the responsibility falls on the programmer. You are advised to write your own tests and test your code locally, where you have more control over debugging your code.
- The Tester class, included in the zip file gives a very basic demonstration of the code. Despite the name, the provided tester is meant to be more of a user guide to get started with the skeleton code and by no means, a representative of the tests performed on the server side.
- You are advised to modify the Tester class. For example you can change the “20” in ultraTest(); to a smaller/bigger number to test less/more operations.
- Design your own test cases, throw in a good mix of operations that includes and interleaves push(x), pop(), get(i), set(i, x), doubleTop(), swapTop(), max(), ksum(k), and size().
- Test your code as you go along. The slow (but correct) solutions can always be taken as reference when testing.
- Use small tests first so that you can compute the correct solution by hand.
- Try to “break” your solution with the tester, in every way you can think of. And of course, don’t forget to test with large test sizes.
- Think about edge cases, large inputs, empty inputs, and random inputs.
- Suppose you have print statements (System.out) in your program that you may have used for debugging use System.out. The auto-grader will execute those statements but ultimately will remove the output generated by the statements from the response. You probably already know how console output can be painfully slow. Even worse, it could cause the testing program to crash if the output is large. So, remember to remove such statements before submitting your work.
- Test for both correctness and speed. Write the correct code first, then think about how to make it fast.