« We're #1 | Main | ISI Workshop: Theoretical Aspects and Models of Large Complex and Open Information Networks »

November 11, 2007

Things to read while the simulator runs; part 7

Using continuous systems for computation, examples being sorting using differential equations. In this latter application, the system of ODEs basically reproduces a bubble-sort style system, in which the sorted list is built up incrementally through comparison of adjacent elements in the list. Although the engineering applications of this stuff might be obvious, there are some interesting scientific questions imbedded in this work, too. For instance, can we use insights into how to analog-ize our typically discrete computation to recognize when Nature is making an effective computation? It's currently quite trendy to think of biological systems as being inherently computational, but our understanding of how living systems compute is mostly metaphorical. (tip to Jake)

I have rather mixed feelings about Malcolm Gladwell's writing. His books (e.g., Tipping Point and Blink) tend to be rather pseudo-scientific, but that hasn't stopped them from becoming virtual textbooks in the business community. On the other hand, his writing for The New Yorker is often excellent. For instance, his latest essay on criminal profiling is a wonderful skewering of the sleight of mind that criminal profilers (perhaps unknowingly) perform on their law enforcement clients.

Planarity is a wonderfully cute game (one that should come standard on every iPhone and iPod Touch!) based around a simple task. You're given a tangled "planar" graph, and your job is to untangle it by moving the graph's vertices around on the page until no two edges cross each other. Like sudoku, this game is based on some nice computational principles. Unlike sudoku, though, planarity is what computer scientists would call "easy", being solvable in polynomial time. (This recent arxiv paper discusses the relevant issues, and shows just how hard it is to untangle the graph quickly.)
In fact, I think there's probably a great business opportunity for taking classic computer science problems (SAT, vertex cover, sparsest cut, etc.) and turning them into entertaining puzzle games.

Finally, Brian Hayes, an intelligent amateur mathematician who frequently writes for the American Scientist magazine, has a pleasantly diverting essay on division and various algorithms for doing it. I remember learning the long-division algorithm in grade school and hating it. The only value I can see of learning long-division is that it teaches us that there's a symmetry in mathematical operations (addition and subtraction, multiplication and division, integration and differentiation, etc.), and helps build intuition into the relation of various numbers to each other. Otherwise, I think it's a complete waste of time (no one, not even careers in mathematics, uses long-division). Hayes, however, points out that while algorithms for addition, subtraction and multiplication are relatively straight forward, a legitimate and interesting question is Why is the algorithm for division so opaque?

(Another of Brian Hayes's essays at American Scientist is on a topic near to my heart: fat tails and power-law things. The byline is great: "Sometimes the average is anything but average.")

posted November 11, 2007 10:22 AM in Things to Read | permalink

Comments

Posted by: rod. at November 12, 2007 10:55 AM