CSE 12 Programming Assignment 5

Testing Partition

This assignment is open to collaboration.

This assignment will teach you how to write tests in a thorough, automated way, will explore some properties of quicksort, and will give you structured practice in re-using code you find on the Web.

This assignment is inspired by an assignment from Brown University’s CS019.

This PA is due on ** Tuesday, May 3 at 10:00pm **

Getting the Code

The starter code can be found from: https://github.com/ucsd-cse12-sp22/cse12-pa5-Partition. If you are not familiar with Github, here are two easy ways to get your code.

  1. Download as a ZIP folder

    If you scroll to the top of Github repository, you should see a green button that says Code. Click on that button. Then click on Download ZIP. This should download all the files as a ZIP folder. You can then unzip/extract the zip bundle and move it to wherever you would like to work. The code that you will be changing is in the folder called pa5-starter.

  2. Using git clone (requires terminal/command line)

    If you scroll to the top of the Github repository, you should see a green button that says Code. Click on that button. You should see something that says Clone with HTTPS. Copy the link that is in that section. In terminal/command line, navigate to whatever folder/directory you would like to work. Type the command git clone _ where the _ is replaced with the link you copied. This should clone the repository on your computer and you can then edit the files on whatever IDE you see fit.

If you are unsure or have questions about how to get the starter code, feel free to make a Piazza post or ask a tutor for help.

File Summary

Part I: A Bad (and Good) Implementation Detector

Testing with Properties

So far in this class, we have usually written tests by following this process:

  1. Construct the input data
  2. Perform an operation
  3. Check that the resulting data is equal to some expected value

This works well for writing a small or medium number of tests targeted at particularly interesting cases. Checking specific output values, however, isn’t the only or necessarily the best way to test and gain confidence in an implementation. In fact, sometimes it won’t work at all.

Consider the partition helper method of quick sort as an interface (here we’ll restrict it to just partitioning arrays of Strings):

interface Partitioner {
  // Change strs between start (inclusive) and end (exclusive), such that
  // all values at indices lower than a pivot index are smaller than or equal
  // to the value at the pivot, and all values at indices higher than the pivot
  // are larger than or equal to the value at the pivot

  int partition(String[] strs, int start, int end);
}

In lecture and discussion, we noted that there are many ways to implement partition, in particular the choice of the pivot index is important. Not only could we choose different pivots, but one choice is to have a random choice of pivot! Let’s imagine writing a test for a Partitioner:

class PartitionerFromLecture implements Partitioner {
  public int partition(String[] strs, int low, int high) {
    int pivotStartIndex = Random.nextInt(high - low);
    ... implementation from lecture ...
  }
}


@Test
public void testPartitionerFromLecture() {
  Partitioner p = new PartitionerFromLecture();
  String[] input = {"z", "b", "a", "f"};
  int pivot = p.partition(input, 0, 4);

  assertArrayEquals(???, input); // What to expect?
  assertEquals(???, pivot);
}

For two items, there are some clever solutions. You can use special matchers, for instance.

Instead of writing out all the tests by hand, we should step back from the problem. We really care that the array is correctly partitioned – there shouldn’t be elements larger than the pivot value at earlier indices, or elements smaller than the pivot value at later indices. There are other properties, too, like all the elements that were in the input list should appear the same number of times in the output list – if partition duplicates or loses elements, it isn’t doing its job!

So, instead of writing single tests, we should write methods that, given a partition algorithm, check if it satisfies some desired properties that partitioning ought to. Properties sufficient to show a valid partitioning are:

Your Task

You will turn the properties above into code that checks if a given result from partition is valid. That means your program will decide, for any call to partition, if it behaves as we’d expect. Further, we can extend this idea to build a method that takes a Partitioner and returns null if we believe it to be a good partitioner, and a CounterExample if we can find an input array and low/high bounds that partition incorrectly:

CounterExample findCounterExample(Partitioner p);

CounterExample is defined to contain:

You will write a version of CounterExample and use it to check multiple different partition implementations, some good and some bad. Note that, even beyond the argument above about randomness, there are multiple possible correct implementations of partition.

You must implement two methods to help you implement CounterExample; you can implement other helpers as you see fit. The two methods you must implement are:

/*
 * Return null if the pivot and after array reflect a correct partitioning of 
 * the before array between low and high.
 *
 * Return a non-null String (your choice) describing why it isn't a valid
 * partition if it is not a valid result. You might choose Strings like these,
 * though there may be more you want to report:
 *
 * - "after array doesn't have same elements as before"
 * - "Item before pivot too large"
 * - "Item after pivot too small"
 */
