Steve Vickers: Introduction to Computer Science

Fundamentals of Computing: Introduction to Computer Science

Assessed coursework 2: solutions

See further down for feedback on general performance on coursework.

For convenience I'll number the different conditions in the invariant. For establishing or reestablishing the invariant, we need to check all the conditions. 

        /* invariant
1        * start <= l <= r <= end
         * In region for indexes i with start <= i < end:
2        *   elements are as originally, but rearranged.
3        *   if i < l then arr[i] < x
4        *   if i >= r then arr[i] >= x
5        * Elements outside region are unchanged.
         */

1. A suitable loop test is l < r.

2. For the result, we do return l;.

Then the returned result a (name used in question) == l by definition.
Looping has finished, so loop test is false: l >= r.
Invariant (1): l <= r.
Combining these, l == r, so a equals both l and r.

Hence from invariant (3,4): within the region we have -
small elements with indexes from start to a-1,
big elements with indexes from a to end-1.

This is what was required for the answer.

Invariant (1) tells us start <= a <= end and (2, 5) tells us that on return the array has elements unchanged outside the region, and the same but possibly rearranged inside.

3. For the initialization, do

    int l = start;
    int r = end;

Invariant (1): using precondition ("requires"), we get
start <= start <= end < end.

Invariant (3,4): There are no elements with indexes in the range start to l-1, so trivially they are all small. Similarly, the elements with indexes in the range r to end-1 are trivially all big.

Invariant (2,5): No elements have been changed yet.

4. The loop body is as follows.

            if (arr[l] < x){
                l = l+1;
            } else {
                int y = arr[l];
                arr[l] = arr[r-1];
                arr[r-1] = y;
                r = r-1;
            }

5. There is at least one element in the grey area, and arr[l] is the first.

Invariant (3): If arr[l] is small, it is already in the right place. After l = l+1;, the elements with indexes from start to l-1 (which used to be l) are all small: they are the ones we already knew were small from the invariant, and the new one we have found. If arr[l] is big, then the invariant condition remains true because no variables have changed that could affect it.

Invariant (4): If arr[l] is small then again nothing has happened to affect the truth of this invariant condition. If arr[l] is big, then we swap it with arr[r-1], the last in the grey area. Then in we do r = r-1; and the reasoning is similar to the above.

Invariant (1): Since we started the iteration with l < r, and then either added 1 to l or subtracted 1 from r, we have l <= r afterwards. The rest is obvious.

Invariant (2,5): The only change we ever make to the elements is to swap two in the region, so that is just a further rearrangement.

6. On each iteration the size of the grey area, which is r-l, decreases by 1: either l increases by 1 or r decreases. This is enough to ensure progress is made.

7. Combining the "requires" condition, the invariant and the loop test we see that 0 <= start <= l < r <= end <= arr.length. It follows that 0 <= l < arr.length, so we don't get an exception from arr[l]. Also 0 <= r-1 < arr.length, so we don't get an exception from arr[r-1].

Assessed coursework 2: feedback

Mark levels

  • If your code was perfect but you didn't understand invariants, then you would get 1+1+2+4+0+0+0 = 8 marks.
  • Between 9 and 12 marks would usually mean you understood invariants a little but not much.
  • Less than 8 usually meant you got the code wrong.

That's about in line with exam grades, where the pass is 50% (12 marks here) and 40% (9.5 here) is the minimum you must get in every module: a comfortable pass corresponds here to a reasonable understanding of invariants. (Remember that the 50% pass level in a masters degree corresponds to some technical competence.)

Over two thirds of you did not reach even the 50% on first attempt, and around two fifths on the second. Are you still under 12 marks? Look very hard about your learning strategy. How you are trying to understand invariants? Just guessing at the answers, and hoping that eventually you will get them right, is not enough.

Invariants are not that difficult, but require clear thinking - they are all about how to think clearly about what your program does. Without that ability you will not be able to write good code (or get a Birmingham MSc).

The Java code

Make sure the code matches the invariant! If it doesn't, you will lose marks in part 4, for not doing what the question asks. You will also lose lots of marks in parts 3 and 5. If in reality your code doesn't establish or reestablish the invariant then how can you explain why it does?

You also lose marks if your code doesn't behave exactly as the question asked. In particular, in the loop body you should check the "first grey element", and either leave it where it is (if it is small) or swap it up to where the big elements are (if it is big). Then adjust the variables.

Do not put extra loops inside the main loop. Many of you tried this, incrementing l past as many small elements as possible (which is pointless, because the main loop does that anyway) and then decrementing r past as many big elements as possible (which arguably has some purpose in avoiding unnecessary swaps).

The invariant

This is what the exercise was about. You have to look at what the invariant says, and answer questions about it. Otherwise you just don't get the marks.

I hope it wasn't too confusing how I talked about ranges of indexes.
In the invariant: line 3 says that elements with indexes in the range start to l-1 are all small, line 4 is similar for the range r to end-1.
In the specification (Javadoc): if we let a stand for the result returned by the method, then elements with indexes in the range start to a-1 are all small, and those with indexes in the range a to end-1 are all big.
Note that a range can be empty, if it is from a bigger number to a smaller number.

When you explain how the invariant is "established" or "reestablished" by some Java code, you are explaining why the invariant is true after that code is executed. Remember to say something about all five parts of the invariant.

You also need to know how to use the invariant by assuming it is true before some code is executed. This is where the invariant becomes your friend, and is key to answering questions 2, 5 and 7.