Computer science is, at its very core, all about algorithms. Data structures — the other core pillar of the field, exist to facilitate the design of more efficient algorithms. There is a limitless number of algorithms. However, almost all of them are designed using a handful of patterns. In this note, I describe a few foundational ones.
<aside> 🏋🏾♀️ Incremental Design is perhaps the first pattern one comes up with when faced with any computational/algorithmic problem. Here's how it goes: You'd like to solve some problem for a collection of items $\left<a_1, a_2, \ldots a_k \right>$. You reason that you can solve the problem by starting with the smallest possible portion of the collection on which the problem is trivially solved, then incrementally solve it for bigger and bigger portions until you cover the entire collection. For instance, you can start by solving the problem on $\left<a_1\right> \text{ then } \left< a_1, a_2 \right> \ldots$ In general, after having solved the problem for $\left<a_1, \ldots a_{i-1}\right>$ you'd like to solve it for $\left<a_1, \ldots a_{i}\right>$. The crux of the problem is figuring out how to add the $a_i$th element into the existing solution. The lower bound for the runtime of incremental algorithms is obviously $\Omega(n)$. Their tight bound, however, depends on the time it takes to incorporate the new item into the existing solution. If it takes logarithmic time, this method yields an $\Theta(n \lg n)$ solution. If it takes linear time, it yields a quadratic solution. Insertion sort is the canonical incremental algorithm. This method also shows up in dynamic programming solutions a lot.
</aside>
<aside> 🛠 Divide, Conquer, & Merge is another canonical design method. It is also, perhaps, the most "mathematical" since it is derived directly from recurrence relations. As before, we'd like to solve some problem for a collection of inputs $\left<a_1, a_2, \ldots a_k \right>$. To solve the problem at hand for the whole collection, we solve it for smaller subproblems and then combine the solutions. That is, we divide the input problem into smaller subproblems. Then, we conquer the problem on those smaller problems. Finally, we merge the solutions to the subproblems. The crux of this method is the merge step — before using this pattern, we have to ensure that we can combine the solution to smaller subproblems in reasonable time.
Merge sort is the prototypical divide and conquer method. To sort a collection with n items, we divide it into two portions and then recurse on each portion until we hit a base case (n = 1 — trivially sorted). Then we merge the sorted subarrays in linear time. The recurrence for merge sort is $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) = O(n \lg n)$. Notice that the time taken to merge the solutions has a huge influence on the runtime of DnC algorithms.
The most straightforward way to analyze the runtime of DnC methods is by reasoning about the structure of the subproblem tree. Finally, note that the splits need not be disjoint. To see an example of this, look up the divide an conquer solution to the maximum subarray problem (we have the left, right and crossing subproblem).
</aside>
<aside>
♻️ Indexing/Lookup Table/Preprocessing is used to great effect whenever we need to design an algorithm where our input collection is fairly static and we expect to make many different queries on it. This involves precomputing answers to all possible queries or placing the input in a clever data structure such that queries can be answered very fast. For instance, if we know we'll be doing prefix queries on some collection of strings, we may decide to keep them in a patricia trie. If we expect to be answering msb queries for a 64 bit numbers, we can create a lookup table with precomputed msb values to all 16 bit integers and then answer each query in constant time (via 4 lookups).
The runtime analysis of this pattern must take into account both the pre-processing time and the query time. We often report it as $\left<g(n), f(n)\right>$ where $g(n)$ is the pre-processing time and $f(n)$ is the query time.
As an aside, I think the coolest method in this realm is the use of sparse tables. Where we use the fact that any number can be written as a sum of powers of 2.
</aside>
<aside> 🐒 Prune and Conquer is another common pattern that is often applied whenever you have a sorted collection. When applying this pattern, we judiciously discard a portion of our collection that cannot possibly contain the answer we're looking for. This is the prune step. We then look for the solution (conquer) in the remaining smaller problem space. Binary search provides the best example of this method.
Note that this method can also be applied even when the input collection is not sorted — as long as it has some structure. The Quickselect procedure for finding the $i_{th}$ order statistic presents a good example of this. By ensuring that the collection is sorted relative to a random pivot (using the partition function from quicksort) we are still able to discard half the inputs without sorting the whole collection.The lower bound for the runtime of such methods is $\Omega(\lg n)$. Binary search attains this runtime while quickselect runs in $\Theta(n\lg n)$ because of partitions' linear runtime.
</aside>
<aside> 🚧 The method of four Russians (aka, how to shave off log factors). This method goes this way: you have an input collection of size $n$ for which you'd like to solve some problem. You start by partitioning the collection into blocks of size $b$ — you end up with $\lceil \frac{n}{b}\rceil$ such blocks. The trick is to ensure that $b$ is small enough so that we can can solve the problem at hand on a single block quickly, but not too small to ensure that the number of blocks is small.
After the partitioning, we solve the problem in each block — ideally, this should take linear time. We then aggregate the solutions from all $\lceil \frac{n}{b}\rceil$ blocks into a macro array. The way we proceed at this point depends on the problem at hand. Suffice to say that the key marker of this method is the micro (sub-problem on each small block), macro (subproblem on the aggregated array of solution from small blocks) decomposition.
To see an example of this, lookup the median of medians method. Another example is the method used to solve the RMQ problem in linear space and constant time. The method also shows up in the design of the Y-Fast trie. As a final thing, this method usually shaves off log factors from the runtime of algorithms (It is how median of medians shaves off the log factor from the $\Theta(n \lg n)$ runtime of quickselect from which it is based.
</aside>
<aside> 🐋 Methods for Decision and Optimization problems deserve their own special section because of the kind of reasoning used. They include Dynamic Programming and Greedy algorithms. Do note, however, that they heavily rely on the other patterns — especially incremental algorithms design (after having found the optimal solution for $k$ items, we'd like to find the optimal solution for $k + 1$ items)
</aside>
<aside> 🐁 Data Structure based algorithms are used whenever, after the modelling step (see below) we discover that the problem at hand can be expressed as some combinatorial structure such as a graph or a tree.
</aside>
<aside> ✂️ Sweeping — refer to the section on computational geometry.
</aside>
<aside> 🎋 Randomized Algorithms deserve a mention mostly because of the elegant probabilistic techniques used in their analysis. They also form the basis of online/streaming algorithms.
</aside>
<aside> 🛬 The patterns discussed thus far work well offline — that is when we have access to the entire input collection. When the input values come in one at a time, and we cannot afford to wait for all items to arrive (perhaps because there's an infinite number of items) we often resort to approximate methods. The two main ones are sampling and sketching. For a brief, but incomplete discussion, see this note here.
</aside>
<aside> 🥃 Of course, patterns can only be applied once the problem at hand has been fully understood and formalized. In real world algorithm design, this often requires patience, and deep domain expertise. Often, modelling is the main part of algorithm design. Knowing the patterns, however, is still extremely valuable since it often guides the modelling process. Formalizing the problem often involves coaxing it into a form that allows us to easily apply one of the patterns above.
</aside>