Proof by induction

Recommended Week

Year 1 : Weeks 5 - 10

Originators

Raphael Clifford, Nigel Smart

Aim

To show the application of proof by induction in computer science (this is importany as Jonathan Lawry identified proving as the topic in the Discrete Math unit, that Computer Science students find most difficult).

Task

This task is based on the example described on page 17 of the book "Introduction to Algorithms" (available in Queens Library under QA 9.58 COR).

Using the proof by induction show that the insertion sort, given by the following pseudocode, correctly sorts an array:

insertion_sort (A)
{
    for j = 2 to length(A)
    {
	key = A[j];
	i = j-1;
	while i > 0 and A[i] > key
	{
	    A[i+1] = A[i];
	    i = i-1;
	}
	A[i+1] = key;
    }
}

Version with answer (available for CS staff only)