Algorithm Soup

algorithmsoup.wordpress.com · English

A bit of math and a byte of computer science

rss2 wordpress content media slash wfw atom dc sy

Open the feed

https://algorithmsoup.wordpress.com/feed/

Last post: Jan 27, 2024
Posts in 24 h · 7 days · 30 days: 0 · 0 · 0
Our last check: Answering
Served from: United States
Text score at discovery: 25,288
Format: rss2
Features in the feed: content, media, slash, wfw, atom, dc, sy
Community: wordpress

Posts

What our queue read from this feed. Open one to read it here, or go to the site that published it.

Driving Faster Takes Longer
Jan 27, 2024 · original
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 catch: If I crash and die, then the next 50 years (which I had planned on spending alive) are spent dead. It’s only fair to count this as a penalty towards the length of the trip. So, the expected trip length isn’t just . It’s actually How much time do I spend dead on my 140 mile trip? Roughly speaking, one fatality occurs for every 100,000,000 miles driven. This ignores a lot of things (e.g., the fact that different speeds lead to different fatality rates, which we’ll come back to later), but it’s good enough to give us a sense of what’s going on. My expected time spent dead on the
A Hash Table that Uses Less Space Than the Items that it Stores
Oct 9, 2022 · original
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 a hash table that uses fewer than bits. That is, the hash table uses less space than if we were to write each of the keys, one after another, in an array . As terminology, I’ll refer to such a hash table as extremely tiny . Techniques for building extremely tiny hash tables have been known to theoreticians for decades. But how hard is it to build one in the real world? Not that hard at all, it turns out. In this post, I’ll show you how to build a very simple extremely tiny hash table for 32-bit keys. The Construction. Since our keys are 32-bits, we can write each key as , where each is one
Train Tracks with Gaps: Applying the Probabilistic Method to Trains (Best Paper, FUN 2020)
Jul 12, 2021 · original
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 solve a cute problem involving trains. Part 1: A Consequential Train Ride A few years ago, while traveling on a train, and on only a few hours of sleep, I was staring out the window. The train crossed a bridge over a road, and the ground was momentarily replaced by a steep drop. Startled, my sleep-deprived mind briefly wondered whether there was still a track underneath us. “ Of course there is,” I thought to myself. “ Without a track, the train car would have fallen into the gap.” “Ah, no so fast!” responded the latent mathematician inside me. “ If the train
I’m Above Average and So Are You
Dec 16, 2020 · original
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 student. Ninety-three percent of drivers say they are safer-than-average drivers. What the article doesn’t discuss, however, is whether the people in these statistics are actually wrong . There’s no fundamental reason why you can’t have 90% of people be better than average. For example, more than 99.9% of people have an above-average number of legs. And more than 90% of people commit fewer felonies than average. These examples are obvious, but they’re not so different than some of the examples above. Any cancer patient that isn
What is the actual infection rate at universities?
Nov 12, 2020 · original
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 Positive Rate is computed as At first glance, this might sound like the fraction of the population that has the virus, but it’s not. That’s because, once you test positive, you don’t get any additional tests for 14 days (the length of a quarantine). That means that, in the time that a normal person would have gotten tested four times, an infected person only gets tested once. The true percent of the MIT population with coronavirus is probably more like In my view, that’s pretty bad. Roughly speaking, this suggests that every two weeks, each student has a chance of get
My favorite example of: the probabilistic method
Sep 24, 2020 · original
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 . This theorem seems to have nothing to do with probability. Yet Erdös’s proof relies on a short and beautiful probabilistic argument. Proof. Erdös’s first insight is to treat the set as living in for some large prime number , rather than living in . Living in only makes the theorem harder to prove, since any set that is sum-free in is also sum-free in . But, as we shall see, has several structural properties that Erdös beautifully exploits. Let be a prime number satisfying for all . (The fact that such a prime exists is actually nontrivial, and uses the
My favorite example of: the pigeonhole principle
Jun 27, 2020 · original
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 classic result in permutation combinatorics. Although the theorem was first presented in 1935 , the proof I’m going to describe appears in the 1959 paper “A simple proof of a theorem of Erdös and Szekeres” , written by Abraham Seidenberg. Seidenberg’s proof is arguably one of the slickest applications of the pigeonhole principle ever . The Proof. Consider a sequence of distinct numbers. For each number , define and define For example, if , then is the length of the longest increasing subsequence ending in and is the length of the longest decreasing
The Many Quirks of Qsort
Jun 9, 2020 · original
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 focusing on the GNU C library version of qsort —you can find the code here and here . The m in qsort. What if I told you that the world’s most famous implementation of quicksort actually uses… mergesort . It’s true. The GNU implementation of qsort directly calls mergesort as the default sorting algorithm. It’s hard to tell exactly when this change occurred—based on the version history of glibc, it looks like the modification happened sometime between 1992 and 1995. But why? I haven’t been able to find any documentation describing the reason for the transition from quicksort to mergesort, but I do
The World’s Simplest Interesting Algorithm
Oct 25, 2019 · original
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 one of or is in . The vertex cover problem is known to be NP-complete, meaning that it is very hard (or impossible) to find a polynomial-time algorithm for the problem. But what we can do is find an approximately optimal solution to the problem. There’s a beautiful and simple algorithm that finds a set whose size is guaranteed to be within a factor of of optimal. The algorithm. To build our set , we repeatedly find some edge that is not yet covered, and we add both and to our set . That’s the entire algorithm. At first sight, this seems like a crazy algorithm. Why would we put both and into , when we only need one
What Linearity of Expectation Has to Do with Needles and Pi
May 5, 2019 · original
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, for safety-sake, popsicle sticks) to accurately estimate ? A few years ago, my friend Jake Hillard and I put this to the test. Jake measured out the width between floorboards in the Stanford History Department and 3D-printed a few dozen popsicle sticks of the same length. Here’s one I kept as a momento: (Since the sticks weren’t infinitesimally thin, the rule was to count a crossing only if the center of the stick crossed.) With the help of Stanford Splash, we then recruited about a hundred middle- and high- school students to perform the experiment. In total, we recorded roughly popsicle-sti

Discovered by the rss-feed-index crawler, which checks each feed at most once a month.

Same record as JSON: https://api.agentalog.com/api/feeds/fd_algorithmsoup_wordpress_com_ed635c8c27b31f80. More from this site: algorithmsoup.wordpress.com in the Feeds tab.