Archive for the ‘computer science’ Category
AlgoRythmics
April 13th, 2011
The video above depicts an insertion sort implemented through Romanian folk dance.
See also: bubble sort, selection sort, and Shell sort.
Painting with WiFi
March 7th, 2011
So clearly this results in a pretty cool set of images. What I’d really like, though, is a 3-d graph depicting signal strength on a 2-d field.
Imagine if we replaced the rod with a disc composed of a set of concentric circles of lights. Suppose the number of circles that light up correlates with the strength of the signal, so that more signal => more light. Head to the city park, wander around in a grid pattern with this device, point the camera down from a building, and take a long exposure of the results. Signal would be represented as pools of light.
Someone go do this for me. Send me pictures.
art+design, computer science, infographic, video | No Comments »
RFC 2324
February 12th, 2011
RFC 2324 defines the Hyper Text Coffee Pot Control Protocol. HTCPCP is built on top of HTTP, implementing a range of new headers and errors (418 I’M A TEAPOT) that enable the intercommunication of networked coffee pots. Manufacturers, take note — standards-compliance grows the market.
Tupper’s Self-Referential Formula
January 22nd, 2011
Tupper’s self-referential formula describes a function whose graph (for inputs within a certain range) is the formula of the function itself.
Hofstadter should probably be informed.
Memoization Using Closures
January 6th, 2011
I wrote a little post about how to use closures in Python a couple weeks ago, but I’m not convinced that I really gave a good motivation for why we might want to use them. The example I gave was a little bit simplistic — here’s a better one.
First, we need to talk about memoization (if you’re familiar with memoization already, feel free to skip along a bit). Suppose we want to write a function to calculate the nth Fibonacci number. We might first write a naïve recursive function:
def fib (n):
if n < 2:
return n
else:
return fib (n - 1) + fib (n - 2)
This does the job (assuming we give it appropriate input), but it's actually terribly inefficient. Check out the call tree for fib (5):
We've got a few redundant calls here (notably fib(2) and fib(3)), and for higher values of n they really start adding up. As it turns out, this Fibonacci implementation is O (2n). Our elegantly simple algorithm is awful, just awful.
But we can salvage it! If we were to record our calculated values (using a closure, say) we could make this thing phenomenally more efficient.
def memoized_fib (n):
values = [0, 1]
def fib_helper (k):
if len (values) > k:
result = values [k]
else:
result = fib_helper (k - 1) + fib_helper (k - 2)
values.append (result)
return result
return fib_helper (n)
We're creating a list called values, for which each entry contains the Fibonacci number associated with its index, starting with the first two. After we've recursed all the way down the first time, we build up the list as we pop functions off the stack, so subsequent calls to fib_helper() don't really need to do any recursion at all — they can just look up the appropriate value in values. The list values is hidden inside a closure, so it's protected from the outside world. Certainly we could have implemented memoization using a global variable, but why would we if we we don't have to? Our closure provides an equally efficient and more elegant solution to the problem.
Just to drive home the efficiency gain, memoized_fib(500) takes 0.014s to run on my machine; fib(500) is still calculating an hour later. Which makes sense, since we've replaced an exponential algorithm with a linear one. Nice.
Python Closures
December 18th, 2010
I don’t exactly make my passionate, sexy-times love affair with Lisp a secret. Imperative languages have their strengths, but every time I have to give up my functional programming perks a little part of me cries.
I’ve recently started seriously digging into Python, though, and I think it’s going to be the Imperative Language That Makes Me Cry The Least. It’s got the holy higher-level trinity of map, reduce, and filter, syntactically-sugary list comprehensions, lambda expressions, and it even uses ** as the exponentiation operator, as God and Fortran intended.1 It also has closures, which are magic if you haven’t seen them before, so I’m going to yammer on about them for a bit.
To be fair, I’m probably not the best person in the world to tell you about lexical closures. You really want Wikipedia. In brief, though, a closure is a function that can access and change state in the environment in which it was defined. Kinda like object-oriented programming without the objects: the way methods can access private data is kind of analogous. Let’s just look at an example: 2
def makePowerFn (power):
def powerFn (base):
return base ** power
return powerFn
cube = makePowerFn (3)
print map (cube, [1, 2, 3, 4, 5])
Executing the above code applies our cube function to every item in the list and prints out [1, 8, 27, 64, 125].3 Neat, right? The magic part is that cube was effectively able to access power because it was defined within the enclosing lexical scope.
The concept of closures is pretty deeply embedded in serious-business functional languages like Haskell and the various dialects of Lisp,4 but lots of relatively modern mostly-imperative languages like Ruby and JavaScript have adopted them, too. I seem to recall that there’s been a ongoing attempt to get closures into Java, but I’m not going to hold my breath.
Anyway, closures! Now you know!
1 Python still can’t make metaprogramming trivial the way Lisp does, though. But I guess we can’t have everything. =P
2 Example adapted from defmacro’s rather nice functional programming discussion (near the bottom).
3 Notice how I got to use both map and ** in there? Awww, yeah.
4 “Haskell and the Lisps” would be an awesome band name, you guys.
A Case for Careful QA
August 22nd, 2010
The unspeakable shame felt here by Asimo’s quality assurance team is the main reason that I don’t want to be a test engineer.
Also, orientation starts tomorrow. Woo!
Social Networking Groups
July 12th, 2010
Google researcher Paul Adams posted a thoughtful presentation critiquing how social networking sites currently model relationships and groups. Executive-summary-summary: poorly.
Hatetris
April 11th, 2010
Hatetris: Like Tetris, but the game will always give you the worst possible piece. So, exactly like Tetris.
Content-Aware Fill
March 25th, 2010
I don’t know which dark god Adobe sold their collective souls to to make this work, but I think they got a good deal for them.
Unrelated P.S.: It looks like a team of researchers at Caltech just cured cancer. FYI.