A Gentle Introduction To Algorithms
Inspired by “How did we get here? The story of algorithms,” by Marek Kowalkiewicz
The first time I heard the word “algorithm” was 16 years ago, in this video on how to solve a Rubik’s Cube. Dan Brown said “you have to learn algorithms. It sounds fancy, and complicated, and nerdy, but it’s really not all that fancy. An algorithm is any sequence that, when repeated enough times, the cube returns to its original position.”
This definition is, of course, too specific, but it came out in a time when the word “algorithm” was not really in the vernacular. Today the word “algorithm” is everywhere. We have algorithmic trading. We have AI algorithms like Random Forest. We also have quite a few articles that discuss the pros and cons of the Facebook algorithm, even though the “Facebook algorithm” is actually just a colloquial term for hundreds, if not thousands, of algorithms. It’s not like there’s a secret file sitting on a Meta server somewhere called Algorithm.js, which contains all the information on how Facebook ranks, targets, and filters content.
Or…maybe there is. I don’t know, I don’t work there.
Introduction To Algorithms provides this definition:
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as an output. An algorithm is thus a sequence of computational steps that transform the input into the output.
— Source
That book, by the way, describes itself as “a gentle introduction to we how we specify algorithms.” It is 1300 pages long.
Motivation
I have never seen people so enthusiastic about AI. I went to a talk, and people seemed so enthusiastic about AI algorithms, how they worked, and what kind of results they achieved.
It got me thinking — what if all this talk of DSA, coding interviews, and whiteboarding is actually not such a bad thing? What if the ability to solve and understand the concepts behind LeetCode questions is fundamentally useful for understanding something relevant, like how to understand and use AI tools?
I write this with some hesitation, as I imagine there may be pushback. In late January of this year, Interview.io conducted an experiment in which they required candidates to cheat on mock coding interviews with ChatGPT without informing the interviewers. The results are somewhat surprising: Interviewees performed 19% better than the control group when using ChatGPT on LeetCode questions, 14% better on “modified” LeetCode questions (modified means they had a significant change, as opposed to being verbatim LeetCode questions), and, most surprising of all, not a single interviewer suspected cheating.
Algorithms are a pretty broad topic, ranging from simple, useful textbook algorithms like Binary Search to whatever evil magic YouTube is using to recommend me videos like Corgi Snow Tunnel. Understanding well-defined textbook algorithms is useful for coding interviews and may be useful to software engineers in general, as a gateway to more complex algorithms. Or not…maybe technology built on generative AI like ChatGPT will simply end these LeetCode interviews altogether.
A Very Brief History Of Algorithms
I had the pleasure of reading this Medium post on TowardsDataScience.
Marek writes:
Until recently, algorithms were a domain of computer scientists. But now, they have entered our lives and are becoming pervasive. Algorithm is not a foreign word anymore. Algorithmic trading, algorithmic bias, the Facebook algorithm, even algorithmic warfare — all these terms have become part of our vocabulary in recent years. Some people go as far as claiming that we live in a new age: the age of the algorithm. But the algorithms are not that new. We have used them, knowingly or not, for hundreds and thousands of years.
The ancient Greeks used algorithms to identify prime numbers. Euclid, who was born in 305 BC, introduced an algorithm for identifying the greatest common divisor of two numbers. Ada Lovelace was born in 1815 and wrote Note G, an algorithm for calculating Bernoulli numbers which she intended to use on a computer called the analytical engine.
Computer programming is relatively new when compared to the long history of algorithms.
An Entry Point: Binary Search
Say you are asked to guess a number between 1 and 100. Every time you do, you are told if the number is higher or lower.
An inefficient algorithm to employ is the linear search. Just guess 1. Then guess 2. Then guess 3…
A better algorithm is a binary search. Guess the middle (50). If it is higher, guess the number between 51 and 100. If it is lower, guess the number between 1 and 49.
This very question generated a lot of buzz when they featured it in HBO’s Silicon Valley.
As some point out, the example is a little strange. Still, it made for some good explanations, like what this user provided:
Imagine you have a book with 10000 pages. You want to find page 5172. You know the pages come one after another, so you can just open the book roughly in the middle, see if you are before or after page 5172 and make another educated guess until you have found it.
Richard went to the beginning of the book and started turning over pages one by one.
— Source
This is the fundamental idea of a binary search. If something is sorted, then you no longer have to search every element. It also serves as a pretty good introduction to Big O. We care a lot about upper-bounds/worst cases.
Linear search is O(N), where N is the number of elements in the list. The very worst case we can have is that we do not find the item until we have searched every single element in the list.
Binary search is O(log N). That is significantly better, especially as N increases.
I am really oversimplifying Big O, but that is because the formalized definition is confusing.
Sorting Algorithms
BaseCS is one of the best DSA resources anywhere, especially Medium.com, and it is also free of paywall blocks. I only wish she had continued to update it with more content.
A fair number of her algorithms are sorting algorithms — she covers insertion sort, quick sort, merge sort, bubble sort, and selection sort. You can see just how bad selection sort is here, with a time complexity of O(n²), but it is probably the easiest algorithm to understand. Just find the smallest item in a list using a linear (it’s not sorted, so we can’t do binary) search. When you find it, swap it with the first unsorted item. You are dividing your input into a sorted side and an unsorted side…illustrated again in BaseCS here.
This is a lot simpler, and a lot worse than a comparatively complex algorithm like merge sort of quick sort.
LeetCode is a website that does a really good job assessing for Big O. You write coding solutions, and you can pass initial test cases…but you are unlikely to pass all test cases unless you keep Big O time and space complexity in mind.
What I did above was 100% not okay, and no one would ever hire me for doing it, but I did want to illustrate how useful these pre-built functions are. std::sort, which uses the amazing algorithm called the Introsort, beats 99.94% of other C++ LeetCode users on time complexity and 100% of them on space complexity. This is probably because the vast majority of them actually solved it, instead of pulling what I just did.
Richard Hendrix also could have just used a prebuilt function, and part of the whole LeetCode interview/whiteboarding debate is that in real life we have libraries as our disposal.
A Random Tangent: HBO’s Silicon Valley
Without spoiling too much, it occurred to me that the entire plot of HBO’s Silicon Valley is built around an algorithm. The idea is that one person invents a compression algorithm, and it changes everything.
How they arrive at this algorithm is not really something I am allowed to talk about on Medium, but the logic behind it is kind of hand-waved. They include a diagram of it here, though the diagram is pretty vague. To build drama and make the plot work, Silicon Valley introduces a made-up metric called the Weissman score. In the universe of Silicon Valley, a Weissman score is a widely accepted metric for lossless compression algorithms. Characters can verify it by simply going to a website that evaluates their compression applications; characters compete to develop a platform with the best Weissman Score.
Dropbox claims to have actually invented Middle-Out. Do what you want with that information.
