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.

Advertisements
This entry was posted in Paper and Puzzle and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s