25.12 We stated in our discussion of online algorithms that some special classes of environments are amenable to online algorithms with constant competitive ratios. An example is shown in Figure 25.27, which shows a robot on the bank of a river. We assume that the robot has an exact position sensor. The robot is trying to find the bridge, which it knows is somewhere nearby, but is not sure how far and in which direction. Unfortunately, there is a thick fog and the robot cannot see the bridge unless it stumbles right onto it.

a. Describe an online algorithm for the robot that is guaranteed to find the bridge after a finite search, no matter where the bridge is.

b. Calculate the total distance traversed by the robot using your algorithm, and compute its competitive ratio.