程序代写代做代考 AI go graph algorithm Distributed Computing, COMP 4001 1

Distributed Computing, COMP 4001 7
Expectation Form of the Probabilistic Method
• Equation (1) is a special cas of Markov’s inequality wchich I
states that
Pr[X > kE[X]]  1 k
• Therefore using Equation (1) if we want to prove that
Pr[X =0]>0 it is enough to prove that
E[X] < 1. Exercise Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 8 Traversals Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 9 Explorations • Graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. E.g., – BFS – DFS 993 than as – typically a sequence of port labels that it must follow from node to node) which is used to traverse the graph. • However, the program used may depend on the starting node. Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Breadth first Death n search uIt . • Used in Search and Exploration. • Each starting node is equipped with a program Distributed Computing, COMP 4001 10 ofloibeds Universal Traversals • A sequence is universal for graphs with n vertices if for every graph and every start vertex, the walk defined by the (same) sequence will visit every vertex in the graph. • Can you produce a universal traversal program that will work for every graph and every starting node of the graph? • To produce a walk defined by a sequence, we need some notion of graph labeling. – For each vertex u, label the edges adjacent to u (ports) from 1 to deg(u) (in fact any numbering will do). – This is what we defined as port labelings! • Then a sequence is a string of edge labels which determines some walk through the graph. Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 11 Universal Traversals on Labyrinths • A robot is placed in a labyrinth in a n ⇥ n square grid. • It runs a program: a sequence of commands of the form N(orth), S(outh), E(ast), W(est), go ⇒ ' • labels -4¥ Port • As an example consider the program NESWEW which is given to every node. • A robot has the sequence “NESWEW” and starting at a node makes movements following the sequence of labels. - Evangelos Kranakis, Carleton University, SCS (October 31, 2020) fixed W EHswμr Follow a trajectory determined by t h e sequence of labels given to m e . . Distributed Computing, COMP 4001 12 Universal Traversals • In addition to external walls on the whole perimeter, walls are also placed between cells. • Executing each command, the robot moves in the prescribed direction if possible (and does nothing when there is a wall in this direction). E.g., NESWEEEW Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 13 • We can show that Universal Traversals not {Theorem 1 (Universal Traversals) For any n, there exists a program that works correctly for all labyrinths of size at most n ⇥ n (independently of the positions of walls inside the square and the robot’s initial position). • “Works correctly” means that the robot visits all reachable cells. • To solve the traversal problem, we prove that a suciently long random program will work with positive probability. • We will do this using the union bound. - Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 14 Preorder Traversals (1/2) • For each n ⇥ n labyrinth, there is a program of size 4n4 that works for it, as each cell is reachable in at most 4n2 steps (round-trip) and there are at most n2 admissible cells. • To prove this note that for each starting cell there is a spanning tree reaching all the n2 cells of a given labyrinth, think of it as a distributed network. too I • Assign ports to each vertex (edge labels associated to the edges connected) H D BC EFG A J Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 15 Preorder Traversals (2/2) • Using a pre-order traversal of this spanning tree (which has length at most 4n2) every cell will be visited in at most 4n2 v steps (round trip). For every vertex me how a traversal 41 labels of n 2×4 ' n • Therefore, a random~program of size N = 4n4 will work with probability at least ✏ = (1/4)4n4 and fail with probability at most 1 ✏. Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 16 Universal Traversals • Select among such programs of size N = 4n2 independently and uniformly at random. times – By independence, a random program of size 2N will fail with probability at most (1 ✏)2 – More generally, a random parogram of size kN will fail with probability at most (1 ✏)k. • Now for each k concatenate k such programs: ~- P1P2 ···Pk f they • This probability is computed for a fixed labyrinth L. • Let FL be the event that a program of size kN fails for the labyrinth L. • It follows from the above that Pr[FL]  (1 ✏)k. Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 17 Universal Traversals • Now take the union SL FL, where L runs over all labyrinths. As a consequence, Pr"[FL#  XPr[FL] LL 0.
• Therefore for k suciently large a random program of size kN
works for all labyrinths with positive probability. • Therefore such a program must exist!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)

