Actual Algorithms (Are Fun)

As a computer scientist, I get pretty annoyed with the constant cultural usage of the term algorithm. There seems to be an unwritten rule that whenever a technical concept is brought into the mainstream cultural discussion, it will be bastardized into the void away from its original meaning. Nowadays it’s used to denote “that internet code.” People talk about the YouTube algorithms, the Facebook algorithm, the Google algorithm, the Amazon algorithms, the Twitter trending algorithm.

I hate these people. Ha, I try not to hate the people, just the behavior. Yet that is certainly one of my pet peeves – people using technical words without conveying what the words actually mean, commonly because they themselves don’t actually know. Poor usage spreads and the word loses meaning. To contrast, you can check wikipedia on algorithms. It’s dry reading and believe me, that’s a feature and not a bug.

To those who are always talking about “the algorithms”, kindly be a little more wary. Most of your online experience nowadays is governed by machine learning statistical engines with very big tables and very fancy heuristics, but it’s really arcane and not very algorithm-y, which is near the root of many of the controversies. For instance, a trainable neural network that you can teach to recognize written numbers is easy enough to do but no expert doing it knows how, and it only works most of the time. If we did, we’d have much cooler algorithms. We don’t, so Google uses their I’m-not-a-robot CAPTCHA to force you to help them train their bots by labeling crosswalks and stop signs. Algorithms are an actual thing, not fancy models that work most of the time.

Precise definitions of the word algorithm can convey to someone educated on relevant subjects a whole rainbow of ideas, thoughts, and worlds. The word algorithm should be like the word library, a word that can connote the Dewey Decimal System, that crazy lady you feared when your books were overdue in school, or rows and rows of books above your head, and that lovely smell of old books – there really is nothing quite like it. Algorithms, similarly, should connote to people titans of technology, pioneers like Turing or Knuth, magical answers to age-old problems, famous puzzles and thought experiments, and math tricks to solve the unsolvable.

Let’s make a definition, what should be denoted:

Algorithm – a finite sequence of well-defined instructions, typically to solve a class of problems or to perform a computation, in a finite amount of space and time, in a well-defined formal language.

This is my own definition, contrived from that wikipedia article I told you to look at. There isn’t an agreed upon precise definition philosophically, partly because of its extremely meta-abstract (even the abstractions are abstract!) nature. (See arcane bickering here).
I’ll emphasize a few things here then we’ll move on:

1. It’s finite. That means it can be complicated but not infinite.
2. well-defined. A good one is like 2+2, there’s no nuances.
3. “instructions” is a great almost-synonym.
4. it’s instructions to compute or solve a problem.
5. it’s useless unless it uses finite (not-infinite) space and time. This is a big attribute I’ll detail in a bit.
6. “in well-defined formal language” they are somehow logically defined, and Spock must approve on the minutia.

If math is mostly playing with nouns, algorithms are mostly verbs. In some sense, algorithms are the playing.


How is this fun? I hear you. I want to talk about what the word should connote, rather than denote. I want to give you a feel, not a definition. Let’s talk about the most fun and easy introduction to algorithms: sorting.

Sorting problems are every computer science nerd’s first fun project. Given a list of random items, like socks or numbers or people of different height, what’s the fastest way to put them in order?

Simple problem, right? WRONG. As it turns out, which way is faster depends on the data set and what ways of shuffling them around you have available. Some of the fastest ways of sorting are actually terrible if they’re already almost in order. And then if you have extra space to make copies or take notes as you sort, you might be able to sort faster in less steps. That’s called a space-time trade-off. Towers of Hanoi is an old puzzle game that on the other extreme makes you sort with as little space as possible. It can be converted into binary because it literally can’t be smaller. (More on Towers of Hanoi and math)
More variables and options is more space, and more steps is more time, and you might decrease one by increasing the other.

Here is a brief introduction to sorting algorithms. I’ll summarize a few classics and have a link for more info. Gifs will make them fun. Wheeeee.

Bubble Sort
Are we done moving yet?

