Computer Science > QUESTIONS & ANSWERS > CS 331: Algorithms and Complexity (Fall 2018) Unique numbers: 51480, 51485, 51490, 51495 (All)

CS 331: Algorithms and Complexity (Fall 2018) Unique numbers: 51480, 51485, 51490, 51495

Document Content and Description Below

Problem 1: Short Answers Section For this section, restrict answers to no more than a few sentences. Most answers can be expressed in a single sentence. Unless otherwise stated, no proofs are necess... ary for this section. (a) (1 pt) True or false: When run on a tree, DFS takes much longer than BFS because it must reach a leaf before it can backtrack. Answer: False. (b) (2 pts) Let T be a BFS tree of a graph G, and let x and y be nodes in T, in layers Li and Lj respectively. Furthermore, assume the edge (x, y) exists in G. What is the maximum difference between i and j? Answer: The maximum difference is 1. This is the content of Theorem (3.4) in Kleinberg & Tardos. (c) (2 pts) True or false: BFS and DFS will always explore every node in a graph. If true, explain why. If false, provide a counterexample. Answer: False. Counterexample: the graph with two nodes and no edges. (d) (2 pts) Consider an undirected graph G = (V, E) where |V | = n. What is the maximum possible value of |E| in terms of n? Briefly explain your reasoning. Answer: |E| = 1 2 (n 2 − n). Each node can have n − 1 edges coming off of it to another node, and there are n nodes, so n(n − 1) edges. We divide by 2 to account for the fact that an edge from u to v is the same as an edge from v to u. (e) (1 pt) Repeat the above question, but assuming that G is a directed graph. Answer: |E| = (n 2 − n). Same logic as above, but edges are directed, so we no longer need to divide by two (i.e. u → v is different from v → u) (f) (2 pts) Consider an undirected graph G = (V, E). Construct its directed equivalent G0 = (V 0 , E0 ) as follows: • V 0 = V • For each pair of nodes x, y in V with (x, y) ∈ E, add the edges (x, y) and (y, x) to E 0 . Note that G0 is a directed graph, even though G was undirected. Now suppose that that two particular nodes, u and v, have a path between them in G. Does this mean that they are necessarily strongly connected in G0 ? If not, provide a counterexample. Answer: They are strongly connected in G’. The following is a proof of this fact (note: you did not need [Show More]

Last updated: 2 years ago

Preview 1 out of 5 pages

Buy Now

Instant download

We Accept: