Introduction

Working with the Instructions¶

We try to keep high-level instructions on the website, where we have access to nice styling and can provide information in order. On the other hand, we try to keep low-level implementation details in the code documentation so that they do not clutter up the assignment instructions. We also aim to minimize the amount of content repeated between the website instructions and code documentation, so you will likely need to shift back and forth between the website and your IDE while completing the assignment. We recommend keeping both open as you work.

Additionally, you may need to poke around the project files to find relevant documentation. To assist in doing so, check out this IntelliJ cheat sheet from 20wi. In particular, the “Go to declaration” and “Quick documentation lookup” commands are very useful for finding method documentation.

Callout Boxes¶

As you’ve probably already seen, our website makes use of colored callout boxes to highlight important information. Make sure to read these boxes, and try to remember them as you complete the assignment.

• Important: We use these for important information that EVERYONE should be cognizant of; often, they indicate something you must avoid doing.
• Warning: These indicate something specific to be careful about, but that may not affect everybody. Often, these point out common issues or mistakes that may cost a disproportionate amount of time to debug.
• Info: A relevant piece of information we’d like to highlight for everybody.
• Tip: A suggestion or advice about the assignment.
• Note: Usually an aside or comment that may not be relevant to everybody; these are usually less important than the other types of callouts above.

Section Labels¶

Each section on webpages that describe an assignment will include one of 3 labels to indicate the type of content in the section:

• Background: background or introductory information that may help you complete the assignment.
• Task: a deliverable task that you must do in order to complete the assignment.
• Reference: describes some code we’ve provided purely for your reference. These do not have any deliverable tasks, but reading through the indicated code may help you complete the assignment.

Program Structure¶

Most of the project tasks in this course share the same overall project structure: each assignment will come in its own IntelliJ module, with a src submodule containing the main assignment code and a test submodule containing JUnit tests for the assignment.

The main module will include a Java package with an interface or abstract class representing the main ADT for the assignment, and your job will be to implement that ADT in one or more subclasses. Usually, the ADT‘s interface or abstract class will include method-level documentation that describes edge cases and other details beyond the cursory description in the website instructions, and the subclasses will only contain method stubs with documentation for details specific to that implementation, if any.

In this assignment, the main interface is deques.Deque, and you’ll be working in the ArrayDeque and LinkedDeque classes in the same package.

Like in the previous assignment, changes to other classes (or attempts to add new files) will be ignored during grading; however, you may need to import or use this other provided code in your implementation.

Assignments will also include client packages that act as users of the ADT/data structure you implement. In this assignment, the client is contained in the deques.experiments package, which displays runtime plots of some provided experiment methods that use the deques you implement.

However, unlike the previous assignment, this and all future assignments will have extremely lax restrictions on classes you are allowed to import: in general, all imports are allowed except for classes that solve exactly the same problem presented in the assignment.

For example, for this assignment, the only restricted imports are for Java’s own deque and list implementations.

Provided Test Classes¶

Given that we’ll often be working with different implementations of an ADT that provide identical functionality, it stands to reason that the code for testing the functionality of different implementations would also look similar.

In order to share test code, our provided tests are often written in an abstract base test class, where each test method calls an abstract method to obtain the instance of the class to test. This way, we can create multiple sub-test-classes of this base test class, each overriding the abstract method to construct instances of the different ADT implementations.

In this assignment, the base test class is BaseDequeTests, and its subclasses ArrayDequeTests and LinkedDequeTests test ArrayDeque and LinkedDeque respectively.

As it turns out, this design pattern has dedicated support in IntelliJ, so attempting to run an abstract test class or a test method in one of them will cause IntelliJ to bring up a menu allowing you to select which implementation to run.

Grader-Only Tests¶

Your code for this and all future assignments will be graded based on some tests that are not provided with the skeleton code and run exclusively on Gradescope.

Usually, these grader-only tests either:

1. involve some setup that is too confusing to be useful (or some code that we simply cannot provide, e.g., when we need to time submissions against our solution code)
2. are test cases that we’ve intentionally decided to withhold in order to encourage you to write your own tests and think about your own code

This second point is particularly important: if you find yourself wondering why your code fails a grader-only test, write a test to replicate the failure. Afterwards, you’ll be able to use the debugger to investigate the issue.

Submission Rate Limiting¶

Finally, a note on the rate limits enforced by the Gradescope autograder: project 0 included nominal rate limiting, but from this project onward, the limiting will be stricter. The limiting is intended to discourage you from abusing the autograder system (e.g., by spamming submissions just to see feedback on grader-only tests, without thinking about changes you’re making), so most students working normally should never actually hit the limit.

To make the system easier to understand, we describe the limiting in terms of submission tokens: you’ll start each assignment with the maximum number of tokens for that assignment, and grading a submission consumes 1 token. Tokens will recharge some rate (depending on the assignment) as long as you’re under the max token count. If you make a submission with no tokens remaining, your submission will not be graded, and you’ll need to resubmit after you get a token back. (The submission feedback on Gradescope should include the time of your next token recharge.)

For each assignment, the max token count is 6, and 1 token will recharge every 10 minutes.

Now, you should be ready for the programming portion of the assignment.