Algorithms. When you think of algorithms and people who know them, you might think of sentient computers that can predict the future that only the geniuses of the world, the Will Huntings, can understand. Viewing algorithms this way is common among new learners, and it can be intimidating.

In reality, "algorithms" are not the mystery that the media, movies, and self-absorbed engineers might like them to be viewed as.

A simple test: can you add, subtract, multiply, and divide? If so, congratulations! You are among the elite society of people who know algorithms.

If you can explain to someone how to multiply two numbers, starting at the lowest digit, "carrying the one" to the next place, and continuing until you have your result, there isn't much in your way to understanding more complex algorithms like graph traversal!

What is an Algorithm?

An algorithm can be defined as a set of rules and instructions that yield a result. In computer science, those rules and instructions come in the form of logical and arithmetic expressions.

Types of Algorithms

Most algorithms that are used in computer science fall under a few algorithm "templates". While not a complete set of every type of algorithm that will ever exist, these have been used time and time again as great starting points when approaching new problems. These types of algorithms include:

  • Brute Force
  • Divide and Conquer
  • Dynamic Programming
  • Greedy
  • Backtracking

Brute Force Algorithms

If you've ever forgotten your phone pass-code, you might have at least once considered starting at 0000 and working your way up to test all the pass-codes. A brute force algorithm does this to test all possible combinations in hopes of finding a solution.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_Intro_01.png" alt="brute-forcing a passcode" style="width:600px;max-width:95%;"> </div>

Another example of this is a brute force chess playing AI; it might test all possible moves, or maybe only a certain number before deducing the best possible move to make. This can also be solved using a greedy algorithm, and made more efficient using heuristics, but more on this later!

Divide and Conquer Algorithms

"Split up and search for clues, then meet back here" is a classic line that helps solve mysteries, and also captures the essence of divide and conquer algorithms.

A divide and conquer algorithm fulfills three concepts:

  1. Divide the problem into sub-problems (split up)
  2. Solve each sub-problem recursively (search for clues)
  3. Combine the final results of each of the sub-problems (meet back here)

> Sorting algorithms are one of the most popular applications of the divide and conquer approach.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_Intro_02.png" alt="splitting big problems into smaller problems." style="width:600px;max-width:95%;"> </div>

There is a subset of divide and conquer called decrease and conquer. The vital difference between divide and decrease is that, instead of solving each sub problem, it might only solve one or a few of the sub problems. The most popular application of this kind of algorithm is binary search.

Because divide and conquer algorithms use make use of recursion, they have a theorem associated with them called the Master Theorem, that makes solving recurrence relations simple, but more on that in another discussion.

Dynamic Programming Algorithms

Dynamic programming algorithms are similar to divide and conquer problems in that they solve a problem by breaking them into sub problems, except with one difference that can sometimes make them much more efficient. The key difference is that these algorithms use previous knowledge about a problem to solve the next step in the problem faster.

A popular example with dynamic programming is the Fibonacci sequence where the result n is found by adding the last two results of the sequence, like so:

<div style="width:100%;text-align:center;font-style:italic;font-size:120%;">f(n) = f(n-1) + f(n-2)</div> This algorithm takes an exponentially increasing amount of time to complete using divide and conquer, taking years to compute the 100th number in the sequence, even on the fastest computers!

The solution to this recursive problem is to start at the first two numbers in the sequence (0 and 1), and store the solution somewhere. Once we have that solution, we can quickly get the next number in the sequence, then store it again. Using this approach, what once took years to compute can be done in a fraction of a second!

Greedy Algorithms

Greedy algorithms are designed to find the locally optimum solution of a problem in hopes that it is also a globally optimum solution. In simpler terms; a greedy algorithm will pick the best choice in a given situation, in hopes that it will end up with the best possible result.

