What Is An Algorithm?
The term algorithm sounds like it's complicated, scary and unapproachable.
To some, "algorithm" sounds like a term for conjuring magic, much like alchemy.
The beauty of the term algorithm is that it's actually really simple: It's just a set of instructions.
An algorithm is a set of step-by-step instructions (called a procedure) to solve a particular problem.
I'll explain an algorithm by using one of my favorite examples that I use every day: Making my morning cup of coffee.
Algorithm for Making a Pour-Over Coffee
- Go to the kitchen.
- Get the kettle from the kettle base.
- Go to the sink.
- Hold the kettle under the faucet.
- Fill the kettle with water to the "Max" line.
- Go to the kettle base.
- Set the kettle on the kettle base.
- Turn on the kettle base to heat water.
- Get a bag of beans.
- Open the bag of beans.
- Pour beans into measuring cup.
- Get the grinder.
- Verify cup for grinds is under the grinding mechanism.
- Plug the grinder into the outlet.
- Pour beans into the grinder.
- Turn on grinder.
- Get the coffee carafe.
- Get the pour-over dripper.
- Get a pour-over filter.
- Put the pour-over filter in the dripper.
- Wait for kettle to reach 193 F.
- Take kettle off base.
- Take kettle and pour-over dripper to sink.
- Pour water for 2 seconds into dripper over sink in circular motion.
- Go back to carafe.
- Put dripper ontop of carafe.
- Pour grinds into dripper.
- Pour water into dripper for around 3 seconds until grinds bloom.
- Wait 30 seconds for bloom.
- Pour water into dripper for 45 seconds.
- Take dripper off of carafe.
- Grab a coffee mug.
- Pour coffee from carafe into coffee mug.
You may not think of this as an algorithm, but it is!
That's a LOT of instructions, but it's simple in that it is an algorithm — a set of step-by-step instructions to solve a problem.
Thanks to algorithms, I enjoy a perfect cup of coffee every morning.
Key Ingredients to An Algorithm
The key ingredients to an algorithm, what's required for an algorithm to exist are:
- Clearly Defined Inputs: An algorithm must have zero or more well-defined inputs. These are the data that your algorithm will process.
- Clearly Defined Outputs: An algorithm should have one or more well-defined outputs. This is the result of your algorithm after processing the input data.
- Definiteness: Each step in an algorithm must be clear and unambiguous. There should be no confusion about what the step does. It's the difference between "cook until done" and "bake at 350 degrees for 20 minutes".
- Finiteness: The algorithm must always terminate after a finite number of steps. An algorithm can't go on forever.
- Effectiveness: Every step of the algorithm must be sufficiently basic that it can in principle be done exactly and in a finite amount of time.
- Generality: The algorithm should be applicable to a set of inputs and not just a single, specific case.
Types of Algorithms
There are a growing number of types of algorithms.
- Search Algorithms: These are algorithms designed to locate a specific item or set of items within a larger structure. Google's search algorithm is a famous example.
- Sort Algorithms: These algorithms are used to arrange data in a certain order. Examples include quicksort, mergesort, and bubblesort.
- Graph Algorithms: These are used for computing the shortest path in a graph, spanning trees, checking graph connectivity and so on. Dijkstra's and Prim's are notable ones here.
- Dynamic Programming Algorithms: These solve a complex problem by breaking it down into simpler subproblems in a recursive manner. An example is the Knapsack problem.
- Greedy Algorithms: These make the locally optimal choice at each stage with the hope of finding the global optimum. The activity selection problem is a classic case of a greedy algorithm.
- Divide and Conquer Algorithms: These break a problem into distinct subproblems of the same type. The merge sort and quicksort algorithms are examples of this approach.
- Brute Force Algorithms: These are the simplest algorithms, attempting to solve a problem through all possible solutions. Examples include simple linear search or the traveling salesman problem solved by checking all possible routes.
- Recursive Algorithms: These algorithms solve problems by dividing them into smaller, identical problems until they reach a simple case that can be solved directly. The Fibonacci series calculation is a classic example.
- Backtracking Algorithms: Backtracking is a type of algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, by incrementally building candidates to the solutions, and abandoning a candidate as soon as it is determined that the candidate cannot possibly be extended to a valid solution. The classic example is the Eight Queens Puzzle.
- Randomized Algorithms: These use a random number at least once during the computation to make decisions. Quicksort using a random pivot is an example.
- Parallel Algorithms: These algorithms divide a problem into smaller subproblems and solve them concurrently (at the same time). An example would be matrix multiplication using parallel computing.
- Heuristic Algorithms: These are rule-of-thumb algorithms that help in making decisions when perfect logic or optimal solutions are not possible. They are commonly used in machine learning and artificial intelligence. Genetic algorithms and A* search are good examples.
- Online Algorithms: These algorithms process their inputs in a serial fashion, i.e., piece-by-piece in an online manner, without having the entire input available from the start. For example, internet packet routing.
It's important that I point out that I don't know all of these types of algorithms. This post was a result of me thinking about algorithms and doing research on algorithms to learn. As I explore these types of algorithms, I'll write more about them, but I want to be clear that I couldn't enumerate them all from memory as of writing!
Algorithms are amazing. They're a simple idea that have wide reaching applications. From coffee, to driving, to getting ready for the day, to sorting and processing data, algorithms are deeply entrenched in our lives.
I think it's a great idea to take some time through your day to ask "what algorithms" do you notice?
The next time you sit down for work, the next time you go to a coffee shop and order a cup of coffee, the next time you decide to go for a bike ride. Notice the sequence of steps you take to perform a task.
Doing so gives you a better understanding of how to think about algorithms.
Doing an exercise like this is also a great way to experience wonder at how our brains create their own algorithms without us explicitly telling them to!