CMPS 256 Final, Fall 2001

ERICAN CNIVERSIT?) LIBRARY OF erie American University of Beirut MATHEMATICS 256 Advanced Algorithms and Data Structures Fall 2001-2002 Final Exam Date: Feb. 1°, 2002 8:00 — 10:00am. Instructor: Jihad Boulos ERICAN CNIVERSIT’ LIBRARY OF REIRUT Name of student to your left: .........seeeeseeeeeeeeeeceees Name of student to your right: .........csesseeseeeoees This is an open-book, open-note exam. Your exam should have 15 pages (the last 3 are blank, so you can use them il you need additional space for any of the exercises), and there are 8 exercises totaling 100 points. You may use your notes, cluss handouts, and the main course textbook. You are NOT allowed to use any external notes. Your answers should be concise, and when possible should be a list of important points rather than prose. Solve as much probiems as you can. advise you to spend time on understanding the problem and budget your time for solving each problem. or else you will be wasting a lot of time on one problem and will run out of time for other problems. The problems are NOT provided with an incremental difficulty, so exercise 7 might be easier than exercise 4, for example. Wordy and/or irrelevant answers will reduce your score for that problem. Your answers should be the summary of work done on scratch paper that you do not hand in. If I could not read your writing, I will just give a ZERO without bothering myself trying to understand what you are writing. The space allocated for answers should be sufficient for your answers. If not, use additional papers. FRICAN DONIVERSIT) LIBRARY OF REIRUY Exercise 1 (15 points): Asymptotics and Recurrences Order these functions in order of increasing ©@-order. When two functions have the same @-order, please indicate this explicitly. Please write your calculations on scratch papers (e.g., on the back side of the proceeding page) and provide on this page your answers only. a) Order the following 5 functions: (1) nflog’ n (2) n2™ (3) loglogn (4) log n (5) Va ANSWER: b) Order the following 4 functions: (1) TQ) =ant5T (n/0) (2) T (a) =14+3T (n/2) (3) Tin) =an+T(nf/7i+T (6nf7). (4) T(n) = nT (30/7) +T (Anf7). Exercise 2 (22 points): True or False? Circle the correct answer. No explanation required. Each correct answer is worth 2 points, but 2 points will be subtracted for each wrong answer, so answer only if you are reasonably certain. 1. Let G be a directed graph with positive edge weights W(e). Let Wins = maxe W(e) be the maximum edge weight. Dijkstra’s algorithm will find the longest path from the start vertex s to any other vertex » in a graph if we replace all the edge weights W(e) by the new positive weights | + W,.... - W(e) before running the algorithm. ANSWER: TRUE FALSE 2. After we run DFS on a directed graph G, it is possible for a single vertex v € G to be simultaneously incident on at least one back edge, forward edge. cross edge and tree edge (Le., all these types of edges together). ANSWER: TRUE FALSE 3. Let 7(0)=! and T(n) = 2" forn > 1. Then the cost of computing T(”) and printing it out as a binary integer is O(T (2-1). ANSWER: TRUE FALSE 4. If Ti) = 497 (n/7) + r cosvn, then T(n) = O(n? logan). ANSWER: TRUE FALSE and 5. The path computed by the Bellman-Ford after the 2™ iteration might be the shortest. ANSWER: TRUE FALSE 6. In a graph G. the sum of the degrees of all the nodes of G is an even number. ANSWER: TRUE FALSE 7. Let G(V. E) be an undirected graph. Then G has a cycle if and only if it is possible to put directions on all the edges in £ so that every vertex in V has an edge pointing to it. ANSWER: TRUE FALSE 8. Let X be a minimum spanning tree of the weighted undirected graph G(V, E). Let G’'(V'. E’) be another graph defined be augmenting G with a new vertex u and some weighted edges incident on w. In other words, V’ = Vu {ur} and E' = E UF where Fisa set of edges touching uw. Then there is always a minimum spanning tree X’ of G’ such that XX’. ANSWER: TRUE FALSE 9." js oer") forall ce > 0. ANSWER: TRUE FALSE 10. Let G be an undirected graph, and let G' be another undirected graph. G’ has one vertex for each biconnected component of G (and no other vertices), Two vertices in G’ are connected by an edge if and only if the two corresponding biconnected components in G share a vertex. Then G’ can have a cycle. ANSWER: TRUE FALSE 11. Let G be a directed graph. The Bellman-Ford algorithm will find the longest path (if it is finite, or report if it 1s not) from the start vertex s to any other vertex v in a graph if we negate all the edge weights W(e¢) before running the algorithm. ANSWER: TRUE FALSE Exercise 3 (3 points): Your friend guesses an integer between 0 and N: You can ask questions like “is the number less than 100?” He will give YES NO answers. How many questions can your friend force you to ask, if you are a smart person? ANSWER: Exercise 4 (8 points): A B-tree with parameter ¢ = 64 has 256 million elements in it. Give the minimum and maximum possible height ol the tree. The parameter ¢ is the minimum branching factor for a node (i.e., the minimum degree of a B-tree as it is defined in the book). You may use the approximation | million = 2” If you do rough calculations you may be off by one either way. This is fine, but show me your logic in computing these maximum and minimum, so that you can get some grades even if the answers are not correct. ANSWER: Exercise 5 (10 points): In a full binary tree, each node is either a leaf or has exactly two children (i.e., there are no nodes with just one child}. Consider a full binary tree with 7 leaves and suppose we give each leaf / a weight of 2" (the root is defined to have depth 0). a) What is the sum of the weights of all the leaves? ANSWER: b) What is the average weight of all the leaves? ANSWER: ¢) The function f(x) = 1/2" is “convex”. This means that for any set of points S, average. s( f(x) 2 fl(averageS)). For example, f(x) f((a+b)/2) Use this fact and your answer to question (b) to complete the following statement: In a binary tree with n leaves, the average depth of a leaf is at least (circle the largest correct answer): | 708: n log, ANSWER: d) The answer to (c) implies that for any comparison-based sorting algorithm, the expected number of comparisons needed to sort a random permutation of n inputs is at least (choose the largest correct answer): l 5 log.” log,” 2log,n —log,(n!) log, (n!) 2 log, (n!) ANSWER: Exercise 6 (12 points): Inverting upper triangular matrices A matrix U is upper triangular if = 0 for i > j. Consider the following recursive algorithm to compute the inverse of an upper triangular matrix U. We will assume that n is a power of 2. [You need not know the definition of the inverse of a matrix to solve this question. ] Procedure Inv(U) ifn = 1 then return ut) . . : A B Decompose U into four n/2xn/2 matrices such that: U = oc Inv(A) —Inv(A)e Be Inv(C) 0 Inv(C) The © is matrix multiplication, which we will assume is performed using the “standard” algorithm that takes Oln') arithmetic operations to multiply two nxn matrices. a) Write a recurrence for the number of arithmetic operations used by procedure Inv() on an nxn matrix. (The base case is T(1) = 1.) ANSWER: b) Solve the recurrence to determine the n umber of arithmetic operations used by procedure Inv() on an Xn matrix. Write your answer using big-O notation. ANSWER: Exercise 7 (15 points): Running te AUB To get in shape. you have decided to start running to the university. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going uphill and then get a nice wind at the end of your run as you run faster downhill. Your run will start at home and end at the university (for those who live on or near the campus, assume that you will be running around the university) and you have a map detailing the roads with m road segments (any existing road between two intersections) and n intersections. Each road segment has a positive length, and each intersection has a distinct elevation. a) Assuming that every road segment is either uphill or downhill, give an efficient algorithm to find the shortest route that meets your specifications. ANSWER: