Steve Vickers: Introduction to Computer Science

Fundamentals of Computing: Introduction to Computer Science

Assessed coursework 2

This coursework is assessed for MSc students and counts for 5% of the module total. You should deliver your answers to the box outside School reception by 12.00 midday on Monday 3rd December 2012.

Intercalated year (ICY) students are advised to do the exercise as unassessed coursework, because it gives some preparation for the exam. If you would like me to mark your work to give feedback, post it in the same box as the MSc students, but please write "ICY" clearly at the top.

The exercise concerns a Java method to rearrange the elements of a region of an array of integers so that the small elements are in the left hand part of the region, and the large in the right hand part. Every element outside the region is left unmoved. Here is the Javadoc.

    /**
     * Partition a region of an array.
     * Rearranges elements in region so that small ones
     *   all have smaller indexes than the big ones.
     * Elements outside the region are unchanged.
     * requires: 0 <= start <= end <= arr.length
     * @param arr   array to partition
     * @param start start of region (inclusive)
     * @param end   end of region (exclusive)
     * @param x     pivot - "small" and "big" are <x, >=x.
     * @return      start index (inclusive) of big elements
     *              in region after partition.
     */
    private static int partition(
        int[] arr, int start, int end, int x
    ){

The region under consideration is the part of the array with indexes in the range start to end-1.

On return, if a is the result, then the small elements (< x) have been rearranged so they have indexes in the range start to a-1 and the big elements have indexes in the range a to end-1.

The plan is to have two local variables l and r and a while-loop using the following invariant. 

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

Thus the invariant says that (within the region) elements on the left are small and on the right are big, but in between there is a grey area with indexes in range l to r-1.

1. (1 mark) What is a suitable loop test?

2. (4 marks) When looping finishes, what is the correct value to return? Explain how the invariant shows that it is the correct answer.

3. (4 marks) What is the correct initialization for l and r? Explain how that establishes the invariant.

4. (4 marks) Write Java code for the body of the while-loop. It should look at the first grey element and then either leave it where it is if it is small, or swap it to just before the big elements if it is big. Then adjust the variables.

5. (6 marks) Explain how your loop body reestablishes the invariant.

6. (2 marks) Explain how your loop body makes progress.

7. (3 marks) Why does the loop body never throw an ArrayIndexOutOfBoundsException?

There are some explanations and diagrams in the slides for week 10.