### Graphs and Bananas

22Apr13

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-only read-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.

#### 8 Responses to “Graphs and Bananas”

1. Wait…write-only? Really?

• Sorry, typo. Read-only. Otherwise the only solution is to get really really high.

2. Damn, Splice is not free and even more damn, I could solve the puzzle only in O(N log N) time. But don’t help, I keep on trying!

3. More than 2 entries could be the same, right? Otherwise it’s easy.

• Yes, you could have more than 2 the same, or multiple pairs the same, or all the same value, etc. Nothing is guaranteed other than what the pigeonhole principle gives you for free.

4. As a consequence, if A and B both have n+1 numbers from 1 to 2n+1, then they can find with O(log n) bits of communication a number that they share. This is quite surprising, as if one of them had only n numbers, then even to decide whether they share a number needs almost n bits!

• 8 daveagp

You have O(log n) bits of working space, but it can be re-written and you might swap from looking at A’s part of the array to B’s part of the array up to a linear number of times.