A bit of math and a byte of computer science
I often drive between Boston and New Haven. While on the road, I find myself pondering a simple question: If my only goal is to arrive as fast as possible, how fast should I drive? Ignoring things like ethics (or fuel efficiency), the solution would seem to be simple. Drive as fast as possible. But there s a Continue reading Driving Faster Takes Longer
When people talk about space-efficient hash tables , they are usually talking about the following type of guarantee: If we are storing keys, each of which are bits, then the total space usage should be bits for some small . But, what if I told you we can do better? In fact, it s possible to construct Continue reading A Hash Table that Uses Less Space Than the Items that it Stores
Some Context: This post is a shortened version of a paper that won the best-paper award at FUN 2020. The paper is ostensibly about trains but the real-world applicability may be somewhat limited. The actual purpose of the paper is educational: we get to see some of the funnest techniques in probabilistic combinatorics being used to Continue reading Train Tracks with Gaps: Applying the…
Derek Severs short essay I Assume I m Below Average recently went viral on Hacker News. The article begins: Ninety-six percent of cancer patients claim to be in better health than the average cancer patient. Ninety-four percent of professors say they are better-than-average teachers. Ninety percent of students think they are more intelligent than the average Continue reading I m Above Average and…
Here s a question: what fraction of students at MIT have COVID-19 right now? Since MIT tests students twice a week, this question should be pretty easy to answer. But it s not. That s because MIT, along with other universities in the area, doesn t report their infection rate. What they report is the positive test rate. The Continue reading What is the actual infection rate at universities?
The probabilistic method is the art of applying probabilistic thinking to non-probabilistic problems. Applications of the probabilistic method often feel like magic. Here is my favorite example: Theorem (Erdös, 1965). Call a set sum-free if for all , we have . For any finite set of positive integers, there is a sum-free subset of size Continue reading My favorite example of: the probabilistic…
This is part of a new sequence of posts titled, My favorite example of: , for different values of . Today, is the pigeonhole principle. The Erdös-Szekeres Theorem: Consider any sequence of distinct numbers. There must exist a subsequence of numbers such that is either entirely increasing or entirely decreasing. The Erdös-Szekeres Theorem is a Continue reading My favorite example of: the pigeonhole…
In 1973, the author of the C programming language Dennis Ritchie was such a fan of the quicksort algorithm that he decided to name the language s sort function after it. In this post, I m going to dive into some of the most interesting (and bizarre) aspects of the qsort function. I m going to be Continue reading The Many Quirks of Qsort
In this post, I want to tell you about what I think might be the world s simplest interesting algorithm. The vertex cover problem. Given a graph , we want to find the smallest set of vertices such that every edge is covered by the set . This means that for each edge , at least Continue reading The World s Simplest Interesting Algorithm
Take a needle of length and drop it in a random position on a hardwood floor whose boards have the same width : There s some probability that the needle crosses between two adjacent floorboards. It turns out that has a surprisingly simple formula, Does this mean we can drop thousands of needles (or, Continue reading What Linearity of Expectation Has to Do with Needles and Pi