Bubble sort is the sort almost everybody thinks of first. If you haven’t read ahead, come up with your own sort first and see if it’s this one. It sucks, but don’t be ashamed. It’s a start.
Step 1: pick a pair of things and swap them so they’re in order.
Step 2: repeat moving groups around until they’re in order.
It sucks because it’s O(n2), which is math talk for saying twice as many things to sort will take 4 times as long. You want your sort to take O(n log(n)) or O(n) if you can manage it (and the O(n) ones are usually theoretical or complicated).

Insertion Sort
Brrrrrrrrrrrr

Insertion sort also sucks (O(n2)) and is like another flavor of bubble sort with its simplicity.
Step 1: Grab the first two items and sort them
Step 2: Repeat adding the next item and putting it where it goes

This might be the other one you thought of. It’s not that bad IRL. Very little to keep track of if you don’t struggle making room each time.

Selection Sort
And the next one, …

Selection sort sucks even worse than the above because it’s O(n2) in the best case. The other ones can be more like O(n) if you’re lucky.
This is the first one I think of.
Step 1: grab the biggest or smallest thing and put it on the end
Step 2: grab the next biggest or smallest thing.

The problem is you have to spend your time looking at everything for the next one, every time. It’s a good one to think about however, because if you managed to keep track of what you found as you compared them the first time, you might be able to make a space-time tradeoff.

Quicksort
Kids in the front! Smile Timmy!

Enter Quicksort. The name is a dead giveaway. This is the not-so-humble “hahaha rekt” sort that kicks butt most of the time. Don’t think of it as the fastest sort. Think of it as the arrogant sort that has weaknesses but is usually so good it makes other sorts mad. It divides and conquers.
Step 1: pick one thing. call it the “pivot”. Pick the middle or randomly, people argue over how to pick a pivot.
Step 2: move smaller ones to the left and bigger ones to the right.
Step 3: Take each half and repeat, going deeper. When you only have 2 left, put them in the right order and you’re done with those.

It’s a devilishly elegant O(n log(n)), but can take O(n2) if unlucky. Sometimes the hare takes a nap and oversleeps.

Mergesort
Alright gang, let’s split up!

Mergesort can go almost as fast as Quicksort, but it doesn’t trip at the finish line at random. The idea is divide and conquer O(n log(n)) like Quicksort, but from the other direction where you combine and conquer.
Step 1: Split in half, then repeat until it’s all groups of one.
Step 2: Go backwards to the last step and combine those two sorted, then three or four, until you’re done and it’s sorted.

It requires you to keep track of a bit more, but I’ve heard it said operating systems can do it fast with files. Notice it may use more space, and takes less time! I’m sure I could make a Fullmetal Alchemist joke here about the law equivalent exchange.

Heapsort
Like I said, complicated.

Remember when I noted some faster ones were more complicated? Heapsort is a last one I’ll mention. Remember when I said Selection Sort was good to think about because it’s easy to improve? This is where you can end up if you chased that white rabbit (wild goose?) of keeping track of what’s sorted. It can compete with Quicksort and Mergesort.
Step 1: Build a heap.
Step 2: Sort it by swapping one not sorted with the top and trickling down
.
What’s a heap? It’s a binary tree like you’ll see in the gif. You build this tree and then sort them so the big ones are at the bottom, by finding a little one compared to its parent and then swapping it with the top one and bubbling it down. The secret is mathematically the number of changes you have to do is O(n log(n)) once you’ve built the heap, because as you move each new one down into its right spot, you only have to look at a few, you forget about the other branches. Do some more research if this is the only one that confuses you. There are several ways of doing it.

Takeaway

Learning algorithms is a lot like taking a ride through a series of thought experiments and seeing how fast or high the roller coaster is. It’s educational to realize how many different ways you can solve a simple problem, and that crucially, not all ways of solving problems are remotely equal. And if you find a better way than anyone else, you’ve added to humanity’s genius.

Let me know what you think because if I can get people interested in the subject I’d love to do a series on algorithms. Searching graphs and hard problems and puzzles and riddles that if you solved unlock secrets of the universe are worthy of talking about. Algorithms are at the heart of our best known ways of solving problems. It’s a good mental exercise to answer a question correctly multiple different ways. It might even make you smarter.