CS170 , Midterm #2, Fall 1994CS170, Fall 1994Midterm #2Professor VaziraniThere are 4 independent problems of equal weight. You need to discard one problem of your choice and dothe other three. You will be graded on these three. (If you turn in something for all problems, only the firstthree will be graded)When using material from lecture, textbook or discussion session, you do not need to repeat it entirely. It issufficient to refer to it clearly.Please start each new problem on a new sheet of paper. Write your name on each sheet of paper. On the firstpage, write you ID number and which section you are enrolled in (AM or PM) (1 point)Problem #1 - Dynamic Minimum Spanning Tree (35 points)Let G = V(V,E) be an undirected graph, with a weight function w(e) &gt 0 for each edge e &lt E. Let T be aMinimum Spanning Tree (MST) of G for this weight function. We consider the problem which takes as inputa minimum spanning tree T of G and a request "Decrease the weight of edge ei down to w'(ei)", where w'(ei)&lt w(ei), and outputs the new minimum spanning tree T' of G with this new wieght.1.1 Example. (5 points) For example, consider the graph G below. Draw a minimum spanning tree T of G. Ifthe request is "Change teh weight of edge {b, d} from 10 to 3", then draw the new MST T'. 1.2 Scheme (15 points) Give a high-levelalgorithmic scheme for constructing T' (no proof of correctness required). You may wish to considerseparately the cases ei &lt T and when ei |&lt T.1.3 Algorithm and running time. (15 points) Give an algorithm which, given Gand T represented byadjacency lists, the weight function in an array w, and a request (ei, w') to decrease the weight of ei from w(ei)to w', outputs tree T'. Argue that the running time of your algorithm is O(V).Problem #2 - Course-scheduling in two lecture halls (35 points)Suppose that we have a list of n classes, where class ci = (si, fi) has starting time si and finish time fi. We havetwo lecture halls, and the problem is 1) to decide whether it is possible to assign each class to a lecture hall(hall[i] = j if class ci is assigned to lecture hall j, where j = 0 or j = 1) so that classes which have beenassigned to the same lecture hall do not overlap, and 2) to give an assignment when it is possible.2.1 Scheme. (12 points) Propose a greedy high-level algorithmic scheme for this problem.2.2 Correctness. (11 points) Prove by induction that the algorithm always finds an assignment when there isone. Be sure to state your inductive statement clearly.2.3 Algorithm and running time. (12 points) Give a detailed algorithm implementing your scheme. What isthe running time ? Justify briefly.CS170 , Midterm #2, Fall 1994CS170, Fall 1994 Midterm #2 Professor Vazirani 1Problem #3 - Shortest path tree (35 points)Given a weighted strongly connected directed graph G = (V, E) with positive edge weights, and a vertex s ofG, we say that a subgraph T = (G, E') of G is a shortest-path tree rooted at s if the following three conditionshold:1) The undirected version of T is a tree,2) For any vertext w, there is a unique path from s to w in T, and3) the weight of that path is equal to the smallest weight of any path from s to w in G.We consider the problem which takes as input a graph G = (V, E) and a subgraph T = (V, E') of G, bothrepresented by adjacency lists, an array w of edges weights, and a vertext s of G, and which decides whetherT is a shortest-path tree rooted at s. Our goal is an O(V + E) algorithm.3.1 Example. (5 points) Draw a shortest-path tree of the graph G below.3.2 Scheme. (10 points) How would you decide whether conditions 1 and 2 above are satisfied? (No proofrequired).3.3 Scheme. (10 points) How would you decide whether condition 3 above is satisfied? (No proof required).3.4 Algorithm and running time. (10 points) Design an algorithm for deciding whether T is a shortest-pathtree rooted at v. Prove that its running time is O(V + E).Problem #4 - Selection in a heap (35 points)Suppose you are given a binary heap A containing n elements, with the minimum at the root. you are asked tofind the kth smallest element in the heap, where k can be any number between 1 and n.4.1 Naive scheme. (5 points) Give an O(k * log n) algorithm for solving this problem. Justify.4.2 Idea for scheme. (10 points) Give an O(1) algorithm for finding the 4th smallest element. Instead ofwriting the algorithm formally, just explain how you would proceed in the example below. (Do not prove thatthe running time is O(1))4.3 Scheme. (10 points) Give an algorithmic scheme for finding the kth smallest element.4.4 Implementation. (10 points) Implement your algorithm. What is the running time? Justify. (We expectyou to find either an O(k^2) running time, or, with an improved implementation, an O(k * log k) runningtime).CS170 , Midterm #2, Fall 1994Problem #2 - Course-scheduling in two lecture halls (35 points) 2Posted by HKN (Electrical Engineering and Computer Science Honor Society)University of California at BerkeleyIf you have any questions about these online examsplease contact [email protected] , Midterm #2, Fall 1994Posted by HKN (Electrical Engineering and Computer Science Honor Society) University of California at Berkeley If you have any questions about these online exams please contact