Annotated Algorithms in Python: Applications in Physics, Biology, and Finance

Main Ideas 

Even if we cover many different algorithms and examples, there are a few central ideas in this book that we try to emphasize over and over.

The first idea is that we can simplify the solution of a problem by using an approximation and then systematically improve our approximation by iterating and computing corrections.

The divide-and-conquer methodology can be seen as an example of this approach. We do this with the insertion sort when we sort the first two numbers, then we sort the first three, then we sort the first four, and so on. We do it with merge sort when we sort each set of two numbers, then each set of four, then each set of eight, and so on. We do it with the Prim, Kruskal, and Dijkstra algorithms when we iterate over the nodes of a graph, and as we acquire knowledge about them, we use it to update the information about the shortest paths.

We use this approach in almost all our numerical algorithms because any differentiable function can be approximated with a linear function:

f (x + δx) ‘ f (x) + f ′(x)δx (1.1)

We use this formula in the Newton method to solve nonlinear equations and optimization problems, in one or more dimensions.

We use the same approximation in the fix point method, which we use to solve equations like f (x) = 0; in the minimum residual and conjugate gradient methods; and to solve the Laplace equation in the last chapter of the book. In all these algorithms, we start with a random guess for the solution, and we iteratively find a better one until convergence.

The second idea of the book is that certain quantities are random, but even random numbers have patterns that we can capture using instruments like distributions and correlations. The presence of these patterns helps us model those systems that may have a random output (e.g., nuclear reactions, financial systems) and also helps us in computations. In fact, we can use random numbers to compute quantities that are not random (Monte Carlo methods). The most common approximation that we make in different parts of the book is that when a random variable x is localized at a point with a given uncertainty, δx, then its distribution is Gaussian. Thanks to the properties of Gaussian random numbers, we conclude the following:

• Using the linear approximation (our first big idea), if z = f (x), the uncertainty in the output is

δz = f ′(x)δx (1.2)

• If we add two independent Gaussian random variables z = x + y, the uncertainty in the output is

δz = √δx2 + δy2 (1.3)

• If we add N independent and identically distributed Gaussian vari- ables z = ∑ xi, the uncertainty in the output is

δz = √Nδx (1.4)

We use this over and over, for example, when relating the volatility over different time intervals (daily, yearly).

• If we compute an average of N independent and identically distributed Gaussian random variables, z = 1/N ∑ xi, the uncertainty in the aver- age is

δz = δx/ √N (1.5)

We use this to estimate the error on the average in a Monte Carlo com- putation. In that case, we write it as dµ = σ/ √ N, and σ is the standard deviation of {xi}.

The third idea is that the time it takes to run an iterative algorithm is pro- portional to the number of iterations. It is therefore our goal to minimize the number of iterations required to reach a target precision. We develop a language to compare algorithms based on their running time and clas- sify algorithms into categories. This is useful to choose the best algorithm based on the problem at hand.

In the chapter on parallel algorithms, we learn how to distribute those iterations over multiple parallel processes and how to break individual iterations into independent steps that can be executed concurrently on parallel processes, to reduce the total time required to obtain a solution within a given target precision. In the parallel case, the running time ac- quires an overhead that depends on the communication patterns between the parallel processes, the communication latency, and bandwidth.

In the ultimate analysis, we can even try to understand ourselves as a par- allel machine that models the input from the world by approximations. The brain is a graph that can be modeled by a neural network. The learn- ing process is an ongoing optimization process in which the brain adjusts its synapses to produce better and better responses. The decision process mimics a search tree. We solve problems by searching for the most simi- lar problems that we have encountered before, then we refine the solution. Our DNA is a code that evolved to efficiently compress the information necessary to grow us from a single cell into a complex being. We evolved according to evolutionary mechanisms that can be modeled using genetic algorithms. We can find our similarities with other organisms using the longest common subsequence algorithm. We can reconstruct our evolu- tionary tree using shortest-path algorithms and find out how we came to be.