Discussion 3: Loop Invariants

Download Starter Code download

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

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool, meaning 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 entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that 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 critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!
Exercise 1: Second Largest Element
Given an int[] array, we'd like to determine its second-largest element. To avoid having to worry about various edge cases or ambiguities, we'll assume that the array contains at least two elements and that all of its elements are distinct. Therefore, a second-largest element must exist. 
1
2
3
4
5

/** 
 * Returns the second-largest element of the given `nums` array.
 * Requires that `nums.length >= 2` and `nums` contains distinct elements.
 */
static int secondLargest(int[] nums) { ... }
1
2
3
4
5

/** 
 * Returns the second-largest element of the given `nums` array.
 * Requires that `nums.length >= 2` and `nums` contains distinct elements.
 */
static int secondLargest(int[] nums) { ... }
We'd like our definition of secondLargest() to use only a single pass over the nums array; we can accomplish this by designing a loop invariant that keeps track of the relevant state as we traverse the array.
(a)
Let’s start by considering what variables we will need to keep track of our progress as we traverse over the array. As usual, we’ll use a variable i to keep track of our position in the array. What other local variables should we introduce?
(b)
Finish filling in the following array diagrams, incorporating your local variables from part (a).
(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)
Using the “Post” diagram, what should be our loop guard? When we exit from the loop, what will our return value be?
(e)
Open up the starter code and set up your loop in the secondLargest() method using your answers to parts (c) and (d). Add a comment above the loop documenting the loop invariant. Then, fill in the loop body.
(f)
Describe how the loop body maintains the loop invariant and makes progress in each iteration.
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 i, what other variables will you need to keep track of our progress as we traverse over 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. You may wish to draw two “Post” diagrams for different possible conditions: reaching the end of the array and certifying that it is a mountain vs. 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)
Open up the starter code and set up your loop in the isMountain() method using your answers to parts (c) and (d). Add a comment above the loop documenting the loop invariant. Then, fill in the loop body.
(f)
Describe how the loop body maintains the loop invariant and makes progress in each iteration.
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 write the initialization 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 set up a while-loop with the correct loop guard.
(c)
Add a multi-line comment documenting the loop invariant above your loop. Use array notation in your documentation.
(d)
Complete the body of your while-loop which should read the value of nums[i] and take different actions whether it is less than, equal to, or greater than the pivot to make progress and restore the loop invariant.