My algorithms class

One of my favorite classes during my doctoral studies at Arizona State University was Design and Analysis of Algorithms. This was back in the fall of 2002. Goran Konjevod was the instructor.

Goran had a penchant for stimulating thought and that showed in the sort of questions he chose from textbooks for his assignments and exams. Here’s one I remember enjoying very much. I like it particularly because of its dark, authoritarian overtones – it brings out the Stalin in you. Not the mass-murdering Stalin but a clinical and efficient one. I am joking, of course, but you'll see what I mean when you read this:

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don’t know which one. To make matters worse, the poison the spy used was very deadly; just one drop diluted even a billion to one will still kill someone. Even so, the poison works slowly; it take a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O (log n) of his taste testers.

And no, the answer is not that we need a human rights commission to investigate this, though that might be a tempting lateral-thinking answer! Don’t ask me for the solution to the question either; I’ve long forgotten it!

What I do want to state is that I was quite inspired by the class. I was doing a PhD in Industrial engineering, but the class taught me the computer science way of looking at problems, and illustrated how intelligent one could be in designing algorithms. Without a doubt, the class was why I eventually went to write a dissertation on algorithmic complexity of certain scheduling problems. Thanks very much, Goran. All the troubles – the poor grades, the hobble to the final exam dodging a nail* – were certainly worth it!

A lot of Goran's papers, many of them OR papers on approximation algorithms and polyhedral theory, are available on his site. He also has an origami gallery.

* I overslept on the morning of the final exam. The exam was scheduled for 7:40 am, but I woke at 7:45 am. When I saw the clock, I screamed; my roommate woke with a start. As luck would have it, I’d left my bike at school the previous night. I had no time to brush. I had no time to wear my shoes either; so I chose an old pair of sandals, one of which incidentally had an iron nail inextricably lodged in it. I hobbled a mile to the exam, making sure I did not step on the portion of the sandal that had the nail. I was in my nightclothes, but mercifully at the time, my nightclothes didn’t differ much from what I wore during the day. I got to the exam at about 8:05 am, and did what I could in the time I had. It shall suffice to say that I somehow scraped through.