Discussion 3: Loop Invariants

The goal of today’s discussion is to practice writing “loopy” code using the tools from last Thursday’s lecture: array diagrams and loop invariants. Becoming more comfortable with these tools will help you design loops in a more principled way that lets you get the code right on the first try, saving debugging time. In addition, we’ll continue to use the language of loop invariants throughout the course as we discuss more complicated methods. During this discussion, you’ll develop three different “loopy” methods from their specifications.

Learning Outcomes

  1. Describe the loop invariant of an iterative method involving an array and visualize it using a diagram.
  2. Use an array diagram to develop an iterative method.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool; it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based on your attendance, active participation, and completion of that day’s activity. More information about the grading and expectations can be found in the syllabus.

Since discussion activities are not graded for correctness, we do not restrict what resources you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from thinking critically to “puzzle” them out.

Exercise 1: Warmup
Suppose that we have a double[] array of sensor measurements. We expect all of the readings to be non-negative; however, occasionally the sensor will record a spurious negative value. To "clean" the data, we'd like to "clip" these negative values, replacing them with 0. For example, the array
would become
We'll define a method cleanData() to carry out this operation. 
1
2

/** Reassigns all negative entries of the `readings` array to 0. */
static void cleanData(double[] readings) { ... }
1
2

/** Reassigns all negative entries of the `readings` array to 0. */
static void cleanData(double[] readings) { ... }
(a)

Throughout the method, we’ll use the loop variable i to keep track of the index of the next array entry that we will inspect. Let’s suppose that we want to carry out the cleaning from right to left.

How should we initialize i?

What should our loop guard be to ensure that we exit the loop immediately after inspecting all of the array entries?

(b)
Finish filling in the following array diagrams for the loop in cleanData().
(c)

Use your answers from parts (a) and (b) to write the definition of the cleanData() method.

Add a comment above the loop documenting the loop invariant. Then, fill in the loop body.

Exercise 2: Mountain Detection
We say that an array of ints is a mountain if its entries (weakly) increase to the array's maximum value and then (weakly) decrease after this. More concretely, an array int[] nums is a mountain if there is some index i with 0 <= i < nums.length for which nums[..i] is a non-decreasing sequence and nums[i..] is a non-increasing sequence. For example,
meets these criteria when i = 3. However,
is not a mountain because it has two "peaks"; its entries increase, then decrease, then increase again. We'll develop a method isMountain() that determines whether a given int[] array is a mountain. 
1
2
3
4
5
6

/**
 * Returns whether the entries of `nums` form a *mountain*, meaning there 
 * is some index `i` such that `nums[..i]` is non-decreasing and 
 * `nums[i..]` is non-increasing. Requires that `nums.length > 0`.
 */
static boolean isMountain(int[] nums) { ... }
1
2
3
4
5
6

/**
 * Returns whether the entries of `nums` form a *mountain*, meaning there 
 * is some index `i` such that `nums[..i]` is non-decreasing and 
 * `nums[i..]` is non-increasing. Requires that `nums.length > 0`.
 */
static boolean isMountain(int[] nums) { ... }
(a)

In addition to a loop index variable j, what other variables will you need to keep track of our progress as we traverse the array? (Hint: Our solution uses one additional boolean variable).

(b)
Draw “Pre”, “Post”, and “Inv” array diagrams to visualize the behavior of your loop. Include two “Post” diagrams to account for two possible return conditions: reaching the end of the array and certifying that it is a mountain, versus detecting that the array is not a mountain and returning early.





(c)

Using the “Pre” diagram, how should we initialize the loop variables? Briefly explain why your initialization makes the loop invariant true at the start of the loop.

(d)

What should be our loop guard? When we exit from the loop, what will our return value be?

(e)

Use your answers from parts (c) and (d) to set up your loop in the isMountain() method. Add a comment above the loop documenting the loop invariant. Then, fill in the loop body.

Exercise 3: Pivot Partitioning
When we partition an array, we split its entries into disjoint pieces according to some property. In this case, we'll partition an array of ints into three segments by comparing them to a pivot, another special int value. We'll move all the entries that are less than the pivot to the beginning of the array, followed by all the entries that are equal to the pivot, followed by all the entries that are greater than the pivot. Soon in lecture, we'll see that this type of pivot partitioning forms the basis for the Quicksort sorting algorithm.
1
2
3
4
5
6

/**
 * Rearranges the elements of `nums` about the given `pivot` so that 
 * `nums[..i) < pivot`, `nums[i..j) == pivot` and `nums[j..] > pivot` 
 * for some indices `i,j`. Requires that `nums.length > 0`.
 */
static void partition3Way(int[] nums, int pivot) { ... }

1
2
3
4
5
6

/**
 * Rearranges the elements of `nums` about the given `pivot` so that 
 * `nums[..i) < pivot`, `nums[i..j) == pivot` and `nums[j..] > pivot` 
 * for some indices `i,j`. Requires that `nums.length > 0`.
 */
static void partition3Way(int[] nums, int pivot) { ... }
You'll develop a method that uses three int loop variables (i, j, and k) and the following loop invariant:
(a)
Adjust the “Inv” array diagram back in time to draw the “Pre” array diagram. Use this to determine the correct initializations of the loop variables i, j, and k.
(b)
Adjust the “Inv” array diagram forward in time to draw the “Post” array diagram. Use this to determine the condition we should use to guard our loop.
(c)

Within the while loop of the partition3Way() method, we’ll start by reading the value of nums[i]. For each of the following cases, describe what must be done in the loop body to make progress and restore the loop invariant.

nums[i] < pivot:

nums[i] == pivot:

nums[i] > pivot:

(d)

Use your answers from parts (a), (b), and (c) to write the definition of the partition3Way() method. Be sure to document your loop invariant (using proper range notation) in a multi-line comment above the loop declaration.

Exercise 4: Code your Implementations
Download Starter Code download
Download this starter code and fill in the method bodies that you developed in today's discussion. You can use the provided unit tests to check your correctness.

Submission

At the end of class, your group’s primary author should create a PDF with your written answers to Exercises 1-3 and upload this to the “Discussion 3” Gradescope assignment, tagging all other members of the group onto the submission. If you need any help with this process, be sure to call over the TA. This is the same process that you’ll be using to submit your homework assignments.