31
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.
32
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 ...
33
34
A “perfect” voting system
A voting system that sidesteps Arrow's theorem entirely. The scare quotes around
35
Fantastic summary of some of the math pertinent to theoretical computer science.
This web page is a revised and extended version of Appendix A from the book Conceptual Structures by John F. Sowa. It presents a brief summary of the following topics for students and general readers of that book and related books such as Knowledge Representation and books on logic, linguistics, and computer science.
36
37
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…
38
39
Complex numbers have never been so intuitive to me
Imaginary numbers always confused me. Like understanding e, most explanations fell into one of two categories: Gee, what a great way to encourage math in…
40
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!”)…
41
Why Data Structures Matter: left, right folds, btrees
Our experience on Day 0 of JPR11 yielded a nice example of the need to choose an appropriate implementation of an abstract concept. As I mentioned in the previous post, we experimented with Michael…
42
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...
43
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:
44
45
Why Philosophers Should Care About Computational Complexity
Update (August 11, 2011): Thanks to everyone who offered useful feedback! I uploaded a slightly-revised version, adding a “note of humility” to the introduction, correcting the footnot…
46
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…
47
Hotelling’s Game, or Why Gas Stations Have Competitors Nearby
There are hundreds of gas stations around San Francisco in the California Bay area. One might think that gas stations would spread out to serve local neighborhoods. But this idea is contradicted by a common observation. Whenever you visit a gas station, there is almost always another in the vicinity, often just across…
48
Succinct Data Structures: Cramming 80,000 words into a Javascript file
<img src="http://zwibbler.com/shared/1024.png"/> jQuery creator John Resig needs a little help storing lists of words in his side project. Let's go overkill and explore a little known branch of computer science called Succinct Data Structures.
49
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…
50
Low-level x86 code compression for 64k intros
This is about the “secret ingredient” in my EXE packer kkrunchy, which was used in our (Farbrausch) 64k intros starting from “fr-030: Candytron”, and also in a lot of other …
51
Smaller than Bloom filters
I've been looking at what would be needed in order to have a global view of CRLs in browsers. At the moment revocation has three problems: privacy (by asking the CA about the status of a certificate you're revealing to them what you're looking at), performance (OCSP checks take hundreds of milliseconds which adds up…
52
Visualizing dynamic programming
I’ve always thought dynamic programming was a pretty crummy name for the practice of storing sub-calculations to be used later. Why not call it table-filling algorithms , because indeed, thinking of a dynamic programming algorithm as one that fills in a table is a quite good way of thinking about it.
53
Ten Ways to Check if an Integer Is a Power Of Two in C
To write a program to check if an integer is a power of two, you could follow two basic strategies: check the number based on its decimal value, or check it based on its binary representation. The former approach is more human-friendly but generally less efficient; the latter approach is more machine-friendly but…
54
Compiling to λ-calculus
Though it contains forms only for function applications, variable references and anonymous functions, it is equivalent to a Turing machine.
55
Skip Lists are Fascinating
Skip lists are a fascinating data structure: very simple, and yet have the same asymptotic efficiency as much more complicated AVL trees and red-black trees.
56
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.
57
Using Python and heat maps to determine the best place to aim on a dart board
Over break I went out with a buddy of mine and played some darts. This got me to thinking, where exactly should someone aim in order t...
58
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…
59
60
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…