Sedgewick Algorithms Course

Working through the first twenty or so lessons from Zed Shaw's Learn C the Hard Way has been interesting but slow going -- a completely open-ended autodidactic mode is pretty difficult to maintain.

To review some algorithms, I've joined Sedgewick's recurring Algorithms Part 1 on Coursera. I gather that this class is more focused on implementation details and the specifics of programming in Java than Tim Roughgarden's excellent algorithms classes on Coursera, which uses CLRS and tends to focus more on reasoning about correctness and complexity. The contrast should be quite interesting. I haven't written in Java since working with Processing, so this should serve as a good language refresher as well.

The "Unfaithful" Sieve of Eratosthenes

I recently came across this bit of Python code on Stack Overflow, in a post that asked for an elucidation of the lambda predicates involved:

primes = range(2, 20) 
for i in range(2, 8): 
     primes = filter(lambda x: x == i or x % i, primes)

This is basically functional-esque code for something that resembles a naive implementation of the Sieve of Erastothenes. Given an input list of integers to start, the algorithm iterates through a second list of integers and uses the lambda predicates to filter the input list such that only primes remain. (The upper bound of 8 for the second list appears arbitrary; it's also a suboptimal upper bound given the input upper bound of 19, but we can ignore that here.)

As far as a naive implementation goes, it's arguably more elegant in a pure functional form like the following (in Haskell):

sieve          :: [Integer] -> [Integer]
sieve []        = []
sieve (p:xs)    = p : sieve [x | x <- xs, x `mod` p > 0]

The Haskell version can be called like so:

sieve [2..19]

As it turns out, though, this is a sieve by trial division rather than the true Sieve of Eratosthenes. Although the underlying logic is similar, the implementation of the algorithm is sufficiently different that the "unfaithful" sieve suffers from noticeably worse time complexity. A quick Google search immediately brings up literature on the subject: The Genuine Sieve of Eratosthenes.