An example of this is the Travelling Salesman problem and the Knapsack problem. While these problems do not always come up with the most efficient solution, they are able to find the solution to non-trivial problems nonetheless. Greedy algorithms are "greedy" because they always choose the most advantageous next step. In a GPS application, it could be finding the fastest road from where the user currently is.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Alg_Intro_03.png" alt="greedy shortest-path decision" style="width:600px;max-width:95%;"> </div>

Backtracking Algorithms

Backtracking algorithms attempt to find all possible solutions to a problem by building up a list of candidate solutions and backtracking - or removing - a possible solution that can be determined to not be correct.

Good examples of this kind of algorithm at work are in solving sudoku puzzles. Additionally, backtracking is sometimes preferred over brute force as it has the ability to remove many useless candidates that the brute force method would attempt anyways.

Heuristics and AI

At this point, you might be thinking to yourself "so, what about algorithms for AI?" While there are many specific algorithms that can be used in AI and fall under one of the classifications above, AI, and Machine Learning in general tend to lean more heavily on heuristics to increase speed.

A heuristic is an approach to solving problems that doesn't guarantee a correct solution, but can reach a conclusion faster than a typical algorithm by using good rules of thumb.

Touching on the chess example above, it might be able to throw out a good number of moves if those moves can be labeled as poor choices; this way, the process will reach a "good enough" conclusion much faster. The key difference here, is that the solution will not always be the best solution; in specific edge cases you may see it pick the wrong choice in an attempt to cut corners and lose the match.

While this may lead you to think what good use this has if it can't always get the right solution, there are many real-world problems where an optimal solution isn't always a practical, or even a possible, request; using heuristics can help guide us to a viable solution in places where either no algorithm exists, or existing algorithms take exponential time or resources to compute.

How to Evaluate An Algorithm

Algorithms must come from somewhere, so it would help too have a defined process of how to come up with an algorithm. There are a series of steps and questions that can be addressed that facilitate the creation of an algorithm, transforming it from a problem to a solution.

1. Consider the problem

Is the problem intuitively taking shape of a graph problem? A sorting problem? Asking these questions can help narrow down the type of algorithm that is needed to solve the problem. You might be able to use popular algorithm frameworks to solve it with minor modifications!

2. Model the problem

Sometimes a word problem can be difficult to translate directly into computer code or even a written idea of a solution. That is why it is important to model the problem in a way that can be visually represented. After all, it is much easier to solve a maze when you can see it in front of you.

An example can be trying to find the shortest distance from point A to point B on a map. Drawing out a map and modeling possible solutions can give valuable insights towards constructing an algorithm.

3. Consider the class of the problem

The P vs NP (P = NP) problem is one of the biggest unsolved mysteries of modern computer science. It poses a question: does every problem that has a quickly verifiable solution also have a quickly solvable algorithm? If the problem you're attempting to solve falls under the category of NP problems, you might be venturing into uncharted territory while designing the solution.

Problems such as the Travelling Salesman problem fall under this category; a solution can be found given enough time, however it cannot be found quickly.

> Greedy algorithms tend to be a default plan of attack against these problems, especially in graph algorithms!

Optimal Algorithms

A final consideration when designing an algorithm is to ask if the optimal solution to the problem already exists. An optimal algorithm is one that, when shown mathematically, solves a problem in the most efficient manner possible, at least in Big-O notation*. For example, the optimal solution to finding the smallest number in a randomized list is to look at every number. Unless you have additional knowledge of the list that would say otherwise, it is impossible to know for certain without looking at every number.

> *There are some algorithms considered to be optimal under Big-O notation, yet they are not actually the fastest known way to solve that problem (Merge Sort vs. Quicksort. vs. Timsort).

A Closing Note

If you are up for a challenge, be the first to prove <a href="https://www.claymath.org/millennium-problems/p-vs-np-problem" target="_blank" style="color:inherit">P vs NP</a> and you will win a $1,000,000 prize from the Clay Mathematics Institute, and maybe even a Nobel prize or two. There is a chance you might also unintentionally prove that modern encryption techniques can be quickly solved, bringing the digital world to its knees.. but hey, you win some and you lose some!

Further Resources