Why learn algorithms?

As an iOS developer, do you really need to know about algorithms and data structures?

This question comes up a lot in one of the Slack groups I hang out in. Questions about algorithms and data structures are popular in job interviews, but are they useful to know once you’ve passed your interview?

My own opinion is that it’s silly to ask someone to reverse a linked list or invert a binary search tree in a job interview, especially if you’re interviewing a junior dev for a regular iOS position. It doesn’t tell you anything about the person’s actual coding ability.

On the other hand, I do think that knowledge of DS&A ought to be part of every developer’s toolbox. I believe it makes you a better programmer.

In a recent discussion I was asked to give a specific example of when I personally experienced that knowledge of algorithms was needed to create an iOS app. Not some hand-wavy theoretical reason but a practical real-world scenario. It’s a fair question. In this blog post I’ll be showing a few such examples.

It’s true that as an iOS developer you probably don’t have to deal with this stuff on a daily basis. Using the routines from the standard library is often sufficient to solve the programming problems you encounter. Often… but not always.

As I wrote in the foreword to the Data Structures and Algorithms in Swift book,

[…] there have been times when I was not able to write the software I wanted to, either because I did not understand how to approach the problem or because I did not understand how to make a solution that was fast enough.

In this blog post I’ve listed a few problems I encountered in some of my own apps. Most of these apps are quite simple but each still required a special algorithm or data structure that can’t be found in the standard library, or where the standard library’s solution would be too slow in practice.

Finding chords

Reverse Chord Finder is a simple but incredibly useful utility for musicians, especially musicians who play by ear. This app tells you the name of the chord you’re playing. Like a regular chord dictionary but the other way around.

The problem: The user can select notes on a piano keyboard, guitar fretboard, or sheet music. The app then has to look up the name of the chord that is made up of these notes. It must also check for partial matches, since you may be playing a chord plus a melody note. The app also detects chord inversions, the function of each note in the chord, and a few other things musicians like to know about.

This is a bit more complicated than just looking up the answer in a Dictionary. It’s certainly possible to include a huge database of all possible chords and note combinations, but I wrote this app in 2008 when iPhones only had 128MB of RAM and a CPU that wasn’t particularly fast.

Instead, I included a much smaller database of chord rules, containing only the formulas that are used to construct the chords. The lookup algorithm then tries to match the chosen notes to the best formulas and ranks them by relevance.

So this is an example where I had to come up with my own data structure to handle this app-specific problem. Often if you know exactly what your data is going to look like, you can optimize for it instead of using a generic but slower solution.

Switching instruments

Reverse Chord Finder had another interesting programming challenge.

The app lets you switch between instruments. For example, you can select notes on the piano and then switch to guitar, and the app will show how to play that same chord on the guitar. This was not the main attraction of the app but a lot of users found it useful to learn how to translate chords between instruments.

The problem: Going from guitar to piano is easy, as each note has a unique position on the piano keyboard. The other way around is harder: the same note can appear in multiple places on the guitar fretboard.

The app needs to be smart in where it places the notes on the guitar, so that it chooses a fingering that a human player would actually want to use.

Again this could have been solved the brute-force way with a huge database of chords and their preferred fingerings. I instead created an algorithm that used heuristics to find the best position for the notes on the guitar.

Dealing cards

Mahjong Cards is the classic game of mahjong solitaire but with a simple twist: it’s played with a regular deck of playing cards instead of Chinese tiles.

Games programming is one area that often needs special algorithms and data structures, especially to make the game run fast enough. If you’re interested in making games, it’s worth reading up on game algorithms.

The problem: How to deal the cards so that players can play for a long time without having to press the “shuffle” button.

If you deal the cards randomly, players will get stuck after just 3 or 4 moves and need to shuffle the cards again before they can continue. That gets annoying fast… not good for what is supposed to be a mindless, relaxing game.

The solution is simple: instead of dealing randomly, play the game backwards. Always deal cards in matching pairs, choosing their position at random from the open slots, and keep going until the level is filled up. Now players hardly ever have to shuffle, since there is always a matching pair to be found somewhere.

It’s a simple algorithm but it makes the difference between a game that is annoying and a game that is fun. Not all algorithms have to be difficult!

Computer player AI

Fnurgletoe (also known as Egg Chess) is like Tic-Tac-Toe except there are 3 game pieces and both players can play any piece — this makes the game much more exciting than Tic-Tac-Toe. You can play against another human or against an AI.

The problem: How to implement the AI for the computer player. The simplest possible AI would just make random moves, but that’s not very hard to beat. You need an algorithm that gives the human player a bit of a challenge!

There are well-known algorithms for this, such as minimax (see GameplayKit) but I did not know about that algorithm at the time and GameplayKit did not exist yet. Roughly speaking, my AI player follows these rules:

1. Can I make a winning move? Make it.
2. Is the other player able to make a winning move? Block it.
3. Otherwise, choose a random move.

This actually creates a pretty strong opponent, although I found it’s possible to beat this AI by playing a specific sequence of moves. If I had known about minimax and other game AI algorithms, I could have made my computer player even better!

Detecting voice pitch

Next up is yet another game. I suppose if you’re making games you run into more of these situations than if you’re just making UITableView-based apps. Although this particular example is not so much about game programming but about audio.

Simon Sings was like the classic game Simon but using musical notes instead of flashing lights. You’re supposed to sing or hum the right notes in the right order.

The problem: The app should listen to the user’s voice and detect the pitch of what they are singing or humming.

