CMPS 256 Final, Fall 2003

January 29, 2003 CMPS 256 Final Exam American University of Beirut CMPS 256 Final Exam January 21, 2003 AMERICAN CXEVERSITY LIBRARY 2 hour exam OF GeMUT Student Name: Student ID: Signature: * There are twelve pages, including this one. The test is out of 100 marks, and the value of each question is provided: please use this information to manage your time effectively. * Your handwriting should be neat and readable OR I will not mark the answer! Question 1: /10 Question 2: __ /10 Question 3: /10 Question 4:___/10 Question 5: 110 Question 7: /10 Question 6: /10 Question 8: __. /10 Question 9: __ /10 Question 10: /10 Toral: CS / 1:00 Instructor: Marcel R. karam ‘ January 20, 2003 CMPS 256 Final Exam Question | [20 points] Multiple Choice True or false? No explanation required. Each correct answer is worth | points, but | points will be subtracted for each wrong answer, so answer only if you are reasonably certain. 1-T F By the master theorem, the solution to the recurrence: 7(n) = 37(n/3) + log nis: O(n dog n) 2-T F Givena graph G= (VE) with cost on edges, anda set Sin V Let (x, v) be an edge such that (1, v) is the minimum cost edge between any vertex in S and any vertex in V- S. Then, the minimum spanning tree of G must include the edge (u, v). (You may assume the costs on all edges are distinct, if needed.) F Let P bea shortest path from some vertex s to some other vertex ¢ in a graph G. if the weight of each edge in the graph is increased by one, ? remains a shortest path from s to ¢. The breadth first search algorithm makes use of a stack. The Bellman-Ford algorithm is not suitable if the input graph that has negative- weight edges Depth-first search of a graph is asymptotically faster than breadth-first search. Dijkstra’s algorithm is an example of a greedy algorithm. The maximum number of edges that can be removed from a graph with nodes in order to construct a spanning tree is: n(n-1)/2 - (n-1) = (n-1) (n/2 - 1) You are given a graph in which all edges have non-negative weights, except those leaving the source vertex s. Then Dijkstra’s algorithm may fail to correctly deter- mine the shortest paths from s. Suppose 7 is a minimum spanning tree for a graph G. Then the largest edge weight of 7 is no larger than the largest edge weight of any other spanning tree of G. Instructor: Marcel R. karam L January 20, 2003 CMPS 256 Final Exam Question 2: Asymptotic and Recurrences [10 points] The following is a Divide-and-Conquer algorithm for finding the minimum value in an (unsorted) array S[{1.n]. The library functionmin(a, b) used in the algorithm returns the smaller between a and b. function minimum(S, x, y) ify-x<l then return min(S[x],S[y]) else min] © minimum(S, x, L( (x + y) yi2)) min2 © minimum(S, L( (x + y) 2) +l,y) return min(min] ,min2) a) Write a recurrence relation for the worst-case number of comparisons used by mini- mum(S, 1, n). (You may assume that » is a power of two.) b) What is the running time of minimum(S, 1, n). Justify your answer Instructor: Marcel R. karam January 20, 2003 CMPS 256 Final Exam vy Question 3: Hash Tables [1 0 points] You are given a hash table m = 10, where all elements are stored in the hash table itself (i.e.,open addressing). On insertion, collisions are resolved using the following reverse linear probe auxil- iary hash function: h (hk, i) = (# (2) - i) mod m for i = 0, m-). Namely, if a collision occurs, the immediately previous slot is examined. If that slot is not empty, preceding slots are examined, one by one, until an empty slot is found. If you reach the beginning of the table, you then wrap around to the end and continue from there. (a) The hash table is initialized (7 = 0) and the x following sequence of insertions is made: insertion order + 1 | gna | ard | fh | 5th | ge | 7 keyh = a b ¢ d © f g primary hash A(k)= 2 | 4 4/9 |]3 13 42 Instructor: Marcel R. karam January 20, 2003 CMPS 256 Final Exam Question 4: Minimum Spanning Trees [10 points] Find a minimum spanning tree for the following graph using Prim’s algorithm. Start with vertex A and show only the final stage of the constructed tree. Instructor: Marcel R. karam January 20, 2003 CMPS 256 Final Exam Question 5: Shortest path [10 points] Does Dijkstra’s shortest path algorithm produce a correct shortest path for input graphs with negative edge weights. Prove using an example: Instructor: Marcel R. karam 6/12 January 20, 2003 CMPS 256 Final Exam Question 6: Graphs [10 points] (a) Draw the following graph: =({I, 2, 3,4, 5, 6}, {{1, 2}, (1, 4}, (2. 5}, (2, 6}, (3, 4}, (3, 5}, 3, 6}, (4, 5}, {4, 6}, (5, 6} }) (b) Redraw the following graph in such a way that no two lines cross. cn L» (c) Add one or more edges to the above graph to create one which cannot be redrawn in such a way that no two lines cross (a proof is not required). Instructor: Marcel R. karam TAZ January 20, 2003 CMPS 256 Final Exam Question 7 [10 points] Given a specific edge (u, v) of a graph G =(V E) devise an algorithm which constructs a spanning tree of G containing (u, v) Instructor: Marcel R. karam January 20, 2003 CMPS 256 Final Exam Question 8 [10 points] You are given a connected directed graph G = (V £) where every edge has the same positive integer weight & There is a distinguished vertex ¢ in this graph and we want to know the shortest distance from each of the other vertices to this distinguished vertex ¢. Present an algorithm, with the best asymptotic upper bound for the worst case running time, that solves this problem. Hint: You can solve this in a couple of ways, using algorithms and data structures we have cov- ered in this course. Your first approach may, or may not, be the best asymptotic one. So, think twice. Instructor: Marcel R. karam ‘ January 20, 2003 CMPS 256 Final Exam Question 9 [10 points] Recall Kruskal’s algorithm to produce a Minimum Spanning Tree (MST). For convenience, the algorithm from the book is copied here: MST-KRUSKAL(G, 18) 1 Acd © A will be MST. 2. for each vertex v € VG] 3. do MAKE-SET(v) ‘i Create forest of singleton trees. 4. sort the edges E into nondecreasing order by weight w 5. for each edge (u,v) € E. taken in nondecreasing order by weight 6. do if FIND-SET(u) # FIND-SET(v) — 4 Are wand v in disjoint trees? 7. then A+ AU{(u,v}} ff Yes. Add edge (u,v) to MST. 8. UNION(u, 0) “ Join disjoint trees connected by edge (u,? 9. return 4 Describe how to modify Kruskal’s algorithm to find a Maximum Spanning Tree, instead o fa Mini- mum Spanning Tree. Instructor: Marcel R. karam 10/12