## Paper and Puzzle a Day 4

Still a pretty early morning post considering the time I got up…

First, the paper: Recently came across the following paper, “Pessimal Algorithms and Simplexity Analysis.” This is the first couple of sentences in the paper, and I have to say, it is quite brilliantly written:

“Consider the following problem: we are given a table of n integer keys A1 , A2 , …, An and a query integer X. We want to locate X in the table, but we are in no particular hurry to succeed; in fact, we would like to delay success as much as possible.”

It goes on later to state,

“The research procedure is a prototypical example of an entirely new branch of Computer Science, the design and analysis of reluctant algorithms.”

Very great read for an early morning when all you want to do is go back to sleep. This tongue-in-the-cheek article attempts to introduce the discipline of simplexity analysis, where it is the algorithm’s designer’s job to design the slowest running algorithm. However, it is not enough to add infinite loops in the code because that is easily detectable and can be construed as wasting time. No, the goal is to produce an algorithm that is the slowest running possible but can full a naive observer that it is making progress with each time step. In this way, we can manage to create an algorithm that is indeed very reluctant.

The paper is filled with more gems that is sure to brighten up your morning, and it’s also very short.

Now, the puzzle: we’re going to steer away from the prisoners’ hats puzzles today no matter how much I like them.

00110010 00110001 00110010 00111000 00110011 00110010 00110010 00110000 00110000 00110000 00110011 00110001 00110010 00110110 00110011 00110011 00110001 00110001 00111000 00110010 00110010 00110000 00110110 00110111 00110000 00111001 00110011 00110001 00110000 00110000

That’s it, good luck.

Now the answer to yesterday’s puzzle:

Again this comes down to timing. If any prisoner sees hats of different colors on the other two prisoner’s head, then he would say the color of the 3 colored hats. If they all see the same color, then no one would say anything and eventually someone would know that the hat on each of the prisoner’s heads is the color with the 3 hats.