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(): ... Discussion: You might not use monoids or eigenvectors on a daily basis, but you use caching far more often than you may know.

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.

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.

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, it turns out that there are hundreds (almost 500, in fact!) other “classes” of problems whose relationships are more or less unknown.

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 never be solved a finite amount of time by a Turing machine.

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 number?

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 highly nontrivial theorem.

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 humans use to crack ciphers.

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 new tool in mathematics can prove its worth by being able to prove the fundamental theorem in a different way.

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 of friendships between pairs of people at the party.