You are facing a high wall that stretches infinitely in bothdirections. There is

Question

You are facing a high wall that stretches infinitely in bothdirections. There is a door on the wall at a finite distance butyou do not know how far away and in which direction. It is pitchdark, but you have a very dim lighted candle that will enable youto see the door when you are right next to it.
*Devise and algorithm that enables you to find the door. *Assume n is the number of steps that you would have taken ifyou knew where the door is and walked directly to it. Calculate theexact number of steps you walk if you follow your algorithm as afunction of n. Try to find the best algorithm (requires smallest number of steps.)
*Devise and algorithm that enables you to find the door. *Assume n is the number of steps that you would have taken ifyou knew where the door is and walked directly to it. Calculate theexact number of steps you walk if you follow your algorithm as afunction of n.

Explanation / Answer

Start by taking 1 step to your left. Turn around and take 2 stepsto your right. Turn around and take 4 steps back in the originaldirection. Turn around and take 8 steps back to your right. Turnaround and take 16 steps to your left, etc. Now, let's say you findthe door 9 steps to the left of where you started. You can nowcompare the two. Had you known where the door was you would havewalked 9 steps. Instead, you walked 13 + 8 + 4+ 2+ 1 = 29 steps.However this is less than 4 times the ideal. In this case, n is 9(the amount you should have walked). Now imagine the door was 5steps to the right of where you started. In this case you shouldhave walked 5 but you walked 8 + 4 + 2 + 1 = 15 steps (since youdidn't find it til the time you walked 8 steps the right). This isless than 4 times the ideal amount. By showing that by using thissystem, your total walk time is always less than 4 times the idea,you are showing that your system works in 4n, which is an O(n)algorithm.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---