DSC 40B – Final Exam August 3, 2019 Name: SOLUTIONS PID: By signing below, you are agreeing that you will behave honestly and fairly during and after this exam. You should not discuss any part of this exam with anyone enrolled in the course who has not yet taken the exam (this includes posting questions about the exam on Piazza!) Signature: Name of student to your left: Name of student to your right: (Write “N/A” if a wall/aisle is to your left/right.) Instructions: • Write your solutions to the following problems in the boxes provided. • The last two pages are scratch paper; you may remove these. • No calculators are permitted, but a cheat sheet is. • Write your name or PID at the top of each sheet in the space provided. Tips: • Show your work to receive partial credit. • Look through the entire exam before starting. • Make good use of all assumptions given to you. (Please do not open your exam until instructed to do so.) Problem 1. (16 points) For the following problems, recall that (u; v) is a tree edge if node v is discovered while visiting node u during a breadth-first or depth-first search. Assume the convention that a node’s neighbors are produced in ascending order by label. a) Suppose a breadth-first search is performed on the graph below, starting at node 1. Mark every BFS tree edge with a bold arrow emanating from the predecessor. 1 2 3 4 5 6 7 8 9 b) Suppose a depth-first search is performed on the graph below, starting at node 1. Mark every DFS tree edge with a bold arrow emanating from the predecessor. 1 2 3 4 5 6 7 8 9 2 PID or Name: c) Fill in the table below so that it contains the start and finish times of each node after a DFS is performed on the above graph using node 1 as the source. Begin your start times with 1. Node Start Finish 1 1 18 2 2 17 3 3 16 4 6 7 5 5 14 6 4 15 7 8 9 8 10 13 9 11 12 3 Problem 2. (24 points) For each of the following statements write T if the statement is true, and F if the statement is false. a) T If f1(n) = O(g1(n)) and f2(n) = O(g2(n)) then f1(n)f2(n) = O (g1(n) g2(n)). b) F Because mergesort takes (n log n) time compared to selection sort’s (n2), mergesort(arr) will execute in less time than selection_sort(arr), no mat- ter what the input arr is. Solution: While mergesort has better asymptotic time complexity, this only means that mergesort is faster for n large enough. In fact, for small inputs, selection sort is typically a little faster. c) T If the input graph G = (V;E) is a tree, the time complexity of depth-firstsearch is (V ). Solution: In general, the time complexity of DFS is (V + E). If G is a tree, jEj = jV j 1, so the time complexity becomes (V + (V 1)) = (V ). d) T If a graph G has two connected components, there must exist a pair of distinct nodes u and v such that adding the edge (u; v) to G would result in a graph with one connected component. e) T An undirected graph with n nodes can have at most n(n 1)=2 edges. f) T Suppose that T is a minimum spanning tree of a weighted graph G, and G0 is the weighted graph obtained by increasing the weight of each edge in G by exactly one. Then T is also a minimum spanning tree of G0. Solution: Increasing the weight of each edge by one increases the total weight of a spanning tree by jEj. Since the total weight of each spanning tree is increased by the same amount, an MST of the original graph is still an MST of the new graph. g) T Suppose that a breadth-first search is run with node u as the source. Let v and w be two nodes. If the shortest path from u to v is (strictly) shorter than the shortest path from u to w, then u is added to the queue before w. 4 PID or Name: h) T Suppose a full DFS is used to compute finish times. If v is reachable from u, itis possible for the finish time of v to be larger than the finish time of node u. Solution: Consider this graph: v w u Start a DFS at node w. The DFS will then visit node u, then node v. The finish time of node u will be 2, while the finish time of node v will be 5. But v is reachable from u. 5 Optionally provide reasoning here to earn credit if your above answer(s) is (are) incorrect: 6 PID or Name: Problem 3. (20 points) Here is a simple way of clustering a weighted, undirected graph G = (V;E; !). Given a real number t, place two nodes u and v in the same cluster if (and only if) there is a path between u and v along which every edge has weight t. For instance, consider the graph below: 1 2 3 4 5 6 3.41.3 2.7 0.3 0.90.5 0.72.1 If t = 1, there are three clusters: f1; 2g, f4; 5; 6g and f3g. If t = 2, there are two clusters: f1; 3g and f4; 5; 6g. And if t = 3, there is one cluster containing all of the nodes. Design an algorithm which returns the clusters given an input graph, a weight function, weights, and a threshold t. Your algorithm should take (V + E) time. To receive full credit, your algorithm should not modify the graph or create a copy of it. Provide pseudocode (or Python). 7 Solution: A BFS or DFS can be used to find the clusters. An unmodified BFS started at node u will find all nodes reachable from u. We wish to find all nodes reachable from u along paths whose edges have weight t. One simple way to do this is to delete all edges of weight > t from the graph and run a full BFS, but the problem asked us not to modify the graph or create a copy of it. We can achieve the same effect by having BFS “ignore” the edges whose weight is above the threshold, essentially acting as if they are deleted. 1 def cluster(graph, weights, t): 2 status = {‘undiscovered’ for node in graph.nodes} 3 clusters = [] 4 for node in graph.nodes: 5 if status[node] == ‘undiscovered’: 6 cluster = bfs_cluster(graph, node, weights, status, t) 7 clusters.append(cluster) 8 9 def bfs_connected_components_with_threshold( 10 graph, source, weights, status, t): 11 cluster = [source] 12 pending = deque([source]) 13 status[source] = ‘pending’] 14 while pending: 15 u = pending.popleft() 16 for v in graph.neighbors(u): 17 if status[v] == ‘undiscovered’ and weight(u, v) <= t: 18 pending.append(v) 19 status[v] = 'pending' 20 cluster.append(v) 21 status[u] = 'visited' 22 return cluster This is essentially the same code as in full BFS, but a node v is “discovered” and added to the pending queue only if the edge from the potential predecessor to v has weight t. 8 PID or Name: Problem 4. (15 points) Describe an algorithm for computing a maximum spanning tree. A maximum spanning tree of a weighted graph G is a spanning tree of G with largest total edge weight. You do not need to provide pseudocode, and you can use the algorithms discussed in class without needing to write their code. Unlike the previous problem, you may modify the graph or create a copy of it. Solution: Create a copy G0 of the graph, G, in which the weight of each edge is the negative of the original edge weight. A minimum spanning tree of G0 will be a maximum spanning tree of G. Therefore, a maximum spanning tree of G is given by running Kruskal’s algorithm on G0. Or: run Kruskal’s in “reverse” by sorting the edges in descending order by weight, and adding an edge to the tree if it connects two previously disconnected nodes. 9 Problem 5. (20 points) For each of the following, state the most precise possible bound on the time complexity using asymptotic notation. a) What is the time complexity of this code? State your answer in terms of n. for i in range(n): for j in range(i, n): print('Hello') (n2) b) What is the time complexity of this code? State your answer in terms of n. def foo(n): if n == 1: return 2 return foo(n-1)*foo(n-1) (2n) c) What is the time complexity of this code? State your answer in terms of n. def bar(n): x = 1 total = 0 while x < n: total += x x = 2 * x (log n) d) The time complexity of full breadth-first search when run on a graph represented using an adjacency matrix. State your answer in terms of the number of nodes jV j and/or the number of edges, jEj. (V 2) 10 PID or Name: Problem 6. (20 points) In the following problem, we will use a slight variant of the merge function seen in mergesort. It accepts two sorted lists, left and right, and merges them into on e sorted list. The only difference between this and the merge used in mergesort is that this function returns its result in a new array rather than modifying an input array. def merge(left, right): m = len(left) + len(right) output = [] left.append(float('inf')) right.append(float('inf')) for i in range(m): print('Hello') if left[0] < right[0]: output.append(left.pop(0)) else: output.append(right.pop(0)) return output Suppose collection is a list of k sorted lists, each of them containing n elements. The code below performs a k-way merge by combining the k sorted lists into one large sorted list with k n elements: def k_way_merge(collection): """Assume collection is not empty.""" k = len(collection) n = len(collection[0]) left = collection[0] for i in range(1, k): right = collection[i] left = merge(left, right) 11 a) Fill in the box so that the following loop invariant is true: After the th iteration of the for-loop in k_way_merge, left contains ( + 1) n elements. b) Observe that the merge function contains a line which prints 'Hello'. Exactly how many lines are printed in total during one call to k_way_merge? State your answer in terms of k and n. Solution: When merge(left, right) is called, it prints a number of lines equal to len(left) + len(right). On the first iteration of the for-loop, merge is called with two arrays of size n, and therefore prints 2n lines. On the second iteration of the for-loop, left contains 2n elements, while right contains n elements. Hence merge prints 3n lines. On the third iteration, left contains 3n elements, and right contains n elements. Hence 4n lines are printed. On the th iteration of the for-loop, it is apparently the case that n + 1 lines are printed. The for-loop makes k 1 iterations, and so the total number of printed lines is: 2n+ 3n+ 4n+ : : :+ (k 1 + 1)n = 2n+ 3n+ : : :+ k n = n(2 + 3 + : : :+ k) The sum of 2 + 3 + : : :+ k is k(k + 1)=2 1. Hence the answer is n [k(k + 1)=2 1] = n k(k + 1) n 2 Before turning in your exam, please check that your name is on every page. 12
