Keeping it Small and Simple

2007.05.20

Understanding algorithms for novice programmers

Filed under: Algorithms, Computer Programming — Lorenzo E. Danielsson @ 19:12

Q: what two tools are essential for a novice programmer trying to understand how algorithms work?
A: pen and paper.

I think that one of the major hurdles for novice programmers comes when they have managed to grasp the syntax of a programming language and move on to actually trying to do something with the language. That is when the concept of algorithms comes in. The first step for the programmer is to learn about existing algorithms and to try to understand them. Already here many people start to find difficulties.

In the old days, when much of the world was ruled by the Emperor of Rome and I was learning how to program, we were encouraged to always work through algorithms on a piece of paper. Going through the algorithm step by step really helps in understanding what the code does. So my usual advice to new programmers is this: always work through parts of the code that you don’t understand on paper. If you still don’t understand the code, go through it again, and again, until you understand exactly what is happening.

Very few people seem to listen to this advice (I guess it is more fun to write code, even if you are just copying it off a web site). The people who don’t often come back to me later to tell me that they find programming difficult. Well, if you want learn how to swim, you really have to jump into the water. If somebody tells you this, and you don’t listen, can you then blame the water for the fact that you cannot swim?

Let’s look at a simple example: bubble sort. It is not the best of sorting routines, but it is, or at least was, the first sorting algorithm that most people learn. It’s also trivial so it makes a good example. Below is a simple implementation of bubble sort, written in C (the language is unimportant, I could have given the example in Pascal and the principle would still have been the same).

 1 #include <stdio.h>
 2 
 3 #define ARRAYLEN 10
 4 
 5 int main(int argc, char **argv)
 6 {
 7     int nums[] = { 7, 2, 6, 10, 1, 9, 5, 8, 4, 3 };
 8     int i, j, tmp;
 9 
10     for (i = 0; i < ARRAYLEN-1; ++i) {
11         for (j = i+1; j < ARRAYLEN; ++j) {
12             if (nums[i] > nums[j]) {
13                 tmp = nums[i];
14                 nums[i] = nums[j];
15                 nums[j] = tmp;
16             }
17         }
18     }
19 
20     for (i = 0; i < ARRAYLEN; ++i)
21         printf("%dn", nums[i]);
22 
23     return 0;
24 }

Anybody who has even the slightest programming experience should be able to follow what the code does, from a syntactical point of view. But let’s try to understand what the code does, that is, what results are produced. So go and grab a notebook and a pen.

The lines 10-18 are where the integers are sorted. This is the part of the code that we need to analyze. First of all, draw a small table, two rows and ten columns. You will draw this again, several times. In the first row you write down the index values of the array. That would be 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. In the second row you fill in the number that occupies each array element at the start of the program. Now you have your start condition.

During the course of the program the integers in the array will be thrown around until finally they are sorted from the lowest number to the highest. Now you want to understand why that happens. We can see that we have an iterator, i, that loops through the values 0 to the second-to-last element of the array. On your paper, jot down that i is 0 (zero).

Next we have an inner loop where the iterator j loops through the values i+1 up to the last element of the array. On your piece of paper, write down that j is 1.

The next code block compares the value held in nums[i] with that of nums[j]. In the first iteration of both loops, that means we are comparing the value of nums[0] with that of nums[1] (look at your paper and you should see i = 0, j = 1 there). The values of these are 7 for nums[0] and 2 for nums[1]. Since 7 is larger than 2 the if statement evaluates to true and its code block is executed.

What happens in the code block is that two variables, nums[0] and nums[1] exchange values. In order to do that we proceed as follows: 1. copy the value of nums[0] to a temporary variable, 2. copy the value of nums[1] to nums[0], 3. copy the old value of nums[0] to nums[1]. In step 2 we overwrite the value of nums[0], that is why we need to store it away to a temporary variable.

