Improving Algorithmic Thinking in 10 minutes

Professor Thomas Cormen posted an answer to the following question on the social media site quora.com: "What can I learn right now in just 10 minutes that could improve my algorithmic thinking?" His answer has received over a thousand "upvotes" and has since been featured on Forbes.com. And so, what can one learn in 10 minutes to improve one's algorithmic thinking? Answer by Thomas Cormen:

It's pretty hard to answer that question without knowing what you already know.  If I had to give just one thing, that thing would be loop invariants.  Understand that when you write a loop, you either implicitly or explicitly use a loop invariant.

A loop invariant is a predicate (a statement that is either true or false) with the following properties:

1. It is true upon entering the loop the first time.
2. If it is true upon starting an iteration of the loop, it remains true upon starting the next iteration.
3. The loop terminates, and the loop invariant plus the reason that the loop terminates gives you the property that you want.

Let's take a really simple example.  Consider this loop to sum the first n elements of an array a, where n is a positive integer:

sum = 0
i = 0
while i < n
    sum = sum + a[i]
    i = i + 1

Here's the loop invariant: Upon entering an iteration of the loop, sum = a[0] + a[1] + a[2] + ... + a[i-1].  Now let's see how the three properties hold for this loop invariant.

1. Upon entering the first iteration, i = 0.  The sum a[0] + ... + a[i-1] is empty, since i-1 = -1.  The sum of no terms is the identity 0 for addition.  Check.
2. Upon entering an iteration for a value of i, suppose that the loop invariant is true, so that sum = a[0] + a[1] + a[2] + ... + a[i-1].  The iteration adds a[i] into sum and then increments i, so that the loop invariant holds entering the next iteration.  Check.
3. The loop terminates once i = n.  According to the loop invariant, sum = a[0] + a[1] + a[2] + ... + a[n-1].  Check: sum is indeed the sum of the first n elements of the array.

Now, this example is pretty trivial.  If you were writing this loop, I doubt that you'd formally reason about it in this way.  But this reasoning is exactly what was in the back of your mind, whether or not you realized it.  Loop invariants help you understand and prove correct more complicated loops.

If loop invariants remind you of mathematical induction, they should.  The first property maps to the basis of the induction, and the second property is like the inductive hypothesis.  It's the third property that's a bit different, since most inductive proofs don't have a termination condition.

Anyway, you asked for something that you could learn in just 10 minutes.  That's about the best thing I can think of that you can learn in 10 minutes.  I might have said recursion, but in my 23 years of experience in teaching recursion in our introductory course, it takes more than 10 minutes.