An exam question on loop invariants

I don’t have a lot of time to muse tonight, so I’m posting a bit of writing I did for another purpose. I’ve added an introduction.

This semester, we decided to add some program verification topics to CSC 301, Algorithm Analysis. That meant that when I was putting together the latest take-home examination, I needed to come up with a good loop invariant problem [1,2]. We’ve already done two forms of binary search, insertion and selection sort [3], and the legendary Dutch National Flag problem. If I were sensible, I would have remembered that I’d probably written similar questions when I taught loop invariants in other courses [4].

But I’m not sensible. So I decided to write something new. It’s preregistration time. And I’m filling a bit silly. So I took one of the traditional loop invariant problems and rewrote it as a course selection problem. Here goes.

Professor R and their advisee are working on preregistration. While they’ve agreed on the first three courses (one CS, one foreign language, and one studio art), they are debating what the student should take for the fourth course. It could be an humanities course or it could be be a social science course. They’ve made a list of possible courses. They decide to repeatedly apply the following process for narrowing down the list of courses.

• Randomly pick two courses from the list.
• If the two courses are in the same division, that’s a sign that that division dominates too much. Get rid of both courses. But to make sure that we still have a reasonable selection, add a new humanities course to the list. (You can assume that there are arbitrarily many new humanities courses to add.)
• If the two courses are in different divisions, keep the social science course and drop the humanities course. (Dropping the humanities course in this case conceptually offsets the addition of the humanities course in the prior case.)

I didn’t say that it was a sensible approach. Just that it was an approach. Still, my advisees may be familiar with it [5].

1. Prove that the process terminates with only one course.

2. Write a loop invariant that provides useful information about the state of the system.

3. Using that invariant, determine the division of the final course based on the number of initial courses in each division.

No, that’s not really how I advise. I do have many students who have identified a wide variety of classes they’d like to take, and we do have to narrow them down, but we do so in a more sensible manner. And we don’t pit divisions against each other.

Still, I thought it was a fun way to phrase the problem. Upon reflection, I may have been wrong.

Perhaps I’ll post a solution after the students turn in the exam.

[1] I suppose I could have come up with another program verification problem. But I like loop invariants.

[2] An explanation of loop invariants is beyond the scope of this musing.

[3] Informally.

[4] The old CSC 201, which I taught as CSC 195 in the distant past, or CSC 207.

[5] No, not really.

Version 1.0 of 2017-11-08.