Distributed Computing, COMP 4001 19
Eciency of Universal Traversals
• How about the length of the sequence of port labels?
– Can we construct a universal traversal sequence of polynomial length in polynomial time (in the size n of the graph)?
• How about eciency?
– Can we give an algorithm to construct a universal traversal
sequence?
• Can we make the construction distributed? to
It is known how
give
algorithmic proofs of this but they a re quite complex!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)

Distributed Computing, COMP 4001 20
Universal Traversals on Graphs
• The Universal Traversal theorem holds on graphs of a given size n.
• Instead of N,S,E,W used in n⇥n grids one now uses ports and port-labelings.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)

Distributed Computing, COMP 4001 21
Exercisesa
1. The traversal of the labyrinth was based on a sequence that was provided to the robot and which the robot must follow. Consider the situation where the robot constructs the sequence “on the fly”: looks at the surrounding environment and based on what it sees makes its next move according to some rule. This will be a local algorithm and the moves of the robot depend on the environment. Will such an algorithm perform a successful traversal?
2. (?) Use the probabilistic method to prove a Universal Traversal theorem on graphs of a given size.n. Hint: Instead of N,S,E,W used in n⇥n grids one now uses ports.
Consider a set of points in the plane. Form n sets
A1,A2,…,An on the plane each of which has k points.
aNot to submit.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)

Distributed Computing, COMP 4001 22
The sets are arbitrary and may share points. Assume that n < 2k. Show that If n < 2k then it is possible to color each point red or blue in such a way that every set Ai has both colors. Hint: Color each of the n points independently choosing red or blue with equal probability and use the probabilistic method. 3. A certain commodity is sold with two lottery tickets, a and b, for Prize A and Prize B, respectively. Suppose the winning probability for A and that for B are both 2/3. Show that there Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 23 must exist a commodity with two winning tickets.b 4. (?) The sets S1,S2,...,Sk are di↵erent subsets of a set S that has 2n elements. {S1, S2, . . . , Sk} is called a Sperner familyc if Si 6✓ Sj, for all i 6= j. Use the probabilistic method to prove Spener’s theorem, namely “If {S1, S2, . . . , Sk} is a Sperner family then k  2n.” For the proof, follow the steps below. n (a) Consider the following process: We start with the emptyset and add random elements of S one by one until (after 2n steps) we get the whole set S. For a fixed subset A ⇢ S of size a show that A will appear during this process with probability Pr[A] = 1/2n. value of Xi is equal to 1 if the given set Si appears during the process, otherwise, it is equal to 0. Show that the bNote that the conclusion is derived without using event dependence. cSperner families have applications in Cryptography and elsewhere. a (b) Consider k random variables X1, X2, . . . , Xk so that the Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 24 expected value of Xi is 1/2n, where si is the number of si elements in Si, (c) Now, consider the random variable X = X1 +X2 +···+Xk. Show that this sum is less than 1 in expectation. Evangelos Kranakis, Carleton University, SCS (October 31, 2020) Distributed Computing, COMP 4001 25 References • Alon, N., Spencer, J. H. (2004). The probabilistic method. John Wiley & Sons. • Hirokasu Iwasawa, Using Probability to Prove Existence, Mathematical Intelligencer, Volume 34, Number 3, 2012. • Mathematical Intelligencer Volume 20, Number 4, 1998 • Aleliunas, R. Karp, R. Lipton, R. Lovasz, L. Racko↵, C. Random walks, universal traversal sequences, and the complexity of maze problems. 20th Annual Symposium on Foundations of Computer Science (FOCS 1979): 218?223 Evangelos Kranakis, Carleton University, SCS (October 31, 2020)