31
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...
32
33
Fibonacci Flim-Flam.
physics, history of science, pseudoscience, hoaxes, writing, education, skepticisism, humor, quotes, illusions, 3d stereo photography.
34
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…
35
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.
36
"The worst algorithm in the world?"
You know the Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … Each number is the sum of the previous two. Let’s say the zeroth Fibonacci number is zero, so: $latex \begin{array}{r@{\…
37
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.
38
39
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 ...
40
41
A “perfect” voting system
A voting system that sidesteps Arrow's theorem entirely. The scare quotes around
42
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.
43
44
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…
45
46
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…
47
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!”)…
48
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…
49
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...
50
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:
51
52
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…
53
The Art of Computer Programming (interview with Don Knuth)
While he was over in the UK for a book tour and lecture series, Professor Donald Knuth made time to talk to BCS editor Justin Richards about his life.
54
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…
55
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…
56
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.
57
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…
58
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 …
59
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…
60
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.