1) Which statement below is correct?
&& A bipartite graph is two colorable
Copyright By PowCoder代写 加微信 powcoder
2) The chromatic number of a graph is at most d+1, where d is
&& the max degree of a vertex of the graph
3) Procedure First Free in the distributed graph coloring algorithm assigns to a node v
&& the smallest admissible color not used by any of its neighbors
4) Algorithm Slow Tree Coloring colors a vertex v of a tree
&& synchrously for all nodes other than the root, a node waits to receive a message from its parent
5) Consider the distributed coloring algorithm REDUCE. While node v has an uncolored neighbor with
&& higher identifier it sends “undecided” to all its neighbors
6) The assertion: “In any coloring, of a graph the set of nodes of a given color forms an independent set” is
&& Always true
7) Consider the two pairs of graphs below.
Which of the following statements is correct?
&& Left pair is isomorphic, Right pair is not isomorphic
8) A graph G=(V,E) with n nodes and max degree d has been assigned pairwise distinct node and vertex labels, respectively. The worst case minimum number of bits required per node to represent the labels is
&& O(\log n) bits for node labels and O(d \og d) bits for port labels
9) The radius growth leader election algorithm in a ring of n nodes satisfies:
&& message complexity O(n\log n), running time O(n )
10) Assume that the identifiers of the n nodes of a ring are chosen from the set 1,2,… ,n (in arbitrary order). The bit complexity of the clockwise leader election algorithm (discussed in class) is
&& O(n^2 \log n)
11) Assume the nodes of a n-node (n \geq 2) synchronous ring are anonymous.
&& A leader can never be elected.
12) In the radius growth algorithm for leader election nodes that survive a round
&& nodes that survive update their probes with TTL \leftarrow 2 TTL
13) Any comparison based leader election algorithm in a n-node ring network requires
&& \Omega (n \log n) messages sometimes
14) In the variable speed algorithm on a ring, a token with value v travels
&& at the speed of one message transmission per 2^v rounds
15) Consider the randomized leader election algorithm on an n-node ring. Which of the statements below is false?
&& each processor must draw \log^2 n random bits
16) Consider a synchronous, oriented ring of size n>4, where n is odd and known to the nodes. Assume that 3 consecutive nodes have the same identifier 0 and the remaining n-3 the same identifier 1. Is leader election possible?
&& Yes, a leader election algorithm is possible
17) Two nodes u, v are connected with a link. In synchronous rounds: each node flips a fair coin randomly and independently. What is the probability that after k rounds the two nodes have produced the same sequence (in the order the bits were generated) of k bits?
18) Consider an synchronous, anonymous bidiectional ring of n (n \geq 3) nodes. Initially exactly one node sends the same bit to both its neighbours. A node receiving a message forwards it in the opposite direction from the direction it is received. The integer n is even if
&& a node receives a bit from both its neighbours at the same time
19) Consider the pirate treasure problem (discussed in class) with five children one of which (unknown to the pirate and the rest of the children) is always a liar. (Assume the treasure is located at the southernmost point on the perimeter of the cycle but this is unknown to the children.)
What is the minimum number of children to which the pirate should reveal the location so that the treasure can be located?
20) Consider a port labeling in a graph. Which statement is correct?
&& the number of ports at a node equals its degree
21) The ports in a distributed network correspond to the
&& links adjacent to a node
22) A pert function on graph (V,E) gives rise to a total of
&& exactly 2 |E| (vertex, port) pairs
23) A round in a distributed algorithm consists of the following three operations
&& receive; compute; send;
24) Which of the claims below is false?
&& the ring graph of 2n+1 nodes has a min vertex cover of size n
25) Which of the following statements is correct for the graph below?
&& the set 1,3,6,8 forms a min vertex cover
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com