CS570 Analysis of Algorithms Fall 2013 Exam I Name Student ID Tuesday Thursday Session Wednesday Session DEN Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total Maximum 20 15 15 20 15 15 100 Received 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 complexity 3 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 to v1 is L v1 0 The length of the longest path to v2 is L v2 1 if the edge v1 v2 is present and 0 otherwise More generally If vi does not have an incoming edge …