You are facing a high wall that stretches infinitely in both directions. There i

ID: 3804678 • Letter: Y

Question

You are facing a high wall that stretches infinitely in both directions. There is a door in the wall, but you don't know how far away or in which direction. It is pitch dark, but you have a very dim lighted candle that will enable you to see the door when you are right next to it. Suppose n is the (unknown to you) number of steps between your initial position and the door. For both algorithms, the input is the high wall that stretches infinitely in both directions. For the output, you can simply return that the door is found. Remember, a complete answer includes an algorithm description, an algorithm, and an analysis.

(a) Give a O(n2) algorithm that enables you to reach the door.

(b) Give a O(n) algorithm that enables you to reach the door.

Explanation / Answer

Alogrithm
1. Define findDoor function for find the where is door or how much steps required
   define enum{wall, door, initial_pos};

2. pass arguments as wall , door, initial position
   define findDoor(wall, door, initial_pos )
       int i = 0
3. declare direction if move is in right direction and initial move
   int direction = 1
   int move = 0
4. increament the move
   int to = initial_pos + move

5. if found door at initial position then return initial position

   if initial_pos == door
       return initial_pos

6. while move till, not found door

   while True
       move = 2*i
       for __ in xrange(2)

   i) initial move from initial_pos
           for index, k in enumerate(wall[initial_pos + direction :to + direction : direction])

   ii) if found door , then return position with add moves and direction
       if k == door
                   return initial_pos + ( direction * index ) + direction
           direction *= -1
           to = initial_pos + move

   iii) if moving in right direction
       if direction == 1
               i+=1
           else
               return initial_pos - move

Navigate

You are faced with the decision of what to do with your cellular phone contract.

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

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You are facing a high wall that stretches infinitely in both directions. There i

Question

Explanation / Answer

Related Questions

Navigate