Crash Course on Algorithms
The word Algorithm is thrown around a lot these days, and for a good reason. They are the foundational building blocks of AI (artificial intelligence) and much of the technology we use every day.
But most people think of it as an abstract, intimidating word that should be a question on Jeopardy (what is an algorithm, Alex?). In truth, algorithms are not only at the core of today’s digital society but also deeply rooted in human culture and psyche. We’ve used algorithms as long as we’ve been able to record history. The first recorded use of algorithms was by the Sumerian civilization four thousand years ago, just about the same time that humans invented written language. We’ve been using them since day one.
What is an Algorithm?
An Algorithm is a finite series of steps that you use to solve a problem or reach a goal. We use forms of algorithms all the time, both consciously and unconsciously.
An important distinction is that an algorithm must be precise. A simple example of an algorithm is a recipe. But as anyone who cooks knows, not all recipes are technically algorithms because many aren’t precise in their instructions. Everyone has seen the recipe on the back of the box that says “cook on high for 25-30 minutes, or until done”. That leaves a lot to interpretation, and that’s something important that a good algorithm does not do.
Algorithms are sequences of precise instructions that produce the same result every time
Exact recipes, aka algorithms, will allow you to cook your favorite meal or bake your famous brownie the same way every time.
Take a second think about how often you’ve used algorithms throughout your life. Since they’re simply a set of instructions to get the desired result, many examples should come to mind. Following the installation manual to put together a piece of furniture or hang your TV on the wall is an example. So is doing laundry. And, if you’ve ever gone to a painting class or watched Bob Ross and his fantastic afro on The Joy of Painting, then you were watching an algorithm at work.
Algorithms are everywhere in today’s world. Some are obvious, while others run without our ever noticing. They schedule flights, route packages for your late-night Amazon purchases, establish real estate comps, and decide what content you’ll see on Facebook.
They help us solve problems, make better decisions, predict likely outcomes, and enhance our daily lives. On the aggregate, we use them to be more productive and happier. They can regulate your thermostat to keep you comfortable while also reducing your energy bill.
Hopefully, if we’ve done our job, you’re on board with the idea that algorithms should be neither scary nor intimidating. Humans create algorithms by default in the form of routines. These ‘intuitive algorithms’ aren’t always precise, but we use them to help reduce uncertainty to make the best decision we can at that moment. An example would be using a list of pros and cons to help you make a tough decision. These are by nature subjective and lack the sophistication and precision of mathematical algorithms used by computers, but in the end, they’re trying to do the same thing.
Take your morning routine as an example. You’ve devised and refined a unique process to make you as efficient as possible while doing what you need to do to get ready for the day. The same is true when you get in your car. There are specific steps you follow to unlock, start, and drive the vehicle.
But how do they work?
The Building Blocks: Inputs and Outputs
Inputs and outputs are the core of any algorithm. Outputs are typically more familiar to us. These include the recommendations you receive on Amazon based on your purchases, or the suggestions Facebook keeps giving for people you may know based on your friends. Algorithms are designed to take information as an input, then perform a task to produce an output. When you put your address in Waze and ask it to tell you the best route home, the output is the route and directions.
But by default outputs can only be produced through inputs, which all algorithms have. These can be a single number or two, but more and more they are complex considerations taken from many sources. Inputs should consider any variable that might be used to solve your specific problem.
When you search for the cheapest flight from airport A to airport B leaving between 2:00-4:00 pm EST on a specific date, you can see many of the inputs involved in determining the output…the flight that best meets your criteria. But these algorithms leverage many other inputs, including a database of all flights incoming and outgoing, the companies providing the services, their routing, weather conditions, etc.
If you take a package to the post office to send out, it’s an algorithm that is deciphering the hand-written zip code on the slip. Specifically, this is a machine learning algorithm that takes countless examples of handwriting with a known output to help it learn what was right from wrong.
Machine Learning Algorithms
We talked about machine learning (ML) in our last crash course series and some of the types of algorithms we interact with. Now let’s go a little deeper into how to develop these types of algorithms by talking about grouping.
According to DLabs, ML algorithms are usually grouped by either learning style or similarities in form and function such as classification, regression, decision trees, etc. The learning styles could include supervised, unsupervised, or semi-supervised, but regardless of the style or the function, all machine learning algorithms contain three components:
- Representation — aims to choose a model and data input which are understandable by the computer.
- Evaluation — aims to select metrics that would validate the model both internally and externally.
- Optimization — aims to find the best settings for the model so that it can produce the most significant output.
Other (but not all) Types of Algorithms
- Dynamic Programming Algorithm: used for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions using a memory-based data structure (i.e., an array or map). Each of the sub-problem solutions is indexed in some way, typically based on the values of its input parameters so that it can be looked up. The next time the same sub-problem occurs, it just looks up the previously computed solution instead of recomputing its solution, thereby saving computation time. This indexing procedure is called memorization.
Example: 1+1+1+1+1+1+1+1 = 8. What happens if we add another 1 to this? We don’t need to recount from the beginning to know this additional 1 will add up to 9. We know how the solution was solved before and therefore can jump to the answer without taking the (computational) time to start over.
- Brute Force Algorithm: a type of algorithm that tries a large number of patterns to solve a problem. Sometimes they are extremely simple and rely on raw computing power to achieve results. A typical example of a brute force algorithm is a security threat that attempts to guess a password using known common passwords. The algorithm might also try dictionary words or even every combination of ASCII strings (American Standard Code for Information Exchange) of a certain length. This algorithm does not include any shortcuts to improve performance, just raw computing to try all possibilities until it finds the solution to the problem.
- Backtracking Algorithm: a technique for incrementally solving problems by trying to build a solution, one piece at a time. Backtracking approaches solving an overall issue by finding a solution to the first sub-problem, then recursively attempting to solve the next sub-problem based on the resolution of the previous issue. If the next sub-problem cannot be resolved, the step is backtracked by removing the previous solution, then applying the next possible solution to the earlier steps and proceeds from there. It continues to eliminate the candidates that fail to satisfy the constraints of the problem at any point in time, ending when all possible solutions to the first sub-problem have been exhausted. This technique searches every possible combination to solve a computational problem. Usually, this algorithm gets outshined by other algorithms like dynamic programming, linear and linear-logarithmic time complexity in order of input size. Backtracking algorithms are generally exponential in both time and space. For example, say you have three boxes and have to find the coin in one of the boxes. You check one by one and discard any that don’t have the coin. Backtracking is solving all sub-problems one by one to reach the best possible solution. Another example is a sudoku problem. You fit a number in the box, and if it doesn’t fit it is removed (backtrack) and try the next digit.
- Divide and Conquer Algorithm: an algorithm that divides the given problem instance into sub-problems, conquers the sub-problems by solving them recursively and combines the solutions from the sub-problems to find a solution for the original problem. For example, when finding a number in an array, the algorithm breaks the array into smaller groups and then performs a binary search for the said number, then combining the results. Binary search is a searching algorithm where, in each step, the algorithm compares the desired element to the middle element. If it matches then it returns the value, if not, it and the x value is lower then the search moves to the left of the middle, if higher it moves to the right.
- Greedy Algorithm: this technique makes the choice that seems to be the best at that moment. This process means that it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. For example, if you need to maximize or minimize an objective function, the greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision. Most greedy algorithms do not produce an optimal solution.
Algorithms are not incomprehensible things that only exist to help mathematicians and computers. We use them every day, even if we’re unaware of it. Algorithms contain a lot of problem-solving wisdom that can help you make the right decisions, predict probable outcomes, and become a more productive individual.