Algorithms Notes – Chapter 1

Algorithm Billboards

What  is an algorithm? The textbook Introduction to Algorithms 3rd Edition by Cormen et. al defines an algorithm thus:

an algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

Wikipedia defines algorithms in the following way:

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

I personally, adhere to the definition on a couple of Ask.com billboards that was temporarily endorsed by XKCD. Repeat after me:

We did not invent the algorithm. The algorithm consistently finds Jesus. The algorithm killed Jeeves. The algorithm is banned in China. The algorithm is from Jersey. The algorithm constantly finds Jesus. This is not the algorithm. This is close.

Onto the actual stuff.

Loop Invariance

A property that satisfies the following conditions:

  1. Initialization. It is true before the start of the loop.
  2. Maintenance. If it is true before an iteration of the loop then it mus remain true before the next iteration.
  3. Termination. When the loop terminates, it must give a useful property that helps prove the correctness of the algorithm.

Note: Loop invariance is kind of like mathematical induction. Initialization is similar to the basis step in a proof by induction, and maintenance is similar to the inductive step. One key difference is the fact that in a proof by induction, the inductive step is true for all values till infinity i.e it does not terminate. In a loop invariant statement, on the other hand, there is termination after a finite number of steps.

Insertion Sort

Input: A sequence of n numbers <a_{1}, a_{2}, ... , a_{n}>

Output: A permutation <a'_{1}, a'_{2}, ... , a'_{n}> of the input sequence such that a'_{1} \leq a'_{2} \leq ... \leq a'_{n}.

Algorithm:


Insertion-Sort(A)
    for j = 2 to A.length
        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

Here’s a nice little GIF demonstrating how insertion sort works, courtesy wikipedia:

insertion-sort-example-300px

Loop Invariance for Insertion Sort:

At the start of each iteration of the for loop of lines 2-8, the subarray A[1 … j-1] consists of the elements originally in A[1 … j-1], but in sorted order.

Let’s see how this statement holds for the above mentioned conditions required for loop invariance.

Initialization – At the start of the first loop, the variable j = 2, hence the subarray A[1 … j – 1] evaluates to A[1]. Since this only contains one element (the first element), it is sorted (this is the trivial case. One element is always sorted). Also, this is the original element. Hence the statement holds.

Maintenance – We won’t tackle this formally yet. Wait a while. You can see from the GIF that this is intuitively true though. At every successive iteration, the subarray moves one element right and since the element is sorted into the correct place in the sub-array without changing the value of any other element, the loop invariant statement about the subarray consisting of its original elements but in sorted order remains true.

Termination – Notice that the loop terminates when j > A.length. Since A had n elements, the value of j will be $latexn+1$ at the time of termination of the loop. It follows that the subarray A[1 .. j-1] will be A[1 .. n i.e the entire array. By the loop invariant statement, $A$ contains its original elements but in sorted order. Since $A$ at termination is the entire array, the entire array contains its original elements and is sorted at the end of an insertion sort. This proves the correctness of the insertion sort algorithm.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s