# 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