Impromptus

Here is an algorithms puzzle which you are welcome to answer with your own implementation. The algorithms question is taken from “Algorithm Design” by Kelinberg and Tardos, which I recommend highly. You are doing some stress testing on jars to determine the height from which they can be dropped and still not break. You test [...]

My current projects list is out of control. I have replicated it below, with project statuses. Internet Topology It got me a PhD, and now its just sitting there. I haven’t touched it since my talk @Google, but it needs to get (re)written up and submitted to an actual journal. Status: only barely able to [...]

And so are many other sorts, I bet. The libbsd heapsort can’t sort an array that is larger than 2 Gb. This is probably because they have a line somewhere like if (2*i+1 > size) and with a 2Gb region, 2*i will overflow and return a negative number. It is a very strange experience to [...]

Let me tell you how mass storage should work: I stick in a new disk, power on the machine, and then the new disk is there waiting to be written to, having been identified as new and then joined into a storage cluster in which a group of non-identical disks mutually back each other up. [...]

Mostly this is posted for its pleasantly recursive nature. In response to many people asking me how I made the Ulam Spiral, I have produced a a PDF of the spiral which includes the code to make said PDF. I really like how it turned out. One subtle touch that fellow Python programmers will appreciate [...]

I looked at many things online which detail how to draw the Ulam Spiral, and all of them use various bad-sounding algorithms. I recently drew the Ulam Spiral and it went very quickly and the algorithm I used was both straightforward and basic-sounding. So I will reproduce it below so that others won’t have to [...]

The Sieve of Eratosthenes, implemented lazily in Python def integers_from(start):     x = start     while 1:         yield x         x += 1 def filter_out_multiples(stream, f):     return (i for i in stream if i%f != 0) numbers = (i for i in integers_from(2)) while [...]

I’ve been reading books on the subway too and from work. It is wonderful. I’ve been alternating between books of quality, and trashy scifi. I just finished my most recent “quality” book, and highly recommend it to all my fellow science nerds and enthusiasts. In The Discoveries, Alan Lightman has collected the most groundbreaking scientific [...]

Just in case you want generate a random tautology, you can find python code to do so at: http://pastie.org/933675. It’s actually pretty sweet – it won’t generate all true statements, but it will generate all tautologies of a given depth. Also, it has some clever hacks that allow it to be random (instead of true) [...]

In Mindstorms (the groundbreaking book, not the Lego set) Seymour Papert writes that part of what drives the mathematical curriculum is the technology available to students. As I see it, a major factor that determined what mathematics went into school math was what could be done in the setting of school classrooms with the primitive [...]