Algorithmically Speaking, Of Course.

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

This post might get a bit too “Mathsy” for some

A Book To End All Books… Kinda

So, recently I’ve been reading “The Art of Computer Programming”. By that I mean:

I bought a copy of “The Art of Computer Programming Volumes 1-4 just shortly after Christmas, and I’ve been working my way through them.

I’m only 40 pages into volume 1, but when you see the size of the tomes themselves… In fact, here take a look at them

What This Has Taught Me, So Far

As I’ve said: I’m 40 pages into volume 1. So far it’s been all about the maths (pure, that is) of computation. But it also has an amazing section on Algorithm composition.

What’s An Algorithm?

In its most basic form, an algorithm is just a list of instructions. For instance, the algorithm for making a cup of coffee might be:

1. Get a cup
2. Add some freeze-dried coffee granules  to the cup
3. Boil some water
4. Add boiled water to cup with coffee granules
5. Stir the mixture a little with a spoon
6. Add milk and sugar to taste
7. If you’ve added milk and sugar, stir mixture again

See that wasn’t difficult, was it?

What I did there was took a, so called, “Real World Problem” (How do I make a cup of coffee?) and broke it down into a set of simple steps. That’s all we ever do when writing/composing an algorithm. Seriously, that’s it. One of most important parts of Computer Science is that easy (not just making coffee, but understanding algorithms, too).

Its Taught You a Bunch Of Algorithms?

Nope. It’s taught me an amazing way to compose them.

Say we have a list of things; a shopping list, for example. How do we check through the list to make sure we have all the items in our basket? You might say something like:

Look at each item in the list in turn, and check whether its in the basket. Right?

Exactly. The only problem is, this is a little vague. We have no clear start and end points. How do we know if the thing is in the basket? How about this:

1. Look at the first thing on the list
2. Search through the basket for an item that resembles the first thing
3. If you can find it, excellent. Move onto the next thing in the list
4. If you can’t, boo. We need to find the thing in the store. Make a note of this thing, and move onto the next thing in the list

We’ve got too many “things”. And it’s still to vague. Let’s remove all the vague terms and construct a simpler way of writing this algorithm. How about something like this:

Initial Setup: Set N ← 1

Beginning: Look at Nth name in the list

Can you find an object that represents the Nth name on the list?

Yes: Set N← N + 1 Go back to the beginning

No: Make a note of the name of the Nth name on the list, set N ← N + 1, go back to the beginning

In this above block of text:

• N is a number
• ← means “Set the value of the thing on the left to that of the thing on the right”

Other than that, it should be quite simple to follow. There are other constructs in Knuth’s Algorithm composition, but I wont touch on them in this example.

Real Example

This is a real “problem” that programmers must take care of in at least one program that they will write in their career (I’ll guarantee it):

Look through a list of un-ordered numbers. Find the smallest and the largest. Sum them both. Find the difference between this new number and the largest number.

This is a problem that I remember vividly from my CompSci 101 classes at University. The first thing I ever did was break it down into individual sentences – this way, you break the problem down into single steps:

• Look through a list of un-ordered numbers.

The list of number’s we’ve been given is in a random order. They are not sorted from smallest to largest, or largest to smallest.

• Find the smallest and the largest.

We need to find two numbers. One that has the smallest value in the list, and one that has the largest value in the list.

• Sum them both.

Once we’ve found both of these numbers, we’re going to add them together.

• Find the difference between sum and the largest number.

Find the difference between the sum and the largest number (subtract one from the other).

The whole point of this exercise was not to write a program that would calculate this for you, but to write an process (an algorithm) for doing this. We were graded on how easy it was to understand our process. Some of the smart-asses in the group just re-wrote the list of things to do, verbatim. The didn’t fail, but were encouraged to give it a proper try.

Here’s what I came up with:

1. Get the first number
2. Get the next number
3. Is the next number bigger than the first number?
4. If it is, then
5. ….

I’ll spare you the details, because the listing was massive – I seem to remember it being half a page of A4 (typed). There were a lot of stages where I looped back to the very beginning, and then jumped around a little. It ended up looking like spaghetti code by the end of the algorithm, and you HAD to follow along with a pen so that you could trace back to where you where.

It was terrible.

It taught me a lot of things.

I looked back at this algorithm, today. I shuddered to think that this was ever acceptable – to be fair, it was the first algorithm I’d ever written, and I was young a stupid.

I re-wrote the algorithm. Here it is:

• Initial Setup: Set N ← 1, M ← 2, Smallest ← 1, Biggest ← 1, Sum ← 0, Difference ← 0
• Beginning: Is N > M?
• Yes: Set Biggest ← N, Smallest ← M
• No: Set N ← N + 1, Set M ← M + 1, Go back to Beginning
• Set Sum ← Smallest + Biggest
• Set Difference ← Sum – Biggest

That’s it. Six lines instead of half a page of A4.

Why Algorithms And Note Code?

Let me put it this way: I can think of 5 different ways to implement this in code, off the top of my head. And that’s just in one language.

In C# (pronounced: “SEE SHARP”) you could do something like this:

And that’s not doing it the optimised way.

If we leave the a solution to a problem as an algorithm, that solution is easily implemented in all the different programming languages, in all the difference programming styles, by all the different programmers.

I think I’ll leave it there, for now. Mainly because there are far better resources out there (on The Internet [search for “beginning algorithms”] or in hundreds of books).

So, until next time: Stay frosty, people

J