Programming - CSE 373 CSE 373 CSE 373 Home Projects CSE 143 Review System Setup Using IntelliJ Programming Unit Testing Commit & Submit Deques Getting Started Programming Tests Exercises Office Hours Staff Syllabus Course Tools Ed GitLab Gradescope Canvas Anonymous Feedback Acknowledgements Programming (16 points total) Deque ADT Debugging ArrayDeque Tips Implementing LinkedDeque Sentinel Nodes Invariants Submission Info See an introductory video for this assignment and logistics here. (This video is from the 20au offering of the course, so the announcements at the beginning of the video do not apply, but the main assignment is still the same.) Note The spec on the website mainly consists of high-level instructions to get you started on the project. Inside the code documentation, we provide more low-level implementation details necessary to complete the project. Deque ADT¶ Deques can do everything that both stacks and queues can do. Specifically, any deque implementation must have the following operations: Signature Description void addFirst(T item) Adds an item of type T to the front of the deque. void addLast(T item) Adds an item of type T to the back of the deque. T removeFirst() Removes and returns the item at the front of the deque. T removeLast() Removes and returns the item at the back of the deque. int size() Returns the number of items in the deque. boolean isEmpty() Returns true if deque is empty, false otherwise. T get(int index) Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth. Unlike lists, we do not allow clients to add items to the middle of a deque. We do, however, allow clients to access elements in the deque—this method primarily exists to make it easier for us to test the implementations. To get started, open deques/src/deques in IntelliJ. Take a look at the Deque.java file to explore the interface in more detail. There are a few important things to note here: The interface methods defined there include comments with extra notes on edge cases and preconditions. The Deque interface extends Java’s Queue interface—the Deque interface inherits all the methods defined by Java’s Queue interface, and any implementations of Deque must define those methods. In AbstractDeque.java, we define the relationships between our Deque interface and Java’s Queue; this means that subclasses of AbstractDeque can implement the functionality of a deque using our Deque interface, but also provide the functionality of a queue through Java’s Queue interface for free. Debugging ArrayDeque¶ Task Fix this buggy Deque implementation. Explore the Circular ArrayDeque Demo1 below to see how the ArrayDeque works: it works similarly to the ArrayQueue class presented in lecture. We’ve provided a nearly-working ArrayDeque implementation that is intentionally buggy, along with a failing test in BaseDequeTests.confusingTest that causes the bug to emerge. Your task is to fix the flaw in the implementation. (This should only involve changing at most 5 lines of code.) Follow the debugging cycle: Develop a hypothesis about what the root cause is based on what you know about the problem. Skim through the code in ArrayDeque.java to learn the layout of its methods and fields. Run the provided tests. Read through ArrayDeque again, focusing on methods relevant to the failing tests. Reproduce the issue in a minimal working example. Write and run simple unit tests to help determine what exactly is going wrong. The failing test that we provide makes it hard to debug since it calls many methods. You’ll want to write some simpler tests to figure out what exactly is going wrong. As an aside, it may be useful to write these new tests in BaseDequeTests so that you can later reuse them for LinkedDeque. Make productive changes based on the root cause discovered. Make sure that the unit tests you’ve written pass after you’ve fixed the issue. If there are more issues, return to step 1. Tips¶ Do not spend more than an hour debugging! It’s easy to lose track of time and get stuck in a deep hole when debugging. Please come to office hours, and remember to take breaks! Use the jGRASP visualizer in addition to IntelliJ’s debugger! It’s very useful for showing the current state of small programs. Java’s own stack trace is usually pretty informative about what errors occur. For example, the following stack trace shows that an addLast call is responsible for a NullPointerException: java.lang.NullPointerException
at deques.LinkedDeque.addLast(LinkedDeque.java:44)
at deques.BaseDequeTests.size_afterAddToOppositeEnds_is2(BaseDequeTests.java:126)
Implementing LinkedDeque¶ Task Implement our Deque interface in LinkedDeque, subject to the following additional requirements: add, remove, and size must run in constant time (operations must not involve any looping or recursion). Note: size is provided for you. get must use iteration, not recursion. The amount of memory that your program uses at any given time must be proportional to the number of items. For example, if you add 10,000 items to the deque, and then remove 9,999 items, the resulting data structure should use memory similar to a deque with 1 item. Do not maintain references to items that are no longer in the deque. Your implementation must use sentinel nodes and adhere to the associated invariants. Sentinel Nodes¶ Sentinel nodes are a type of node that never has any null references and doesn’t contain any meaningful data. This allows us to simplify how we handle linked nodes as we no longer need to check if a node is null before accessing it. When used in linked data structure, we can avoid null pointer exceptions by pointing our front and back fields to them, even with an empty data structure. Invariants¶ A data structure’s invariants are a set of internal requirements maintained by the data structure: they must be true before and after any of the data structure’s operations. A doubly-linked deque with sentinel nodes should include the following invariants: The front field always references the front sentinel node, and the back field always references the back sentinel node which allows us to skip null checks when accessing front or back. The sentinel nodesfront.prev and back.next always reference null. If size is at least 1, front.next and back.prev reference the first and last regular nodes, respectively. The nodes in your deque have consistent next and prev fields. For example, if a node curr has a curr.next, we expect to see curr.next.prev == curr. Since invariants are always meant to be true in a data structure, we can also explicitly check a data structure’s invariants to determine whether it’s behaving correctly. Our unit tests will extensively check the invariants to ensure that your deques always remain in a valid state. Tips¶ If you’re still not sure how to get started, look back at LinkedIntList from project 0 Work out what your LinkedDeque will look like on paper before you try implementing them in code! If you can find a willing partner, have them give commands, while you attempt to draw everything out. Try to come up with operations that might reveal problems with your implementation. Make sure you think carefully about what happens if the data structure goes from empty, to some non-zero size (e.g. 4 items) back down to zero again, and then back to some non-zero size. This is a common oversight. If you find your code failing the grader-only tests on Gradescope, you should try to recreate the test locally so that you can run and debug it. If your first try goes badly, don’t be afraid to scrap your code and start over. The amount of code for this part isn’t actually that much. (Our solution adds about 40 lines of code to the skeleton.) Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery. Likewise, if you’ve been stuck debugging for more than an hour, take a break and work on something else. Submission¶ If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission. Warning Submitting the same code as another student without using Gradescope’s group feature is considered plagiarism, and may have consequences. Josh Hug. 2019. cs61b sp19 proj1 slides. In CS 61B: Data Structures, Spring 2019. https://docs.google.com/presentation/d/1XBJOht0xWz1tEvLuvOL4lOIaY0NSfArXAvqgkrx0zpc/edit ↩ Josh Hug. 2019. cs61b lec5 2019 lists3, dllists and arrays. In CS 61B: Data Structures, Spring 2019. https://docs.google.com/presentation/d/1nRGXdApMS7yVqs04MRGZ62dZ9SoZLzrxqvX462G2UbA/edit ↩
