Homework 20

Due Friday, May 1 at 7:00 PM. Please refer to the homework policy here.


In what feels like an eternity ago, suppose you are going to the graduate student social thingy on the 3rd floor of Lawson. You can get to the third floor by either an elevator the stairs. The elevator takes 15 seconds (once you get in), while the stairs take 2 minutes. Your goal is to get up to the third floor as fast as possible before the donuts are all taken.

You press the button to go up for the elevator. You don't know how long it will take to come down. Do you wait or take the stairs?

  1. Suppose you knew how long the elevator would take to arrive. What is the optimal choice, based on this wait?
  2. Now suppose you don't know how long the elevator would take. Design a deterministic algorithm that is competitive with the optimal solution (where you know how long the elevator would take). I believe a 15/8 competitive ratio is possible.
  3. Suppose you have a quarter in your pocket, which lands heads or tails with equal probability. You can toss the coin once every 15 seconds. Design a randomized algorithm with a (slightly) better competitive ratio than the deterministic one from question 2.1


1 I actually don't know what the best competitive ratio would be, and I'm interested to see what everyone comes up with.