Latex辅导 | Algorithm 1 Reaching fence knowing distance

这个作业是使用Latex 解析伪代码

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
d
2
Question 2
1. vertices v and x are not adjacent; This statement is true.
2. edge 6 is incident with vertex w; This statement is true.
3. vertex x is incident with edge 5; This statement is false.
4. vertex w and eges 5 and 6 form an induced subgragh of G; This statement is false.
5. vertex x has degree 2. This statement is false, vertex x has degree 3.
Question 3
Firstly, we need to prove that students receive different grades in the both
classes are independent.
We know that the probability of a student receiving a grade in a class is 1
k
,
then the probability of a student receiving different grades in the both classes
is1 ∗
k−1
k =
k−1
k
Now, given the probability that studenta receive different grades in both
class is Pstudenta
(Ai 6= Bi) = 1 ∗
k−1
k
, then the probability that studentb is
P(Pstudentb
(Ai 6= Bi)|Pstudentb
(Ai 6= Bi))
=
Pstudentb
(Ai6=Bi)
T
Pstudenta
(Ai6=Bi)
Pstudenta
(Ai6=Bi)
= Pstudentb
(Ai 6= Bi)
3
=
k−1
k
So, students receive different grades in the both classes are independent.
Assume
xi(A student receives the same grade in the both class) = (
1 ifAi = Bi
0 ifAi 6= Bi
Let Y =
Xn
i=1
xi
The probability that some student receives the same grade in both tests
is P(Y > 0) = 1 − P(Y = 0)
P(Y = 0) = Yn
i=1
P(xi = 0)
=
Yn
i=1
P(Ai 6= Bi)
=
Yn
i=1
k − 1
k
= (k − 1
k
)
n
P(Y > 0) = 1 − (
k−1
k
)
n
Question 4
4
The first pair of graphs are isomorphic. s ↔ +, p ↔ ×, q ↔ −, t ↔=,
r ↔ ÷.
The second pair of graphs are not isomorphic. Because in first graph, the
two nodes 5 and 6 which degree is 3 are adjacent. But in the second graph,
the two nodes e and g which degree is 3 are not adjacent.
Question 5
1. If two graghs are isomorphic, must they have the same degree sequence?
Yes. Suppose we have two graphs G1 = (V, E) and G2 = (V
0
, E0
) which
are isomorphic. Let V = {v1, v2, v3, …, vn} and V
0 = {u1, u2, u3, …, un}.
We can get the degree sequence of G1 in ascending order which can
be represented as d1, d2, d3, …, dn (with repeating). If two graphs are
isomorphic, we must get a same degree sequence of G2.
2. If two graphs have the same degree sequence. must they be isomorphic?
No. Using the second pair of graphs in question 4 can provide an
example to prove this. The two graphs have the same degree sequence
in ascending order, which are {2, 2, 2, 2, 3, 3, 3, 3} and {2, 2, 2, 2, 3,
3, 3, 3} . But they are not isomorphic.
Question 6
5
Algorithm 3 Find the minimum value in a ring
1: Assume there are 1…n nodes in the ring, let them be node1,
node2,…,noden
2: node1 has two neighbor which are noden and node2
3: Let node1 be the initiator and send the value it contains and its identifier
to its neighbor node2
4: for node ∈ {node2, …, noden} do
5: Compare its own value and the value it receives
6: if its own value is lager than the value it receives then
7: Send the value it receives and its identifier to its neighbor who
does not send value to it
8: else
9: Send its own value its identifier to its neighbor who does not send
value to it
10: loop finished and node1 receives the minimum value.
Using a example graph in class note:
The cost of this single-initiator protocal is n because each node in the
ring send value once and there are n nodes in the ring.
Proof of Correctness
Each node has two neighbors. Since the loop starts from node2 and each
node will receive the identifier of the node that send value to it, this ensures
that the value can be sent to the neighbor who does not send the value.
Assume the minimum value vmin is in nodei
.Now nodei receives a value
from its neighbor nodei−1. Since nodei has value vmin, vmin will be sent to
nodei
’s neighbor nodei+1. Because vmin is the minimum value, it will be sent
by nodei+1, nodei+2, nodei+3,…, noden without any change. noden will send
6
vmin to node1 and the minimum value is found.
Question 7
1. What is the expected number of unpecked chicks? From the question
we can know that the probability that a chick is pecked by another chick
is 1
k
, so the probability that a chick is unpecked by another chick is k−1
k
.
Therefore, the probability of a chicks are unpecked by all chicks is
Y
k
i=1
P(a chick is unpecked by another chick)
=
Y
k
i=1
k − 1
k
= (k − 1
k
)
k
So, the expected number of unpecked chicks is
E[X] = Xn
i=1
(
k − 1
k
)
k
= n(
k − 1
k
)
k
2. What is the expected number of unpecked chicks in the complete graph
Kn, asymptotically in n?
From the question we can know that the probability that a chick is
pecked by another chick is 1
n−1
, so the probability that a chick is unpecked by another chick is n−2
n−1
.
Therefore, the probability of a chicks are unpecked by all chicks is
nY−1
i=1
P(a chick is unpecked by another chick)
=
nY−1
i=1
n − 2
n − 1
7
= (n − 2
n − 1
)
n−1
So, the expected number of unpecked chicks is
E[X] = Xn
i=1
(
n − 2
n − 1
)
n−1
= n(
n − 2
n − 1
)
n−1
To prove the expected number asymptotically in n:
we need to check if at n → +∞(we ignore −∞ here) n(
n−2
n−1
)
n−1 behaves
as a line. Let say the line is f(n) = an + b.
To find a:
limn→∞
n(
n−2
n−1
)
n−1
n =
1
e To find b:
limn→∞
(n(
n−2
n−1
)
n−1 −
1
e
n) = −
1
2e
Therefore the slant asymptote5 is f(n) = 1
e
n −
1
2e
, we can say that the
expected number asymptotically in n.
Question 8
1. Given an assignment of identifiers to the nodes for which O(n
2
) messages are sent.
Assign unique identifiers to the nodes with descending order (from the
first node v1to last node vn). Then each node except v1, will received
an identifier that is lager than its own identifier. So, each node except
v1, has to pass the received identifier message through. Since there are
n identifiers, each node except the node has the maximum identifier,
will send n messages. The total message sent will be O(n
2
).
2. Given an assignment of identifiers to the nodes for which only O(n)
messages are sent.
Assign unique identifiers to the nodes with ascending order (from the
first node v1to last node vn). Then, each node will send there a message
8
its identifier once, which takes O(n) message complexity. Also, all the
node except vn will pass the message with the highest identifier (from
vn) once, which take O(n − 1) message complexity. The total message
complexity is O(n) + O(n − 1) = O(n).
Question 9
Algorithm 4 share bike
1: Input : u, v, d
2: dbiker1 ← 0, dbiker2 ← 0, dbiking ← 0
3: biking(dbiker1, u)
4: walking(dbiker2)
5: while dbiker1 6= d AND dbiker2 6= d do
6: t1 =
d−dbiker1
1
. t1 is time for biker1 finish remaining trip by walking
7: t2 =
dbiker1−dbiker2
1
. t2 is time for biker2 catch up biker1 current location
8: t3 =
d−dbiker1
v
. t3 is time for biker2 finish remaining trip by biking
9: if t1 = t2 + t3 then . if not satisfy the condition biker1 keep biking
10: dbiking = dbiker1
11: walking(dbiker1)
12: if dbiker2 = dbiking then . if not satisfy the condition biker2 keep walking
13: biking(dbiker2, v)
Since the condition two bikers have the same biking speed in question 1
is include in question 2’s condition u ≥ v > 1, we only need one algorithm.
When two bikers and the bike arrive at the same time, the trip time will
be minimized.
Proof of Correctness:
Line 6 to 13 ensures that the two bikers will change state to walking/biking
at correct location. Since only they change state when t1 = t2 + t3 can
ensure they arrive at the same time.Changing state to walking/biking at this
location ensures t1 = t2 + t3. So, this algorithm is correct.
9
Question 10
1
0 0
when n = 1, node v has only 1 packet which is smaller than its degree
(which is 2). Therefore, node v wait, and its two neighbors who have 0
packet also wait. It reaches a state in which the number of packets at all
nodes remains unchanged.
2
0 0
0
1 1
when n = 2, node v has 2 packet which is equal to its degree (which is 2).
Therefore, node v send packets to its two neighbors. After first sending, the
number of packets that v has is 0, and node v’s two neighbors have 1 packet,
respectively. Since all the number of packets at all nodes is small than their
degree (which is 2), all nodes wait and it reaches a state in which the number
of packets at all nodes remains unchanged.
3
0 0
1
1 1
When n = 3, node v send packets to its two neighbors. As the above
picture shows, after first sending, the number of packets that v has is 1, and
its two neighbors have 1 packets, respectively. Since each node has 1 packets
10
which small than their degree (which is 2), all nodes wait and it reaches a
state in which the number of packets at all nodes remains unchanged. (which
is 1).
4
0 0
2
1 1
0
2 2
2
1 1
0
2 2
Step 1 Step 2 Step 3 Step 5 Step 4 Change between two configurations (Step 4 and 5)
…
When n = 4, node v send packets to its two neighbors. As the above
picture shows, after first sending, the number of packets that v has is 2, and
its two neighbors have 1 packets, respectively. Since the neighbors of node
v has 1 packets which small than their degree (which is 2), they wait. Node
v now has 2 packets, it keep sending. After second sending, node v has 0
packets and its two neighbors have 2 packets. Now, node v start waiting and
its two neighbors send packets. After third sending, Node v has 2 packets
and its neighbors have 1 packet. Node v sends packets and its neighbors wait.
After the fourth sending, node v has 0 packets and its two neighbors have 2
packets. Now, node v start waiting and its two neighbors send packets. It is
obvious that when n = 4, the number of packets of node v change between
2 and 0, and the number of packets of node v’s neighbors change between 1
and 2. This configuration will never stabilize.
11
5
0 0
3
1 1
1
2 2
3
1 1
1
2 2
change between two configuration (Step 4 and 5) …
Step 4 Step 5 Step 1 Step 2 Step 3
When n = 5, node v send packets to its two neighbors. As the above
picture shows, after first sending, the number of packets that v has is 3, and
its two neighbors have 1 packets, respectively. Since the neighbors of node
v has 1 packets which small than their degree (which is 2), they wait. Node
v now has 3 packets, it keep sending. After second sending, node v has 1
packets and its two neighbors have 2 packets. Now, node v start waiting and
its two neighbors send packets. After third sending, Node v has 3 packets
and its neighbors have 1 packet. Node v sends packets and its neighbors wait.
After the fourth sending, node v has 1 packets and its two neighbors have 2
packets. Now, node v start waiting and its two neighbors send packets. It is
obvious that when n = 5, the number of packets of node v change between
3 and 1, and the number of packets of node v’s neighbors change between 1
and 2. This configuration will never stabilize.
6
0 0
4
1 1
2
2 2
When n > 5, for example n = 6, node v send packets to its two neighbors.
As the above picture shows, after first sending, the number of packets that v
has is 4, and its two neighbors have 1 packets, respectively. v keeps sending
12
and its neighbors which both have 1 packets keep waiting. After second
sending, the number of packets that v has is 2, and its two neighbors have
2 packets, respectively. Since each node has 2 packets which equals to their
degree (which is 2), all nodes keep send packets to it neighbors and it reaches a
state in which the number of packets at all nodes remains unchanged. (which
is 2).
From above observation, we can know that when initial configuration
1 < n < 4, after node v send packets, the number of all nodes packet will be
smaller than their degree. They keep waiting forever and it reaches a state
in which the number of packets at the nodes remains unchanged.
When initial configuration n > 5, the number of packets at node v will never
lower than the degree of node v. While node v’s neighbors firstly have 2 packets, the number of packets at node v still equal or higher than the degree
of node v. Therefore, all nodes keep sending each of its neighbors 1 packets
and reaches a state in which the number of packets at the nodes remains
unchanged.
13