Friday November 30
To sign up for a problem, send email to alubiw "at" uwaterloo.ca.
I will update this list to indicate the first person who signs up.
- [Yun Lu]
A robot is looking along a wall for a door that is distance d away but
might be to the left or to the right. In Algorithm 0 the robot goes i
steps right and back, then i steps left and back, for i = 1, 2, ...
Show that the distance travelled is Theta(d^2).
-
[James Rupke]
For the same problem, Algorithm 1 doubles the distance the robot goes
each time. (1 step left and back, 2 steps right and back, 4 steps left and
back, . . . ) Suppose 2^i <= d < 2^{i+1}. Analyze the distance travelled,
and show that it is at most 9d.