String isValidPartitionResult(String[] before, int low, int high, int pivot, String[] after)

/*
 * Generate a list of items of size n
 */
String[] generateInput(int n);

This method should create a list of items to use as input to purported partition algorithms. It’s up to you how it generates the items; it should produce an array of length n, however.

An Overall Strategy

Here’s one way you might approach this problem:

You can write these tests in TestPartitionOracle.java (yes, the tester has its own tests!). This will get you through the beginning of the problem, and familiar with all the major interfaces. With this in hand, you can proceed with more refined tests. Here are some ideas:

Overall, your goal is to make it so findCounterExample will return null for any reasonable good partition implementation, and find a CounterExample for any bad partition implementation with extremely high probability. We will provide you with a bunch of them to test against while the assignment is out, and we may test on more than we provide you in the initial autograder.

We won’t test on truly crazy situations, like a partitioner that only fails when passed lists of 322 elements, or when a one of the strings in the array is "Henry". The bad implementations will involve things logically related to sorting and manipulating lists, like boundary cases, duplicates, ordering, length, base cases, and comparisons, as a few examples.

What to do about null?

Assume that there are no null items in the arrays, that sorts won’t putnull items in the arrays, and that the variables holding lists of items won’t contain null. There are plenty of interesting behavior to consider without it!

Don’t have your implementation of findCounterExample take more than a few seconds per sorting implementation. You don’t need to create million element lists to find the issues, and it will just slow down grading. You should focus on generating (many, maybe hundreds or thousands of) small interesting lists rather than a few big ones, which should process very quickly.

Part II: Implementing Different Partitions

When you’re learning, it’s useful to write implementations yourself to gain experience. Your task now will be to write three partition methods that differ in the way they choose the initial pivot value. There are many different way to choose the pivot value, but the two we ask you to implement are listed below. You are welcome to search for solutions on the internet to solve this portion of the PA. Include a link to wherever you found an internet solution if you do use a solution from the interent.

Put these implementations in the corresponding files:

All these files should contain classes that implement the Partitioner interface, which means that the partition method you are expected to implement should follow the method signature provided in that interface. Both implementations will return the final pivot position and maintain the correct behavior where all values that are less than the pivot should be stored before it and all values greater than the pivot should be store after it. One way to check whether your implementations are correct is to use findCounterExample from part I to determine if a counterexample can be generated for your partition, provided that your code from part I is correct and thorough. If a counterexample is generated that means that there is likely an error and you can use that to debug your program.

Part III: Copying Code from the Internet

There’s a lot of code out there in the world. Much of it is available, with permissive licensing, for free on the Web. When you’re learning, it’s often useful to write implementations yourself to gain experience. However, there are also skills related to finding and re-using code, rather than writing your own from scratch. These skills are useful to develop, and come with their own set of best practices.

When you re-use or repurpose code, there are two main concerns:

For this assignment, you must go find a single partition implementation in Java on the Web. You should document the source you got it from clearly, and adapt it to fit the Partitioner interface that partitions Strings. For each implementation you find, you write in a header comment with the method:

Put the implementation you adapt in the provided file WebPartitioner.java.

A search engine is your friend here. Searching “Java partition implementation” or “Java quicksort implementation” is a fine way to start. Searching “java partition implementation site:github.com” gives a bunch of promising options, as well. Have fun searching, there’s lots of cool stuff out there!

NOTE: This part of the assignment comes with a deliberate, narrow exception to the Academic Integrity policy for the course. You shouldn’t, in any other assignment (or other parts of this assignment) go hunting for code on the Web that solves the assignment for you. You certainly shouldn’t do it in other classes or at your job unless you know it’s acceptable to do so – you should always know and consult the policies relevant to your current context. We (the instructors) know how to search for code on the Web. So do intellectual property attorneys, to extend the analogy to the professional context.

Asking for Help

The coding task for this assignment is to implement and test findCounterExample along with the two partition methods. You are free to go to help hours for assistance, but be aware that tutors may not be able to directly answer your questions or debug your program.

Answers to FAQ

Style

The style guidelines are the same as PA3, with the following additions:

The remark about redundant inline commenting from PA3 is still a recommendation, not something we will enforce.

Submission

On the Gradescope assignment Programming Assignment 5 - code please submit the following files:

You may encounter errors if you submit extra files or directories. You may submit as many times as you like till the deadline.

Scoring (40 points total)