How to learn algorithms in programming

Do you want to learn algorithms in programming? Are you wondering where to start? In the next paragraph, I give you the answer.

The study of algorithms in programming has two main topics: algorithm analysis and algorithms design.  The recommended way to learn algorithms in programming is to start learning algorithm analysis. Only after that, you can spend time learning algorithm design techniques. Also, always start writing the algorithm on paper, never start straight on the computer. Let’s take a view of what contents are part of each topic.

Algorithms in programming

I am going to give you an informal and brief introduction to algorithms.

Why we write algorithms? The answer is quite simple, to solve problems. So the first thing we must have in mind when thinking about creating an algorithm is: we want to solve a problem. From now on, we must assume problem-solving thinking (or mindset).

An algorithm is a sequence of steps we (or a computer) can take to solve a problem.

The steps must have some characteristics for them to be useful in programming.

The first characteristic is that a computer must be able to execute all the steps. i.e. one of the steps cannot be, take a flight to a certain place. Also, the execution of the steps on a predefined order must always lead to a solution to the problem.

You must be aware that a problem can have many solutions, all of them right. That is why we usually state that the algorithm finds a solution to the problem. In some cases, we will be able to say that the algorithm finds an optimum solution to the problem, but that has to be proved (usually using maths).

The second characteristic is that the computer can execute all the steps in a finite amount of time. It won’t be a good algorithm if we have to wait forever for a result.

Find below an example of an algorithm that you must be using daily.

In the morning, I wake up at 6:00, exercise at home, take a shower, brush my teeth, dress up and go to school. The problem that you solve here is that you have to go to school every day. There are other routines to follow (algorithms) to be able to go every day to school, but this one is the one you use.

From the programming perspective, it is very similar. Let’s say you have to add two numbers and show the result, you first get the numbers, then you add them and finally, you show the result.

Algorithms are the fundamentals of programming. If you want to learn programming you have to start learning about algorithms.

Algorithm analysis

There are two objectives of algorithm analysis.

The first one is to calculate the amount of time the algorithm will take to give the result, called time complexity.

The second one is to calculate the amount of memory the algorithm will take to give the result, called spatial complexity.

The time complexity is very easy to understand, not so easy to calculate in all cases. Here, you just have to calculate how many operations the computer has to execute to give a solution.

At this moment you can say, but to count is very easy, I know how to count. While I’m teaching Discrete Mathematics to my students, one of the topics is Counting. I always ask my student do you know how to count? The answer is always yes, but there is a lot about counting that they don’t know.

To count the number of operations the computer have to do to execute an algorithm, you will have to use some math. It is not that basic but it is easy to understand. I’m not going to explain it in this post because is out of scope, but if you are interested leave a comment and will get in touch with you. If you want to go straight for more information on the topic, you can search for the Big-O notation.

In the second case, you will have to calculate how much memory the computer will use to execute the algorithm. In this case, the approach is somehow similar. Every variable that you use in your code needs a specific amount of space. All you have to do is to find your variable types, calculate the amount of memory for each one and add them up.

Why we do algorithm analysis?

As I mentioned before, several algorithms can solve the same problem. Therefore, we use algorithm analysis to determine which algorithm is the best for our specific situation.

Usually, there is no one single algorithm that is the best in all cases. If we have to choose one among several, we have to do the analysis.

Some (but not all) questions that you have to answer are:

• Do I have a time constrain to get the solution? i.e. the algorithm is for an ambulance driver to find the quickest way to the hospital because the passenger is a patient with a heart attack.
• Can I forget about the space needed to execute the algorithm?
• Do I have limited hardware resources to execute the algorithm? i.e. the algorithm is designed for an embedded system.

The answer to those questions, and some more, lay in algorithm analysis. Which is basically to calculate time and spatial complexity.

Algorithm design

After you learn how to analyse algorithms, it is time to start learning how to design some of your own.

When we learn programming, a very important technique to learn is recursion. Although it can be explained very quickly and easy, it is quite difficult to understand. This one is a very important technique and there are a lot of examples of applications.

Although it is recommended to avoid recursion because is computationally expensive (regarding the amount of memory), it is very much used in several algorithms.

The second algorithm design technique I recommend you to learn is Divide and Conquer. You probably used many times and maybe you use it daily.

The technique is very simple, take a problem, divide it into problems of smaller size and then combine the solutions to the smaller problems.

Let’s see how this technique works by applying to a specific problem.

Our problem is to design an algorithm to order (ascending) 20 numbers. If we apply divide and conquer, we can divide the original problem into 2 problems. Each of the two problems will be to order 10 numbers. Once we solve the two problems we can easily combine the two solutions as follows (remember we have two sets of 10 numbers each one, and the two of them are in order):

• Get the smaller number from each set and add it to a new set.
• Repeat until the two sets that represent the smaller problems are empty.

The third technique I recommend you is dynamic programming. Sometimes some algorithms calculate the same value several times. The dynamic programming technique address this issue. The goal is to make sure that the algorithm does each calculation only one time.

A typical problem that this technique solve is to calculate the Fibonacci number. This number is calculated as follows:

Fib(0) = 0, Fib(1) = 1

Fib(n) = Fib (n-1) + Fib(n-2)

If you calculate Fib(5) = Fib(4) + Fib(3), you have to calculate then Fib(4)=Fib(3)+Fib(2), and then you calculate the second term which is Fib(3) = Fib(2) + Fib(1).

Can you see the operations that are repeated?

A dynamic programming approach will avoid repetitions and calculate the values only once.

Greedy algorithms are another category. They are greedy because they choose at each time the best choice for a partial solution, without considering the impact of that partial solution in the global one.

This technique is useful to solve optimization problems when the known algorithms have high temporal complexity. A common way to say this is the algorithm is computationally expensive. In those cases, most of the time we have to accept a “good enough” solution because the optimum solution is too expensive.

Summary

I strongly recommend you to learn first, algorithm analysis and then you move into the design techniques.

For the algorithm design techniques, just start with the ones I mentioned above. They are the ones that are mostly used, although there are more.

When you get deeper into the study of algorithms, the new techniques will come on a needed basis.

And always start the design of the new algorithm on paper. Never start straight on the computer

If you want to start learning some basic algorithms, you can read this post.

Find bellow my favourite books to study algorithms.