The straightforward way to do this is to use a Fast Fourier transform (FFT). There were no FFT routines available on iPhone OS at the time, so I had to implement my own. The Fourier transform gives you the frequencies that are in the sound, but additional post-processing is needed to make sense of this data in the game.

If your app needs to do audio processing, you’ll probably end up using one or more DSP (Digital Signal Processing) algorithms like the FFT.

Linked lists, trees, graphs

I wrote my fair share of linked lists back in the day when programming languages didn’t have arrays that would automatically resize when you added or removed elements. These days you almost never need to use a linked list, especially not the kind of LinkedList container class they make you write in job interviews.

But you definitely will need to link objects together one way or the other.

Linked list example: A nice example of where a linked list is used to great effect can be found in my friend Marin’s EasyAnimation library that makes it easy to run several animations in a row.

In order to chain animations together it uses a special class EAAnimationFuture. One way to keep track of the chain of animations is to put them in an Array but then you need someone to manage that array. It’s much more elegant to make each EAAnimationFuture object simply point to the next animation in the chain. Voilá, a linked list.

Trees come up on a regular basis too. Not so much binary search trees (another favorite of many interviewers), but whenever you’re dealing with hierarchical data, a tree is the obvious data structure to use.

Tree example: A JSON file or XML file is a tree-based data structure. The HTML DOM is a tree. The iOS view hierarchy is a tree. In fact, most of your app’s data model is probably tree-like.

I’m sure I’ve used trees many times in the apps I’ve worked on, but the only one that comes to mind right now is a recursive descent parser in Swift for Markdown files. It’s safe to say that if you’re using a tree to store data, you’ll probably end up using some kind of recursive algorithm to work with that data.

Linked lists and trees are special cases of a graph. If you could only learn about a single data structure, you should learn about graphs. They’re everywhere. If your data can be expressed as a graph (protip: it usually can), it becomes possible to use one of the many standard graph algorithms to do interesting stuff with that data.

Graph example: I wrote a library that lets you construct deep neural networks on iOS using a domain-specific language in Swift:

let output = Input()
      --> Resize(width: 28, height: 28)
      --> Convolution(kernel: (3, 3), channels: 32, name: "conv1")
      --> MaxPooling(kernel: (2, 2), stride: (2, 2))
      --> Convolution(kernel: (3, 3), channels: 64, name: "conv2")
      --> MaxPooling(kernel: (2, 2), stride: (2, 2))
      --> Dense(neurons: 128, activation: relu, name: "fc1")
      --> Dense(neurons: 10, name: "fc2")
      --> Softmax()

The natural data structure for storing the definition of this neural network is a graph, in particular a directed acyclic graph or DAG. Every time you use the --> operator it adds a new node to this graph.

To make predictions using such a neural network, the layers need to be executed in the correct order from start to finish. If layer D depends on layers B and C, and layer B depends on A, then the order in which to perform the layers is A, B, C, D or C, A, B, D.

The algorithm for deciding which nodes in the graph need to be performed first is called a topological sort, which in turn is based on a depth-first search. This was an easy problem to solve because I knew about graphs. 😎

Text editor and diffs

This one is not really an iOS app but I’m including it because it’s something that could conceivably be done in a mobile app.

Compare and Merge is a file diffing utility for Windows. It shows two text files side-by-side with big arrows pointing out the differences between them. You can edit the files and the app immediately updates the diffs while you’re typing. (The app is still for sale in case you need to do some diffing on Windows.)

Problem #1: I could not use the standard Win32 text editor component for this app, so I had to write my own text editor. One of the main problems facing text editors is that typing into the middle of existing text requires the rest of the text to be shifted up in memory.

It’s like calling insert() on an Array, which is an O(n) operation. The larger the array, the longer it takes. Doing this naively is fast enough for small text files but if you’re inserting text at the beginning of a 10 MB document, moving up all 10 MB of text on every keystroke to make room for the new characters is really inefficient.

Data structures to the rescue! There are many possible ways to solve this. The data structure I ended up using is called gap buffer. You probably won’t be writing your own text editor on iOS but you may run into the problem of repeatedly inserting data into the middle of a large array.

Problem #2: To find the differences between two text files, you need to find lines both files have in common, lines that are different but where only a few characters have been changed, and lines that are only in one of the files and missing from the other.

At first I tried to come up with my own diffing routine but I soon realized this is a difficult problem! Since the diffs need to update in real-time while you’re typing, it also needs to be fast.

Fortunately, I came across the well-known LCS or Longest Common Subsequence algorithm. Even so, just having the algorithm is not enough, I had to make many tweaks. For example, you don’t want to recompute all the differences between the two files on every keystroke, only those in the visible area.

Problem #3: One other interesting challenge I remember is drawing the “mini map” on the side of the window next to the scroll bar. This shows you at a glance where all the diffs are. It’s not a super difficult algorithm, but not trivial either. I include it here because sometimes just making something look nice requires you to code up a clever algorithm.

The end

These were some anecdotes I could remember from my own personal apps. Even for these relatively simple apps, I’ve had to come up with an algorithm or data structure that didn’t exist in the standard library or Cocoa APIs. To me that proves it’s worthwhile to learn about DS&A even if you’re “just” an iOS developer.

I’ll gladly admit that certain kinds of apps are more algorithm-heavy than others. I already mentioned games and audio programming as two examples of this. These days I’m doing a lot of machine learning and so I’m up to my neck into algorithms.

But even as a regular iOS developer I’m sure you’re eventually going to run into situations where knowing a bit about graphs, trees, and so on could make a big difference. And if not, you might want to think about working on more exciting apps. 😉