Removing the Magic Veil of Algorithms

A quick guide to understanding algorithms

The word “algorithm” is a word that gets thrown around quite a lot in media. After all, Google uses an algorithm… and Twitter, and Tinder, and Instagram, and Medium, and on and on and on. In movies and TV, algorithms are only created by the super genius that either wants to end the world, or save it. It can feel a little daunting.

But what if I told you that an algorithm doesn’t have to be as complicated as you think it is. In fact, you probably use an algorithm — in some form or another — in your every day life?

Abra…

An algorithm is, quite simply, a list of instructions to be used to achieve a desired result. Think about it this way: have you ever cooked or baked while using a recipe? Or assembled a piece of furniture from IKEA with the instructions? That recipe and instructions, were actually algorithms.

… kedabra!

And like that, the veil is gone. Yes, it really is that simple.

Types of Algorithms

When it comes to computer algorithms, we can categorize them into 6 different types:

1. Recursive Algorithms
2. Divide and Conquer Algorithms
3. Dynamic Programming Algorithms
4. Greedy Algorithms
5. Brute Force Algorithms
6. Backtracking Algorithms

Let’s take a closer look at each of them:

Recursive Algorithms

In a nutshell, a recursive algorithm is one that calls on itself directly or indirectly. For example, a factorial function:

function factorial(n) {
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n ‑ 1);
   }
}

We’ve seen another example of this in our loops!

let i = 0; i < a.length; i++

Look familiar? This calls on itself after each iteration until the conditions are met.

Divide and Conquer Algorithms

This Machiavellian approach is already being used all over your code and you probably didn’t even know it. A great example of a divide and conquer function is JavaScript’s .sort()

const array = [5,3,1,2,4]
array.sort();
console.log(array);
// [1,2,3,4,5]

The way this works is by dividing the array — starting with 5 and 3 — asking, is 5 greater than, less than, or equal to 3? And moving the 5 according to the answer. It divides the array into smaller parts and then puts the solved smaller parts back together.

Dynamic Programming Algorithms

Dynamic programming is a technique that breaks the problems into smaller problems, and saves the result for future purposes. The perfect example of this is the fibonacci sequence.

function fibonacci(num) {  
   if (num <= 1) return 1;   
   
   return fibonacci(num - 1) + fibonacci(num - 2);
}
// => 2,3,5,8,13,21...

Doesn’t this look a little familiar? It does! That’s because this function is also recursive! Dynamic programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using dynamic programming.

Greedy Algorithms

Greedy algorithms take a problem and make locally optimal choices (the best solution at a given point) at each step with the hope of finding a global best solution. It’s yet another recursive approach to solving a problem. Take the following example, we want to get from node B to G with the least possible resistance:

As you can see from the image above, the greedy algorithm (red = 19) is not the best path available. Here, the heuristic solution (green = 18) is actually optimal. Sometimes, the greedy algorithm can even take you further away from the solution you’re looking for.

Brute Force Algorithms

Brute Force Algorithms are exactly what they sound like — straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency.

For example, imagine you forgot the PIN to your bank account. A brute force algorithm will start at the beginning and go through every possible combination until it finds the right one (0000, 0001, 0002, 0003… etc). An example in code would look like this:

function bruteForceSubstringSearch(text, pattern) {
    const lengthOfText = text.length;
    const lengthOfPattern = pattern.length;
    for (let i = 0; i < lengthOfText; i++) {
        let j;
        for (j = 0; j < lengthOfPattern; j++) {
            if (text.charAt(i + j) !== pattern.charAt(j)) {
                   break;
            }
        }
        if (j === lengthOfPattern) return i;
    }
    return lengthOfText;
}

bruteForceSubstringSearch('this is a test', 'test');

As you can see by the use of a recursive function inside a recursive function, these algorithms continue to play and build off of each other.

Backtracking Algorithms

Backtracking is a technique to find a solution to a problem in an incremental approach. It solves problems recursively by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.

For example, consider what it takes to solve a Sudoku puzzle: we try filling digits one by one, but whenever we find that current digit cannot lead to a solution, we remove it (backtrack) and try next digit.

// N is the size of the 2D matrix (N*N)
let N = 9;
function solveSuduko(grid, row, col){
    if (row == N - 1 && col == N)
       return true;
    if (col == N){
       row++;
       col = 0;
    }
    if (grid[row][col] != 0)
       return solveSuduko(grid, row, col + 1);
    for(let num = 1; num < 10; num++){
       if (isSafe(grid, row, col, num)){
         grid[row][col] = num;
         if (solveSuduko(grid, row, col + 1))
            return true;
        }
        grid[row][col] = 0;
     }
  return false;
}

I hope this brief overview gave you a good place to start for navigating those rough algorithm waters. Always remember, just like spoken language rhetoric, there is no one size fits all solution to all of the problems we will face. It’s important to use the best tools for the job at hand. Now go cast those spells you wizards!

Happy coding!