Graphs and Bananas
Some fantastic things as of late. (Not more fantastic than previously but still not bad.)
- A puzzle. You have an integer array of length N in memory, indexed from 1 to N. Each of the integers that it contains is between 1 and N-1. By the pigeonhole principle, two entries are the same. If the array is
write-onlyread-only, can you find two identical entries of the array in O(N) time, using O(log N) additional bits of read-write memory? Thanks to Dan Armendariz for telling me about this at SIGCSE.
- A game. Binary tree isomorphism? There’s an app for that. The game Splice is based on this at some level, where you have a limited number of moves to adjust one tree to make it into another. This is alone a nice kind of puzzle, especially since it’s NP-complete. But what is the most striking about this game is its beautiful user interface. Very responsive and fluid, behaves well with a touchscreen. Excellently themed. Getting started is rough since the instructions are tucked away in a corner. Probably my favourite Android game, although I have not found that many contenders.
- A book. In Pursuit of The Travelling Salesman by Bill Cook describes a classical problem in computer science and mathematics in a way that is both scientifically elegant and humanistically down-to-earth. This is probably my favourite book out of anything I could hand to an undergrad and get them to care about the P vs NP problem. The writing explains insights without being technical, and presents interesting stories about the researchers without turning into biographies.
- A movie. There is also a movie Travelling Salesman, which recently completed an IndieGogo campaign, dealing with the same problem. According to Bill Cook, the film almost had to cancel production in the middle of 2010 when an alleged proof of P != NP was circulated. (Although, aren’t a lot of good fictional movies based on false premises?) Perhaps my favourite thing about this movie is that the main character shares a name with a beloved Canadian hockey player-cum-coffee mascot.
- Muffins. Not sure why I like bananas only when they are a component in a baked good, but there you go.
Filed under: computer science, food, tsp | 8 Comments