COS 226 Algorithms and Data Structures Fall 2005FinalThis test has 11 questions worth a total of 83 points. You have 150 minutes. The exam is closedbook, except that you are allowed to use a one page cheatsheet. No calculators or other electronicdevices are permitted. Give your answers and sh ow your work in th e space p rovided. Write outand sign t he Honor Code pledge before turning in the t e st .“I pledge my honor that I have not violated the H onor Code during this examination.”Problem Score Problem Score1 72 83 94 105 116Sub 1 Sub 2TotalName:Login ID:12 PRINCETON UNIVERSITY1. Analysis of a lgorithms. (10 points)A Fibonacci heap is a priority queue that supports the following operations in the givenamortized running time. Here, the elements are 1 through N and the data in the keys canonly be accessed via pairwise comparisons.Operation Description AmortizedCreate(N )create an empty heapof capacity NO(N)Insert(i, k)insert element i, andassign it key kO(1)DecreaseKey(i, k)decrease the key associatedwith element i to kO(1)DeleteMin()delete and return the elementwith the s mallest keyO(log N)(a) Define wh at the amortized runnin g times mean in this context.(b) Suppose you implement Dijkstra’s algorithm using a Fibonacci heap as the und erlyingpriority queue. What is the resulting worst-case asymptotic running time of Dijkstra’salgorithm as a function of the number of vertices V and the number of edges E.(c) Explain briefly why no priority queue can implement Insert, DecreaseKey, andDeleteMin in O(1) time each.COS 226 FINAL, FALL 2005 32. String searching. (6 points)The following DFA purports to accept precisely those strings (over the two letter alpha-bet) that contain bbabbb. Ass ume state 0 is the start state and state 6 is the acceptstate.(a) Are there any strings containing bbabbb that it rejects?If s o, give the shortest such string and circle it.(b) Are there any strings not containing bbabbb that it accepts?If s o, give the shortest such string and circle it.(c) Describe how to fix the DFA so that it works as intended.4 PRINCETON UNIVERSITY3. Pattern matching. (6 points)Draw an NFA that recognizes the same language that the regular expression a(bc)*d | e* de-scribes. Use the notation and construction given in lecture. Circle your final answer.COS 226 FINAL, FALL 2005 54. Convex hull. (6 points)Run the Graham scan algorithm to compute the convex hull of the 9 points below, using I asthe base point, and continuing counterclockwise starting at H.0 1 2 3 4 5 6 7 8 9 10 11 12 13 140123456789IHGEFCDBA(a) List the points in the order that they are considered for insertion into the convex hull.(b) Give the points that appear on the trial hull (after each of the 8 remaining points areconsidered) in th e order that they appear.1.2.3.4.5.6.7.8.6 PRINCETON UNIVERSITY5. Geometry. (12 points)Given a set of N intervals on the x-axis of the form (ai, bi), design an O(N log N) sweep-linealgorithm to find a value x that is contained w ithin the maximum number of intervals. Youmay assume that no two endpoints have th e same value.(a) What are the events?(b) How d o you implement the sweep line?(c) What data structure stores the set of intervals that intersect the sweep line?(d) How d oes your sweep-line algorithm work, i.e., how do you process each event?COS 226 FINAL, FALL 2005 76. Digraphs a nd DFS. (6 points)Consider the following DAG. Run dep th fi rst search, starting at vertex A. Assume the adja-cency lists are in lexicographic order, e.g., when exploring vertex A, use A-B before A-D orA-E.hello(a) List the vertices in preorder.(b) List the vertices in postorder.(c) List the vertices in topological order.8 PRINCETON UNIVERSITY7. Undirected graphs and BFS. (10 points)The girth of an undirected graph is the length of the shortest cycle.helloA girth 5 gra ph.(a) Describe a polynomial time algorithm to find the girth of a graph.(b) What is its asymptotic running time as a fu nction of the number of vertices V and thenumb er of edges E.COS 226 FINAL, FALL 2005 98. Minimum spanning tree. (8 points)hello(a) Consider the weighted graph above. Give the list of edges in the MST in the order thatKruskal’s algorithm inserts them. For reference, the 18 edge weights in ascending orderare:4 9 12 18 19 21 22 23 24 25 30 33 34 35 36 39 42 65(b) Consider the weighted graph above. Give the list of edges in the MST in the order thatPrim’s algorithm inserts them. Start Prim’s algorithm from vertex A.10 PRINCETON UNIVERSITY9. Data compression. (6 points)Suppose you compress the following string using LZW compression over the two letter alpha-bet.a a b a a b a b a a a b a(a) List the strings in the LZW dictionary in the order th ey are inserted. (Assume thedictionary is initialized to begin with the two strings a and b.)(b) Draw the binary trie r ep resentation of th e resulting LZW dictionary.COS 226 FINAL, FALL 2005 1110. Linear programming. (5 points)Convert the following linear program to standard form, i.e., a maximization problem w ithequality constraints and nonnegative variables. (Do not solve.)minimize 26A + 30B + 20Csubject to: A + B + C = 1002A + 6B + 3C ≥ 1457A + 1B + C ≥ 855A + 1B + 6C ≤ 95A , B , C ≥ 011. Reductions. (8 points)Consider the following two decision problems.Ham-Path. Given a digraph, is there a path that v isits each vertex exactly once?Short est-Simple-Path. Given a digraph with integer edge weights (positive or negative),two d istinguished vertices s and t, and an integer L, is there a simple path from s to tof length at m ost L. (A simple path is a path that visits each vertex at most once.)Show that Ham-Path polynomial reduces to Shortest-Simple-Path. To demonstrate yourreduction, draw the instance of Shortest-Simple-Path associated with the followin g in-stance of Ham-Pat h. Be sure to include the edge weights and the value L. Assuming it iscorrect (and obvious how it extends to arbitrary digraphs), you need not describe it furth
View Full Document
Unlocking...