CS570 Analysis of Algorithms Fall 2013 Exam I Name: _____________________ Student ID: _________________ ____Tuesday/Thursday Session ____Wednesday Session ____DEN Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Problem 4 20 Problem 5 15 Problem 6 15 Total 100 2 hr exam Close book and notes If a description to an algorithm is required please limit your description to within 150 words, anything beyond 150 words will not be considered.1) 20 pts Mark the following statements as TRUE or FALSE. No need to provide any justification. [ TRUE/FALSE ] A directed graph G is strongly connected if and only if G with its edge directions reversed is strongly connected. True, by definition of strongly connectedness. [ TRUE/FALSE ] If a weighted undirected graph has two MSTs, then its vertex set can be partitioned into two, such that the minimum weight edge crossing the partition is not unique. True, Let T1 and T2 be two distinct MSTs. Let e1 be an edge that is in T1 but not in T2. Removing e1 from T1 partitions the vertex set into two connected components. There is a unique edge (call it e2) that is in T2 that crosses this partition. By optimality of T1 and T2, both e1 and e2 should be of the same weight and further should be of the minimum weight among all edges crossing this partition. [ TRUE/FALSE ] If the vertex set of a weighted undirected graph can be partitioned into two, such that the minimum weight edge crossing the partition is not unique, then the graph has at least two MSTs. False. Consider the graph with edge set {(a,b),(b,c),(c,d)} where all edge weights are identical. ({a,d},{b,c}) is a partition that does not have a unique minimum weight edge crossing it, however the graph (being a tree) has a unique MST. [ TRUE/FALSE ] The number of binomial trees in a binomial heap with n elements is at most O(log n). True. See the lecture notes. [ TRUE/FALSE ] A bipartite graph cannot contain a cycle of length 3 or greater. False. Consider the graph which is also a cycle with 4 vertices. It is bipartite contradicting the assertion in question. [ TRUE/FALSE ] Since Fibonacci heaps guarantee amortized cost and not worst case cost, the run time complexity of Dijkstra's algorithm using Fibonacci heaps may be worse than that of a binary heap implementation. False. For Fibonacci heaps with n entries, the amortized running time of delete min is O(log n) and the amortized running time for decrease key is O(1). Thus for every sequence of extract mins/decrease keys with (A extract mins and B decrease keys in total), the worst case running time is bounded by O(B+A log n). When applied to the implement the priority queue in Dijkstra, A is O(B), that is the number of vertices visited is asymptotically bounded by the number of edges relaxed. A binary heap implementation would take at least Theta(B log n) time since decreasy key takes Theta(log n) time. Thus, the Fibonacci heap implementation is faster even in the worst case.[ TRUE/FALSE ] Implementations of Dijkstra’s and Kruskal’s algorithms are identical except for the relaxation steps. False. It is Dijkstra's and Prim's that bear a resemblance not Dijkstra's and Kruskal's. For instance, at a generic stage in Kruskal's we could have multiple disconnected components (a forest) while Dijkstra's always grows a tree. [ TRUE/FALSE ] The divide step in the divide and conquer algorithm always takes less time than the combine step, therefore, the complexity of a divide and conquer algorithm is never dependent on the divide step. False. Divide step could be slower than the combine step. [ TRUE/FALSE ] Suppose that in an instance of the original Stable Marriage problem with n couples, there is a man M who is first on every woman's list and a woman W who is first on every man's list. If the Gale-Shapley algorithm is run on this instance, then M and W will be paired with each other. True. If (M,W) are not matched with each other, then since (M,W) prefer each other to everyone else, they can swap making the matching unstable. [ TRUE/FALSE ] For a search starting at node s in graph G, the DFS Tree is never as the same as the BFS tree. False. For instance, G being a tree is a counterexample. 2) 15 pts Suppose you are choosing between the following three algorithms: I) Algorithm A solves problems by dividing them in constant time into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. II) Algorithm B solves problems of size n by dividing in constant time and recursively solving two subproblems of size n-1 and then combining the solutions in constant time. III) Algorithm C solves problems of size n by dividing them in constant time into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n2 ) time. What are the running times of each of these algorithms (in big-O notation), and which would you choose? I. O(nlog25) II. O(2n) III. O(n2log(n)) - the minimum time complexity3) 15 pts Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite graph G has a node for each course, and an edge from course v to course w if and only if v is a prerequisite for w. Find an algorithm that works directly with this graph representation, and computes the minimum number of semesters necessary to complete the curriculum (assume that a student can take any number of courses in one semester). The running time of your algorithm should be linear. First do a BFS/DFS to make sure that the graph is a directed acyclic graph (DAG) (otherwise, the coursework cannot be completed in finitely many semesters since there would be a cycle of prerequisite dependencies). The problem then reduces to finding the length of the longest path in the DAG which can be solved as follows.Do a topological sort, let the resulting set of vertices be {v1,v2,v3,...,vn} in O(|V|+|E|) time. Recall from HW 4, prob 5 that the above topological sorting implies that for all j>i, there is no directed path from vj to vi. Set all the edge lengths to equal 1. Then iteratively (similar to Dijkstra's modification in HW 4, prob 5) compute the length of the longest path to v1, then the length of the longest path to v2, and so on until vn as explained below. Let L(v) denote the length of the longest path ending at v. We will iteratively compute L(v). Start with v1. Since v1 has no incoming edges, the length of the longest path