This post comes in preparation for a post on decision trees (a specific type of tree used for classification in machine learning). While most mathematicians and programmers are familiar with trees, we have yet to discuss them on this blog. For completeness, we’ll give a brief overview of the termino...

The Recipe for Classification One important task in machine learning is to classify data into one of a fixed number of classes. For instance, one might want to discriminate between useful email and unsolicited spam. Or one might wish to determine the species of a beetle based on its physical attribu...

The Blessing of Distance We have often mentioned the idea of a “metric” on this blog, and we briefly described a formal definition for it. Colloquially, a metric is simply the mathematical notion of a distance function, with certain well-behaved properties. Since we’re now starting to cover a few mo...

A Series on Machine Learning These days an absolutely staggering amount of research and development work goes into the very coarsely defined field of “machine learning.” Part of the reason why it’s so coarsely defined is because it borrows techniques from so many different fields. Many problems in m...

Dear reader, this post has an interactive simulation! We encourage you to play with it as you read the article below. In our series of posts on cellular automata, we explored Conway’s classic Game of Life and discovered some interesting patterns therein. And then in our primers on computing theory, ...

Problem: Write a program that compares two sequences of differing lengths for similarity. Solution: (In Python) import math def dynamicTimeWarp(seqA, seqB, d = lambda x,y: abs(x-y)): # create the cost matrix numRows, numCols = len(seqA), len(seqB) cost = [[0 for _ in range(numCols)] for _ in range(n...

It’s often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey’s paper, “An Algorithm for the Machine Calculation of Complex Fourier Series.” They published a landmark algorithm which has since been called the Fast Fourier Transform algorithm, and has s...

Problem: Reduce the dimension of a data set, translating each data point into a representation that captures the “most important” features. Solution: in Python import numpy def principalComponents(matrix): # Columns of matrix correspond to data points, rows to dimensions. deviationMatrix = (matrix.T...

So here we are. We have finally made it to a place where we can transition with confidence from the classical continuous Fourier transform to the discrete version, which is the foundation for applications of Fourier analysis to programming. Indeed, we are quite close to unfurling the might of the Fa...

Problem: Compute a reasonable approximation to a “streaming median” of a potentially infinite sequence of integers. Solution: (in Python) def streamingMedian(seq): seq = iter(seq) m = 0 for nextElt in seq: if m > nextElt: m -= 1 elif m < nextElt: m += 1 yield m Discussion: Before we discuss the deta...

After a year of writing this blog, what have I learned about the nature of the relationship between computer programs and mathematics? Here are a few notes that sum up my thoughts, roughly in order of how strongly I agree with them. I’d love to hear your thoughts in the comments. Programming is abso...

Last time we investigated the naive (which I’ll henceforth call “classical”) notion of the Fourier transform and its inverse. While the development wasn’t quite rigorous, we nevertheless discovered elegant formulas and interesting properties that proved useful in at least solving differential equati...

In our last primer we saw the Fourier series, which flushed out the notion that a periodic function can be represented as an infinite series of sines and cosines. While this is fine and dandy, and quite a powerful tool, it does not suffice for the real world. In the real world, very little is truly ...

Problem: Derive the double angle identities $$\sin(2\theta) = 2\sin(\theta)\cos(\theta)\\\ \cos(2\theta) = \cos^2(\theta) – \sin^2(\theta)$$ Solution: Recall from linear algebra how one rotates a point in the plane. The matrix of rotation (derived by seeing where $ (1,0)$ and $ (0,1)$ go under a rot...

Problem: Prove that $ 2 = 4$. Solution: Consider the value of the following infinitely iterated exponent: $$\displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}$$ Let $ a_n = \sqrt{2} \uparrow \uparrow n$, that is, the above power tower where we stop at the $ n$-th term. Then $ a_n$ ...

Overview In this primer we’ll get a first taste of the mathematics that goes into the analysis of sound and images. In the next few primers, we’ll be building the foundation for a number of projects in this domain: extracting features of music for classification, constructing so-called hybrid images...

The Complexity of Things Previously on this blog (quite a while ago), we’ve investigated some simple ideas of using randomness in artistic design (psychedelic art, and earlier randomized css designs). Here we intend to give a more thorough and rigorous introduction to the study of the complexity of ...

Main Theorem: There exist optimal stackings for standard two-player Texas Hold ‘Em. A Puzzle is Solved (and then some!) It’s been quite a while since we first formulated the idea of an optimal stacking. In the mean time, we’ve gotten distracted with graduate school, preliminary exams, and the host o...

Problem: Prove that generalized versions of Mario Brothers, Metroid, Donkey Kong, Pokemon, and Legend of Zelda are NP-hard. Solution: http://arxiv.org/abs/1203.1895v1 Discussion: Three researchers (including Erik Demaine, a computer science professor at MIT famous for his work with the mathematics o...

Problem: Remember results of a function call which requires a lot of computation. Solution: (in Python) def memoize(f): cache = {} def memoizedFunction(*args): if args not in cache: cache[args] = f(*args) return cache[args] memoizedFunction.cache = cache return memoizedFunction @memoize def f(): ......

Problem: Write a program that shuffles a list. Do so without using more than a constant amount of extra space and linear time in the size of the list. Solution: (in Python) import random random.seed() def shuffle(myList): n = len(myList) for i in xrange(0, n): j = random.randint(i, n-1) # randint is...

By the end, the breadth and depth of our collective knowledge was far beyond what anyone could expect from any high school course in any subject. Education Versus Exploration I’m a lab TA for an introductory Python programming course this semester, and it’s been…depressing. I remember my early days ...

Not Just Time, But Space Too! So far on this blog we’ve introduced models for computation, focused on Turing machines and given a short overview of the two most fundamental classes of problems: P and NP. While the most significant open question in the theory of computation is still whether P = NP, i...

Decidability Versus Efficiency In the early days of computing theory, the important questions were primarily about decidability. What sorts of problems are beyond the power of a Turing machine to solve? As we saw in our last primer on Turing machines, the halting problem is such an example: it can n...

Finding Bigger Numbers, a Measure of Human Intellectual Progress Before we get into the nitty gritty mathematics, I’d like to mirror the philosophical and historical insights that one can draw from the study of large numbers. That may seem odd at first. What does one even mean by “studying” a large ...

This post assumes familiarity with some basic concepts in complex analysis, including continuity and entire (everywhere complex-differentiable) functions. This is likely the simplest proof of the theorem (at least, among those that this author has seen), although it stands on the shoulders of a high...

This post is the third post in a series on computing with natural language data sets. For the first two posts, see the relevant section of our main content page. A Childish Bit of Fun In this post, we focus on the problem of decoding substitution ciphers. First, we’ll describe a few techniques human...

This post assumes familiarity with some basic concepts in abstract algebra, specifically the terminology of field extensions, and the classical results in Galois theory and group theory. The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a...

Problem: Prove or disprove: at a party of $ n$ people, there must be an even number of people who have an odd number of friends at the party. Solution: Let $ P$ be the set of all people, and for any person $ p \in P$, let $ d(p)$ be the number of friends that person has. Let $ f$ be the total number...

This post assumes familiarity with some basic concepts in algebraic topology, specifically what a group is and the definition of the fundamental group of a topological space. The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a new tool in...