1
Darts, Dice, and Coins: A beautiful article on a beautiful algorithm
Earlier this year, I asked a question on Stack Overflow about a data structure for loaded dice . Specifically, I was interested in answering this question:
New
The latest blog posts to take off on Hacker News. 75 posts.
2
A Perl Regular Expression That Matches Prime Numbers
Take a look at this Perl regular expression: perl -lne '(1x$_) =~ /^(11+?)\1+$/ && print "$_ is composite"' This regular expression matches only the composite numbers (and doesn't match prime numbers). Can you figure out how it works? I'll give the explanation below but try to figure it…
3
4
5
6
7
VP trees: A data structure for finding stuff fast
<img src="http://stevehanov.ca/wavelet/cup.png"/> Let's say you have millions of pictures of faces tagged with names. Given a new photo, how do you find the name of person that the photo most resembles? <p> In the cases I mentioned, each record has hundreds or thousands of elements: the pixels in a photo, or patterns…
8
A primer on Bezier curves
A detailed explanation of Bézier curves, and how to do the many things that we commonly want to do with them.
9
Fuzzy string search
Intro Fuzzy search algorithms (also known as similarity search algorithms) are a basis of spell-checkers and full-fledged search engines lik...
10
Matrix multiplication in O(n^2.373)
For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n2.376) steps. Last year, though, in his PhD thesis, Andrew Stot…
11
Equations True Computer Science Geeks Should (at Least Pretend to) Know
This idea is a complete rip off an article that appeared in Wired a little while ago and it got me thinking what would my list for Compu...
12
Abstract algebra for developers and people who hate math
Hi. I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the sam...
13
14
A shuffled deck of cards is unique in all human history
Every time you shuffle a deck of playing cards, it's probably a unique order, never before seen in human history.
15
The (logarithmic) calendar I want
I was looking at my Google Calendar tonight and I realized that this software was encouraging a way of thinking about time which has signifi...
16
17
Recursive Functions of Symbolic Expressions and Their Computation by Machine
This paper appeared in Communications of the ACM in April 1960. It is the original paper on Lisp.
18
How to turn a biased coin into a Fair Coin
Fair Coins are the currency of Userland. A Fair Coin flips fifty-fifty with mathematical exactness. In the real world most coins are pretty fair, but you never know whether there might be a small bias to one side or another. This presents Lauren Ipsum , a girl who's lost in Userland, with a problem. No one wants her…
19
Fibonacci Flim-Flam.
physics, history of science, pseudoscience, hoaxes, writing, education, skepticisism, humor, quotes, illusions, 3d stereo photography.
20
Quake's Fast Inverse Square Root
I'm no graphics expert, but appreciate why square roots are useful. The Pythagorean theorem computes distance between points, and dividing by distance helps…
21
22
Algorithmic symphonies from one line of code
Lately, there has been a lot of experimentation with very short programs that synthesize something that sounds like music. I now want to sha...
23
Finding Love Optimally
Like many in operations research, my research interests often creep over into my everyday life. Since I work on scheduling issues, I get particularly concerned with everyday scheduling, to the consternation of my friends and family (“We should have left six minutes ago: transportation is now on the critical path!”)…
24
Lovelace's Leap
There's a great deal said about Ada, Countess of Lovelace that I find misguided. And, worse, the real intellectual triumph of Lovelace is ...
25
Crit-bit Trees: the best way to store sets
A crit-bit tree can be used as a high-speed associative array. For example, an array mapping 54 to 1, 19 to 2, 99 to 3, 85 to 4, and 88 to 5 can be stored as a crit-bit tree containing 54=1, 19=2, 99=3, 85=4, and 88=5. The smallest string in the crit-bit tree larger than 85= is 85=4.
26
Latitude doesn’t exactly mean what I thought
There are two kinds of latitude: geocentric and astronomical. On a perfect sphere, they're the same, but on an oblate spheroid like Earth they're different.
27
Surprises from numerical linear algebra (2010)
Here are ten things about numerical linear algebra that you may find surprising if you're not familiar with the field. Numerical linear algebra applies very advanced mathematics to solve problems that can be stated with high school mathematics. Practical applications often require solving enormous systems of…
28
Faster pathfinding using Jump Point Search
This is the final article in my three-part look at symmetry reduction algorithms for speeding up pathfinding on uniform-cost grid maps. Recapping the story so far: Part one introduces the notion of…
29
30
Compiling to λ-calculus
Though it contains forms only for function applications, variable references and anonymous functions, it is equivalent to a Turing machine.