CMPS 256 Final, Fall 2004

at oa EMI ENEFE Faculty of Arts & Sciences Department of Computer Science CMPS 256—Advanced Algorithms and Data Structures Fall 2004-2005 Tuesday, February 1°, 2005 Final Exam This exam is for Section 1 exclusively — F. Abu Salem Name: Duration: 120 minutes General Instructions e There are 10 pages to this exam. Make sure you have all of them. e The exam is closed book, closed notes, and closed neighbor. e You are not allowed more than two A4 pages of notes (front and back). ¢ Your handwriting should be readable so it can be graded properly. Grade Distribution Question Allocated | Received 1 (a) 5 1(b) 1(c) 1 (d) 1 (epi. 1 (©) ii. 1 (ec) iii. 1 (e) iv. Final Exam (2005-02-05) Initials: Question 1: (40 pts) (a) (S pts) Modify the adjacency list representation for an undirected graph so that the first edge on the adjacency list of a vertex can be deleted in constant time. Write an algorithm to delete the first edge using your new representation. (b) (5 pts) The police department in the city of Beirut has made all streets one-way. The mayor contends that there is still a way to drive legally from any intersection in the city to any other intersection, but the opposition is not convinced. Furthermore, the city elections are coming up soon, and there is just enough time to run a Jinear-time algorithm. Formulate this problem as a graph-theoretic problem, and explain why this problem can indeed by solved by a linear-time algorithm. CMPS 256 2 of 10 Final Exam (2005-02-05) (©) (pts) The following algorithm is proposed to obtain the median value in an array with n’ elements, where is odd and n>1: First arrange the r’ elements into n groups with n elements in each group. Next find the median in each of the n groups. Finally find the median of these n medians. Either (1) write a convincing justification why this algorithm is correct, or (2) construct a counterexample that shows this algorithm is not correct. (d) G pts) Draw a minimum spanning tree for this graph using Kruskal’s algorithm: B Cc D 16 15 25 17 24 CMPS 256 Final Exam (2005-02-05) Initials: (e) (20 pts—5 each) True of False? Justify your answer with either a proof or a counter-example. An unjustified answer will receive no credit. Ina depth first search of a directed acyclic graph, the vertex with the highest post-order number is necessarily a source. In a depth first search of a directed graph, it is possible to have an edge between two vertices u and v with starting and finishing times: (10, 40) for u and (30, 50) for v. CMPS 256 Final Exam (2005-02-05) Initials: ii. Ina depth first search of an undirected graph, it is possible to have an edge between two vertices u and v with starting and finishing times: (5, 20) for w and (30, 50) for v. iv. Ina depth first search of a directed graph, if u has starting and finishing times (10, 20) and v has corresponding times (15, 18), then (v, u) must be a back edge. CMPS 256 5 of 10 Final Exam (2005-02-05) Question 2: (15 pts) Kruskal’s algorithm and Prim’s algorithm (a) Will either Kruskal’s or Prim’s algorithm work correctly on graphs that have negative edge weights? If yes, justify your answer with a proof; else, provide a counter-example. (b) The notion of a minimum spanning tree is applicable to a connected weighted graph. Do we have to check a graph’s connectivity before applying Prim’s algorithm or can the algorithm do it by itself? CMPS 256 Final Exam (2005-02-05) Initials: Question 3: (15 pts) Simple cycles We say that a relation = on a set A is an equivalence relation if it satisfies the following three conditions: R (Reflexivity): For every a € A,a =a. S (Symmetry): For every a,b € A, a = bimplies b = a. T(Transitivity}: For every a, b,c € A, ifa = bandb =, thena = c. Now, let G = (VE) be a graph. Let = be a relation on V such that u = v if and only if u and v lie ona common (not necessarily simple) cycle. Prove that = is an equivalence relation. CMPS 256 Final Exam (2005-02-05) Initials: Question 4: (15 pts) Minimum cost spanning tree (a) Suppose that you are given an undirected graph with distinct positive costs on its edges. How can the minimum cost spanning tree change if we change the cost of one edge? (b) Suppose that you are given an undirected graph G = (V, E) with distinct positive costs on its edges and a minimum cost spanning tree of the graph. Suppose that the cost of exactly one edge is changed. Assuming an adjacency list representation of the graph, give an O(|E|) running time algorithm that finds a new minimum cost spanning tree. CMPS 256 Final Exam (2005-02-05) Question 5: (15 pts) Dijkstra’s algorithm (a) Dijkstra’s single source shortest paths algorithm works for non-negative weights. Give an example of a directed weighted graph that has both non-negative and negative weights in which Dijkstra’s algorithm produces wrong output (i.e. gives paths that are not shortest paths). Let G = (V,E) be directed weighted a graph where some of the edges have negative costs. Let W min be the smallest negative number that appears as a cost of an edge. Suppose that we construct anew graph G’ = (V,E) by changing the weights of edges in G according to the following formula: Ww i=W,-Ww min for all edges e in E. Note that G’ as such does not have edges with negative weights. Suppose that we run Dijkstra’s algorithm on G’. Will the shortest paths in G be thus correctly identified? Prove your answer if you think the output will be correct, or else provide a counter-example. CMPS 256 Final Exam (2005-02-05) Question 6: (16 pts) Hash tables Clearly explain the answers to the following questions; wherever applicable a simple yes or no will not count. (a) Is hashing an efficient way to implement sorting? For a hash table of size M, does separate chaining or does it not reduce the number of comparisons for sequential search by a factor of M? Describe a possible hash function for strings. Can a user elicit the worst-case behaviour of a hash table where universal hashing is used? CMPS 256