CS570 Analysis of Algorithms Fall 2014 Exam I Name Student ID Thursday Evening Section Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total Maximum 20 15 15 20 15 15 100 DEN Yes No 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 Adding a number w on the weight of every edge of a graph might change the shortest path between two vertices and True Consider G V E with V u x v and E ux xv uv Let weight of edge ux wux wxv 3 and wuv 7 Then the shortest path from u to v is given by u x v with a total weight of 6 However if we now add 2 to every edge weight the path u x v will have a total weight of 10 while the path u v will have a weight of 9 making it the new shortest path TRUE FALSE Suppose that for some graph we have that the average edge weight is A Then a minimum spanning tree of will have weight at most False We may be forced to select edges with weight much higher than average For example consider a graph G consisting of a complete graph G on 4 nodes with all edges having weight 1 and another vertex u connected to one of the vertices of G by an edge of weight 8 The average weight is 8 6 7 2 Therefore we would expect the spanning tree to have weight at most 4 2 8 But the spanning tree has weight more than 8 because the unique edge incident on u must be selected TRUE FALSE DFS finds the longest paths from start vertex s to each vertex v in the graph False Depends on the order in which the nodes are traversed TRUE FALSE If one can reach every vertex from a start vertex is strongly connected in a directed graph then the graph False TRUE FALSE F n 4n 3 is both and True The dominant term is 4n which is obviously both O n and Omega n TRUE FALSE In Fibonacci heaps the decrease key operation takes time True Just as definition of decrease key operation in Fibonacci heaps TRUE FALSE If the edge weights of a weighted graph are doubled then the number of minimum spanning trees of the graph remains unchanged True With edge weights doubled the weights of all possible spanning trees in the graph are doubled So any MST in the original graph is also the MST in the new graph any spanning tree that is not the MST in the original graph is still not the MST in the new graph TRUE FALSE Given a binary max heap with n elements the time complexity of finding the smallest element is O lg n False The smallest element should be among the leaf nodes Consider a full binary tree of n nodes It has n 1 2 leafs you can think of why Then the worst case of finding the smallest element of a full binary tree heap is Theta n TRUE FALSE An undirected graph must be connected if False Consider a graph having nodes a b c d e a b c d forms a fully connected subgraph while e is isolated from other nodes Now the fully connected subgraph has 6 edges and there are only 5 nodes in total But this graph is not a connected graph TRUE FALSE If all edges in a connected undirected graph have unit cost then you can find the MST using BFS True Any spanning tree of a graph having only unit cost edges is also a MST because the weight is always n 1 units Of course BFS gives a spanning tree in the connected graph 2 16 pts At the Perfect Programming Company programmers program in pairs in order to ensure that the highest quality code is produced The productivity of each pair of programmers is the speed of the slower programmer For an even number of programmers give an efficient algorithm for pairing them up so that the sum of the productivity of all pairs is maximized Analyze the running time and prove the correctness of your algorithm Solution A simple greedy algorithm works for this problem Sort the speeds of the programmers in decreasing order using an optimal sorting algorithm such as merge sort Consecutive sorted programmers are then paired together starting with pairing the fastest programmer with the second fastest programmer Sorting takes O n lg n time while pairing the programmers takes O n time giving a total running time of O n lg n Correctness Let P be the set of programmers The problem exhibits an optimal substructure Assume the optimal pairing Given any pair of programmers i j in the optimal pairing the optimal sum of productivity is just the sum of the productivity of i j with the optimal sum of the productivity of the all pairs in P i j We now show that the greedy choice works by showing that there exists an optimal pairing such that the two fastest programmers are paired together Assume an optimal pairing where fastest programmer i is not paired with the second faster programmer j Instead let i be paired with k and j be paired with l Let pi pj pk and pl be the programming speeds of i j k and l respectively We now change the pairings by pairing i with j and k with l The change in the sum of productivities is pj min pk pl pk pl pj max pk pl 0 since pj is at least as large as the larger of pk and pl We now have an optimal pairing where the fastest programmer is paired with the second fastest programmer Hence to find the optimal solution we can keep pairing the two fastest remaining programmers together 3 16 pts The graph is defined to be an undirected graph with n vertices and all possible edges a fully connected graph That is the vertices are named and for any numbers i and j with there is an edge between vertex i and vertex j Describe the result of a breadth first search and a depth first search of For each search describe the resulting search tree Solution For the BFS the algorithm looks at all the neighbors of the root node before going to the second level Since every node in the graph is a neighbor of every other node every node other than the root is put at level 1 Thus the tree has one node at level 0 and n 1 nodes at level 1 The non tree edges are exactly those edges between different nodes on level 1 there are n 1 choose 2 of these For the DFS the search of the root node call it 1 will find another …