Project 1 Extra Credit: Autograding

Introduction
Getting the Skeleton Files
Randomized Testing
- Task I
- Task II
Tips
Frequently Asked Questions

Introduction

This project is optional and worth a total of 32 extra credit points. In this project, you will build a rudimentary autograder for the data structures part of project 1. This project may be quite challenging and is considered extra credit, so it will have the lowest priority during office hours and Ed.

In the skeleton, we have provided the following files for Project 1 Extra credit:

student/StudentArrayDeque.java: A buggy implementation of ArrayDeque.
tester/ArrayDequeSolution.java: A correct implementation of ArrayDeque.
tester/AssertEqualsStringDemo.java: Demo of how to use assertEquals.
tester/StudentArrayDequeLauncher.java: Demo of how to use StudentArrayDeque.

You’ll note again that we’re using packages here to separate the student implementation with the testing infrastructure.

Getting the Skeleton Files

As before, pull the skeleton using the command git pull skeleton master.

Randomized Testing

Here’s a fun secret: The autograder for project 1 largely relies on randomized tests. For example, our JUnit tests on Gradescope simply call random methods of your LinkedListDeque class and our correct implementation LinkedListDequeSolution, and as soon as we see any disagreement, the test fails and prints out a sequence of operations that caused the failure. In this part of the project, you’ll pretend you’re writing the autograder for the class using these same ideas.

We will introduce here how to make nice JUnit error messages which is actually a very great skill. Your future employers will love you if your tests have simple to read and helpful error messages.

To start off this project, you should start by making sure your IntelliJ has properly imported the project. To do this, try running the StudentArrayDequeLauncher.java file. If it works, you should see the numbers between 0 and 9 printed out (not necessarily in order). If you run into any issues, follow the instructions in lab2.

Task I

Next, create a JUnit test file called TestArrayDequeEC.java in your tester package. Start your file with the needed package declaration:

package tester

Then make sure to add the neccessary imports:

import static org.junit.Assert.*;
import org.junit.Test;
import student.StudentArrayDeque;

In this file, write a single JUnit test marked with the @Test annotation. The name of your test method does not matter. Your test should randomly call StudentArrayDeque and ArrayDequeSolution methods until they disagree on an output. You can generate random numbers using the StdRandom library (Documentation can be found here). Use StudentArrayDequeLauncher as a guide, and if you copy and paste code from StudentArrayDequeLauncher, make sure to cite your source using an @source tag. You might find the tests that you wrote for Project 1 useful here.

We are not testing the equals(Object o) and iterator() methods in this extra credit assignment, so only write tests for the other methods.

For this project, you must use Integer as your type for the Deque, i.e. StudentArrayDeque<Integer>. You should be able to find an error using only the addFirst, addLast, removeFirst, and removeLast methods, though you’re welcome to try out the other methods as well.

Your test should NOT cause a NullPointerException. Make sure you never try to remove from an empty ArrayDeque, since Integer x = ad.removeFirst() will cause a NullPointerException. Additionally, for this project always use Integer instead of int when you are retrieving values from the deques, i.e. do not do int x = ad.removeFirst(). For an explanation of why this causes problems, please read the “Frequently Asked Questions” below.

Task II

Once you’ve managed to get the test consistently failing, the trickier part begins. Simply telling the student that their code fails is only going to lead to tears, sadness, confusion and late night Ed posts. Thus, you’re going to modify your autograder so that it tells the student something useful.

To do this, we’ll take advantage of the assertEquals(message, expected, actual) method, which outputs a helpful message to the user.

For an example of how this method works, see AssertEqualsStringDemo.java in the examples folder.

Modify your TestArrayDequeEC.java so that the message parameter to assertEquals contains a list of operations that cause the StudentArrayDeque to output the wrong answer.

The string message provided to assertEquals must be a series of method calls, where the last call in the sequence yields an incorrect return value. For example, if adding 5 to the front, then 3 to the front, then removing from the front yields an incorrect value, then the String message passed to assertEquals should be exactly the following, with newlines in between each command.

addFirst(5) 
addFirst(3)
removeFirst()

You do not need to supply the expected and actual values as part of the String message, since those are passed separately to the assertEquals statement as the expected and actual parameters. In other words, your message should NOT look like:

addFirst(5) 
addFirst(3)
removeFirst(), student was 3, correct was 7

It should also not look like:

addFirst(5) 
addFirst(3)
removeFirst(): 3
removeLast(): 4

Tips

It’s probably not a good idea to write tests that compare entire Deques at once. Suppose you write a compareDeques(studentDeque, solutionDeque) method that returns false. Even if this function returns false, that doesn’t give you an operation that causes a failure. It’s much easier to test the output of single operations (e.g. student.removeFirst() vs. solution.removeFirst()).
If you insist on comparing entire Deques at once, assertEquals will not work the way you’d hope. For example, assertEquals(deque1, deque2) will not return true if all the items are the same. You’ll need to write your own comparison method if you want to compare entire deques, though to be honest, there’s no reason to do this for this assignment.
The StdRandom class is the easiest way to generate random numbers. See the official documentation for a list of methods.
There’s no need to do any exception catching or throwing on this assignment (we haven’t learned this in CS 61B yet).
Build a failure sequence as you perform operations! Don’t try to construct it only after a failure has been detected (this is really hard).

Frequently Asked Questions

How would I write a test for printDeque()?

It would be rather involved, and our autograder isn’t quite smart enough to be able to read your output anyway. Stick with the other methods. If you’re really truly curious, google “redirect standard output”.

I’m getting a “reference to assertEquals is ambiguous” error.

Always try searching the web for mysterious error messages. Recall that self-sufficiency as a programmer is a major goal of CS 61B. I think the first hit on Google should be enough.

I keep getting a `NullPointerException`

First, make sure you’re not trying to get from somewhere beyond the available size. Second, if you’re writing code like int result = deque.removeFirst(), instead write Integer result = deque.removeFirst().

This error happens because Java will freely convert from Integer (boxed type) to int (primitive type). This is called unboxing. However, only reference types can be null, so if you try to automatically convert a null Integer to an int, you’ll get a NullPointerException in your own code. The StudentArrayDeque is buggy and may return a null (incorrectly), which can trigger this problem in your code.

The autograder is complaining about my failure sequences.

As you might imagine, the autograder for this gold project is a weirdly complex beast, as it is has to autograde autograder output. To keep things simple the String argument to a failing assert must contain a failure sequence and ONLY a failure sequence, and all tests must fail due to a failing assert. There should be no failures due to null pointer exceptions. The String argument to your assert statement must contain no extraneous information.

The autograder is still complaining about my failure sequences.

You need to include the operation that caused the failure. For example, if size() returns the wrong value, you need to include size() in your failure sequence, since you’re required to provide “a series of method calls, where the last call in the sequence yields an incorrect return value”. Also make sure your failure sequence only appears once!

I tried all that and the autograder is still complaining about my failure sequences.

Copy the reported failure sequence from the online autograder, and write a simple file Quick.java which generates a studentDeque, applies the operations listed, and prints the result of the final step. Chances are you’ll find that the result is not the same as your test reported in the AG. Most likely you forgot to include an operation, or possibly added operations you didn’t actually make.k