CS570 Analysis of Algorithms Fall 2014 Exam I Name: _____________________ Student ID: _________________ Thursday Evening Section DEN Yes / No 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 ] 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 in a directed graph, then the graph is strongly connected. 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