CSE 12 Programming Assignment 4

Runtime, Measured and Modeled

This assignment is open to collaboration.

This assignment will give you experience working with big-Ο/θ/Ω representations, practice matching them to implementations and perform measurements of the runtime of different methods.

This assignment is inspired by a combination of a lab in Swarthmore College’s CS35, and by a similar assignment by Marina Langlois in CSE12 at UCSD

This PA is due on ** Wednesday, July 24 at 11pm **

Part 1: Runtime Analysis Questions

Big-O Justification

Indicate whether the following assertions are true or false, and give a justification:

If you are justifying the positive direction, give choices of n0 and C. For big-Θ, make sure to justify both big-O and big-Ω, or big-O in both directions.

If you are justifying the negative direction, indicate which term(s) can’t work because one is guaranteed to grow faster or slower than the other.

As a quick guide, here is an ordering of functions from slowest-growing (indeed, the first two shrink as n increases) to fastest-growing that you might find helpful:

This portion will be submitted via Gradescope. It can be found in the Programming Assignment 4 - questions assignment (this is question 1).

List Analysis

Consider the two files ArrayStringList.java and LinkedStringList.java, which are included in this repository. Answer the following questions, and justify them with one or two sentences each:

In all cases, give answers in terms of the current size of the list, and assume that the list has some non-empty size n. That is, you shouldn’t consider the empty list as a best case; instead think about the best case based on other factors like size, capacity, and nodes.

Notable points to consider:

Example for get in the LinkedStringList class:

The get method is O(1) in the best case when the index is 0. In this case,
it will do constant work checking the index and immediately return the
first element, never entering the while loop.

The get method is O(n) in the worst case, because the index could be at
the end of the list (for example, index n - 1). In this case, the while
loop will run n times, spending constant time on each iteration, resulting
in an overall O(n) number of steps taken.

This portion will be submitted via Gradescope. It can be found in the Programming Assignment 4 - questions assignment (this is question 2). Make sure to follow the formatting instructions!

Part 2 (Sorting): A Bad (and Good) Implementation Detector

In this part of the assignment, you will:

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

The starter code for part 2 can be found at: https://github.com/ucsd-cse12-ss24/cse12-pa4-pt2-Partition.

Testing with Properties

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

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

This process works well for writing a small or medium number of targeted tests for particularly interesting cases. However, checking specific output values isn’t necessarily the best way to test an implementation. In fact, sometimes this process won’t work at all.

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

interface Partitioner {
 /* Change strs between start (inclusive) and end (exclusive), such that
  * 1) all values at indices lower than a pivot index are smaller than or equal
  * to the value at the pivot, and 2) 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 class, we learned that there are many ways to implement partition, and that the choice of the pivot index is very important. Not only could we choose different pivots, but you could choose a random pivot!

Imagine you’re 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 such as using special matchers.

Then, instead of writing out all the tests by hand, we should step back from the problem.
We care that the array is correctly partitioned. In other words, there shouldn’t be 1) elements larger than the pivot value at earlier indices, or 2) elements smaller than the pivot value at later indices.
There are other properties, too, such as 3) 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!).

Therefore, 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 For Part 2

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

CounterExample findCounterExample(Partitioner p);

CounterExample is an object 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);

Where generateInput() creates a list of items to use as input to purported partition algorithms. It’s up to you how it generates the items so long it produces an array of length n.

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:

TL;DR: Overall, your goal is to make it so that findCounterExample() returns null for any reasonable good partition implementation, and 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.

Note: We won’t test on truly crazy situations, like a partitioner that only fails when passed lists of 322 elements, or when 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?

You can Assume that:

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.

On this PA, we will not give deductions for violating standard style guidelines (but you should still follow them):

Submission

Part 1

You may submit as many times as you like till the deadline.

Part 2

On the Gradescope assignment Programming Assignment 4 - 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.

Grade Breakdown

Note that this assignment has a lot of manual grading, so there’s less value in submitting after the deadline.

Part 1 (28 points total)

Part 2 (26 points total)