留学生作业代写do not hesitate to contact me!
WeChat：lovexc60

Assignment 1
October 6, 2019
Question 1
(1) Given an algorithm to reach the fence when the distance d is known to
the robot.
Algorithm 1 Reaching fence knowing distance
1: The robot go straight d distance
2: The robot starts to search a circle until the robot find the fence
The robot moves like the figure1.1 shows. In line 1, it will take d time
to move forward. In line 2, it will take at most 2 ∗ π ∗ d = 2πd to search a
circle. Therefore, the running time will be O(d + 2πd) = O(d).
(2) Given an algorithm to reach the fence when the distance d is known
to the robot
Algorithm 2 Reaching fence unknown distance
1: repeat
2: The robot go forward by 2i distance
3: search a circle
4: until The robot reaches the fence
The robot moves like the figure1.2 shows. Each time the robot moves 2i
distance and search a circle.
Total distance that the robot moves forward is d.
This will take d + 2 × 2
1π + 2 × (21 + 22
)π + 2 × (21 + 22 + 23
)π + … + 2 × dπ
1
time to move and search circles.
We know that 21 + 22 + 23 + … + 2n = 2n+1 − 2 < 2
n+1. And we know
d = 2log2d
.
So, d + 2 × 2
1π + 2 × (21 + 22
)π + 2 × (21 + 22 + 23
)π + … + 2 × dπ
= d + 22π + (22 + 23
)π + (22 + 23 + 24
)π + … + 2dπ
= d + 22π + (22 + 23
)π + (22 + 23 + 24
)π + … + 2log2d+1π
< d + 23π + 24π + 25π + .. + 2log2d+1π
< d + 2log2d+2π = d + (22d)π = d + 4πd = O(d)
Therefore, the running time will be O(d).
robot d
robot2
… Figure1.1 Figure1.2 4