T-Th 9:05
or
T-Th 11:15
in Olin 155

CS 1110: Introduction to Computing Using Python

Fall 2012

Loops and Invariants

There is a PDF version of these instructions, if you would prefer to have that instead.

The purpose of this lab is to give you practice with developing loops from invariants. It also introduces some of the important seqeunce algorithms that you should know for the final exam. On the final, you would be expected to write (a variation of) one of the following: binary search, Dutch National Flag, partition, selection sort, and insertion sort.

Requirements For This Lab

There is no code to turn in for this lab. The purpose of this lab is to design loop algorithms, and you are to write the algorithms that you design (together with the diagrams for your pre and postconditions) on this sheet of paper. When you are done, you should show your instructor the contents of the sheet. If you finish the first three exercises, the instructor will mark you down has having completed the assignment.

If you do not finish that much, you should the first three exercises by the beginning of the next lab, which is after Thanksgiving. You should show them to your instructor at that time. In any case, you should try to do all the exercises (including the remaining two) because that will help you understand and gain skill in solving such problems.

Note in our sample answers, that we do not draw all the pictures that are required. If an invariant is not drawn as a picture, you should draw it as a picture before continuing to work on the problem. If you need help, you should ask your TA or consultant.

You do not need to implement these algorithms. However, if you wish to test your programs in Python, you are welcome to do so. In this case, you may find it useful to print out the contents of the list after each time that you complete the algorithm.

If you get stuck, do not waste time. Ask the TA or consultant for help.

Algorithm Shortcuts

In writing your algorithms in the space below, we want the algorithms to be as close to Python as possible, and not high-level "pseudo-code". However, if you want to swap two elements of an list, you are permitted to write 

   swap b[i] and b[j];
instead of the the three assignments that perform the swap.

Exercise 1: Warm-Up Exercises

Counting the values in b[x..y-1]

You are to give a formula (in Python code) for the number of values in the segment b[x..y-1], which you should write in the box below:







If you do not know what the formula is, first try to figure it our by looking at segments of size 1 and 2. Otherwise, ask you instructor and then memorize it. That formula is a useful tool. Knowing it will help you develop loops that deal with ranges of integers.

Drawing Array Diagrams

Draw an list b that satisfies these conditions 

   b[0..i] >= 5, b[i+1..j] = 5, b[j+1..] <= 5








Exercise 2: Finding the Minimum of the List

The following are assertions for an algorithm to find the minimum of an list b[h..k]:
Precondition: h <= k < len(b)
Postcondition: b[x] is the minimum of b[h..k]
We represent these assertions as the following pictures (you may either use the text version or the pictures in your algoritms).

Given these assertions, we present four different loop invariants below. You are to write a loop (with initialization) for each one.

Invariant P1

Written in text form, this invariant is as follows:
invariant: b[x] is the minimum of b[h..t]
Pictorially, we represent it as follows:

Write your loop for this invariant in the space below:























Invariant P2

Written in text form, this invariant is as follows:
invariant: b[x] is the minimum of b[h..s-1]
Pictorially, we represent it as follows:

Write your loop for this invariant in the space below:























Invariant P3

Written in text form, this invariant is as follows:
invariant: b[x] is the minimum of b[r..k]
Pictorially, we represent it as follows:

Write your loop for this invariant in the space below:























Invariant P4

Written in text form, this invariant is as follows:
invariant: b[x] is the minimum of b[w+1..k]
Pictorially, we represent it as follows:

Write your loop for this invariant in the space below:























Exercise 3: Partitioning on a Fixed Value

The purpose of the algorithms in this question is to swap the values of list b and to store a value in k so that the postcondition given below is true. Array b is not necessarily sorted initially. The precondition and postcondition are as follows:
Precondition: b[0..] = ? (i.e. nothing is known about the values in b)
Postcondition: b[0..k] ≤ 6 and b[k+1..] > 6

Below are three different invariants. You should write a loop (with initialization) for each one. You are also to draw pictorial representation of the invariant in each case.

Invariant P1

Written in text form, this invariant is as follows:

P1: b[0..h] < 6 and b[k+1..] > 6
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P2

Written in text form, this invariant is as follows:

P2: b[0..k] < 6 and b[t..] > 6
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P3

Written in text form, this invariant is as follows:

P3: b[0..s-1] < 6 and b[k+1..] > 6
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Exercise 4: General Partitioning Algorithm

This question is a generalization of the previous one. Again b is not necessarily sorted initially. Develop the partition algorithm (which uses only swap operations) to meet the assertions below:

Precondition: b[h] = x for some x and h ≤ k < len(b)
                      (this is just so we can talk about b[h] initially; x is not a program variable.)
Postcondition: b[h..j-1] ≤ x = b[j] ≤ b[j+1..k]
Below are three different invariants. You should write a loop (with initialization) for each one. You are also to draw pictorial representation of the invariant in each case.

Invariant P1

Written in text form, this invariant is as follows:

P1: b[h..j-1] ≤ x = b[j] ≤ b[t..k]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P2

Written in text form, this invariant is as follows:

P2: b[h..j-1] ≤ x = b[j] ≤ b[q+1..k]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P3

Written in text form, this invariant is as follows:

P3: b[h..j-1] ≤ x = b[j] ≤ b[j+1..n-1]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Exercise 5: Selection Sort

The last exercise is to write a selection sort, which sorts the contents of the list b. The postcondition for this problem is straightforward:

Postcondition: b[0..len(b)–1 is sorted (in ascending order)
We have provided several invariants for you below. Before you do each one, write the invariant as a picture. Then write the statement(s) you use to maintain the invariant in the repetend in English. You should state what it is you want to do, not how to do it. In particular, we do not want to see a nested loop (e.g. a loop within the repetend of your first loop). Instead, you should use one of the two methods you wrote above as a helper method.

Invariant P1

Written in text form, this invariant is as follows:

P1: b[0..k–1] is sorted and b[0..k–1] ≤ b[k..]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P2

Written in text form, this invariant is as follows:

P2: b[0..h] is sorted and b[0..h] ≤ b[h+1..]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below:























Invariant P3

Written in text form, this invariant is as follows:

P3: b[s+1..len(b)-1] is sorted and b[0..s] ≤ b[s+1..]
Draw the pictorial representation of this invariant below







Write your loop for this invariant in the space below: