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

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.

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.

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.

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.


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.

Thinking in 4D

I want to mention of one of my favorite mental exercises: thinking in higher dimensions. I find it’s useful to expand your ability to visualize difficult things. (I should do a list of brain workouts!) These nerd kings will take you on a journey, and I want to go over the 4D part. (You might watch it more than once when you have time, until you can grasp it!)

Try conceptualizing 4D objects. It’s not easy to handle higher dimensions, but I encourage you to try the fourth specifically. One of the common ways of describing the fourth dimension is to use time as another axis. This has the benefit of showing you an animation of something changing shape to describe all the 3D “slices”, showing you the whole thing. The problem is it introduces a bit of a crutch, in that it feels a lot more like regular 3D, hiding the nature of that extra dimension.

If you are going to imagine something changing shape over time, you need to also imagine that all of the vertices on the object are connected through time to each other. You have to imagine that a certain subset of the frames, even if just the first and last, are all connected by lines you can’t see. See the problem? That’s why it’s easier to imagine the fourth as something like scale instead, when introducing it. Just pretend you can go smaller forever like you can go bigger.

Here is what a 4D rotation looks like on its fourth axis. It’s fun.

A 4D cube, a tesseract, rotating on the fourth axis. Rotation on other axes look normal.

Make sure you remember that 4D objects are built out of 3D objects. You need to think of the tesseract as 6 squished cubes connecting the inner and outer cubes. Those 8 cubes are what a tesseract is made of. Don’t think about it as points and lines too much, or you’ll miss what you’re trying to visualize. Here’s a way to fold and unfold it that might help.

See all 8 cubes.

I really think that’s the one you ought to have down by now. Now go back and watch the first Avengers movie and you might look at the blue cube different. If you’re religious, you can go see Salvador Dalí’s Corpus Hypercubus.

Once you have that down, you can begin to think about the other five regular convex polytopes. You might know that the platonic solids mentioned in the video are the D&D dice (minus the d10 diamond). Well, you can think of these as the main six 4D dice.

What fun are 4D dice if you don’t roll them?

Nobody would expect you to grasp 120 squishy dodecahedrons. I still recommend trying to study the first four to expand your mind. The first three should be reasonably within reach. For fun, we’ll end with the 120-cell from the inside.