What has happened is the first two array elements have swapped values. So draw the array table once more. This time array element 0 should hold the number 2, and array element 1 should hold the number 7.

The next thing that will happen is that j will be incremented by 1 (i will only be incremented once the inner loop completes). Check if the control condition is still true. It is. The value of j is now 2, and the control condition states that the loop should continue as long as j is less than ten.

The value of nums[0] (which is now 2) will now be compared to that of nums[2] (6). This time, 2 is less than 6, so the if statement evaluates to false. We increase j by one and check if the loop condition is true. The program continues like this until j has reached 10. Then the inner loop completes.

If you have been following along with your pen and paper through all the steps of your inner loop, then your last array table should contain the number 1 in array position 0. What that means is that after one iteration of the outer loop, the first array position contains the lowest value in the array.

Now it is time to increment i by 1. On your paper you write down that i is now 1. Next we start a new cycle of the inner loop, so you write down j = 2 (i+1) on your paper. For each iteration of the inner loop, we again go through the comparison and swap values if the condition nums[i] > nums[j] is true. If you look at your array table after the second iteration of the outer loop, the first two array elements should contain 1 and 2.

By the time you have gone through the last iteration of the outer loop you will hopefully have gained a good understanding of how the bubble sort algorithm works. Writing it is trivial, copying it from somebody else even more so. But in order to be a programmer you don't need to just be able to type code and get it to run, you need to understand it as well.

Stepping through code in this way also gives you the opportunity to test a few "what ifs". Suppose, for example, you didn't understand why the start value of j should be i+1 and not i. Well, then you could test it. By writing down all the values and comparisons that are done step-by-step you will soon see that that would introduce a redundant comparison when a value is compared with itself.

You may notice that it takes quite a bit of time to analyze a piece of code in this way. But it's well worth it, especially when you apply the principle to more complex algorithms where it is not so apparent what the code does. And remember, in order to learn programming (or any other skill for that matter), you must be ready to sacrifice some time and effort.

Advertisements

4 Comments »

  1. To really program is not the language syntax, all is about thinking the algorithm for solving the problem at hand. Knowing syntax of a language yes, really helps in so many ways but the heart of programming is the ability to write down the algorithm for solving a particular problem.

    So my little advice to novice programmers is, spend much time on writting algorithms than trying to grasp a programming language syntax, syntax is easy to learn and for that matter, don’t waist time on it.

    Comment by eyedol — 2007.05.22 @ 00:12

  2. Just as Lorenzo said, the first and probably must important tools for programming is a book and pen. The thing about algorithms is that they can be some times tricky in understanding. Variables are not spat onto the screen but are manipulated in the computer. It then becomes useful if you the one trying to unravel the wisdom in an algorithm, write the code down and go through it by hand. It really does help.

    The theme for the blog is OK but i have a little issue with the font size(a bit too small). If possible a bit larger or appropiate font will do just fine.

    Comment by bbaka — 2007.12.13 @ 15:42

  3. I guess it hits the spot to say that programming is about understanding the essence rather than look at things syntactically. Algorithm is the very foundation a language can be built on and it starts with a pen and paper. Wish this page had more examples, maybe a bit more complex. But its good work. Thanks!!

    Comment by Shashank — 2008.02.21 @ 09:06

  4. @Shashank: I wrote this post because of a specific problem I had been thinking about. In my experience, programming students have no problems picking up the absolute basics of a language.

    But when they get to the point where they have to start using programming to solve problems they get stuck. Many inexperienced programmers when faced with a piece of code don’t know where to even begin analyzing it, panic and assume that it’s impossible to understand. This is post is then an attempt to present a simple method for how to build an understanding of an algorithm.

    Granted the “algorithm” presented was over-simplistic, but it really needed to be. If you are interested in more on algorithms, I will try to put a few more posts together.

    Comment by Lorenzo E. Danielsson — 2008.02.21 @ 09:21


RSS feed for comments on this post. TrackBack URI

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

Blog at WordPress.com.