COS 226 Algorithms and Data Structures Spring 2004FinalThis test has 11 questions worth a total of 84 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 show your work in the space provided. Write outand sign the Honor Code pledge before turning in the test.“I pledge my honor that I have not violated the Honor Code during this examination.”Problem Score Problem Score0 61 72 83 94 105Sub 1 Sub 2Tot a lName:Login ID:Precept:1 12:3021:3043:3012 PRINCETON UNIVERSITY0. Miscellaneous. (2 points)(a) Write your name and arizona login in the space provided on the front of the exam, andcircle your precept number.(b) Write and sign the honor code on the front of the exam.1. Analysis of algorithms. (8 points)In this course we have encountered several different types of algorithmic analyses. For eachtype, list two algorithms for which that style of analysis was used in lecture or in the textbook.Be specific, e.g., don’t just say quicksort, say quicksort with partitioning on a random element.(a) Amortized.(b) Worst-case.(c) Average case.(d) Randomized.COS 226 FINAL, SPRING 2004 32. String searching and pattern matching. (8 points)(a) Give a DFA that recognizes the set of all strings (over the two letter alphabet) thatcontain aaba.(b) Give an NFA that recognizes the same language that the regular expression (ab*a | a*b) de-scribes.4 PRINCETON UNIVERSITY3. Convex hull. (8 points)Run the Graham scan algorithm to compute the convex hull of points below, starting fromA. Give the points that appear on the trial hull (after each iteration) in the order that theyappear. Circle your answer.0 1 2 3 4 5 6 7 8 9 10 11 12 13 140123456789ABCDEFGHICOS 226 FINAL, SPRING 2004 54. Discretized Voronoi diagram. (10 points)Suppose you want to compute a Voronoi data structure for a set of pixels drawn from anR-by-R grid. Devise an efficient scheme to support the following three operations.• create(R ): create an empty data structure to handle an R-by-R grid.• insert(i, j): insert the pixel (i, j) into the data structure, where i and j are integersbetween 0 and R-1.• find(x, y): return the inserted pixel which is closest to (x, y) in Euclidean distance,where x and y are integers between 0 and R-1.The create and insert operation should take O (R2) time; the find operation should take O(1)time. For partial credit, give an algorithm that takes O(NR2) time for insert, where N is thenumber of points already inserted into the data structure. Hint: think simple.(a) Describe how to implement create(R). Indicate what is being stored.(b) Describe how to implement find(i, j).(c) Describe how to implement insert(i, j).6 PRINCETON UNIVERSITY5. Undirected graphs. (8 points)Consider the following undirected network. Run depth first search, starting at vertex A.Assume the adjacency lists are in lexicographic order, e.g., when exploring vertex A, use A-Bbefore A-H. List the vertices in the order they are visited with DFS according to preorderand postorder. Circle your answers.(a) Preorder.(b) Postorder.COS 226 FINAL, SPRING 2004 76. Minimum spanning tree. (8 points)Consider the following undirected network with edge weights as shown.(a) Give the list of edges in the minimum spanning tree and circle your answer. You mayuse the fact that e−1is approximately 0.3678794411714423215955238 and e−2is approx-imately 0.1353352832366126918939995.(b) Suppose that the weight of edge B-D is changed to x instead of e−16. For which valuesof x isB-DanedgeinaMST.8 PRINCETON UNIVERSITY7. Max flow, min cut. (8 points)Starting from the following flow (printed above or to the right of the capacities), perform oneiteration of the Ford-Fulkerson algorithm. Choose a shortest augmenting path, i.e., the pathwith the fewest number of arcs.(a) Write down your shortest augmenting path.(b) Perform the augmentation. What is the value of the resulting flow?(c) Is the resulting flow optimal? If so, give a min cut whose capacity is equal to the valueof the flow. If not, give a shortest augmenting path.COS 226 FINAL, SPRING 2004 98. Data compression. (8 points)(a) What is the Burrows-Wheeler transform of “baracadabra”? Circle your final answer.109876543210baracadabra(b) What is the inverse Burrows-Wheeler transform of “7 rdrbcaaaaab”. Circle your finalanswer. Show your work for partial credit.next109876543210rdrbcaaaaab10 PRINCETON UNIVERSITY9. Linear programming. (8 points) (Hillier and Lieberman, 3.4-9)You are the pilot of a cargo plane. The plane has three compartments (front, center, andback) with the following absolute limits on how much weight and volume you can store ineach.Weight Space(Tons) (Cubic Feet)Front 12 7,000Center 18 9,000Back 10 5,000To balance the plane, the amount of weight in each compartment must be exactly equal. Youcan ship any (or all) of the following four types of cargo, in whole or fractional units.Volume Profit(Cubic Feet / Ton) (Dollars / Ton)1 500 3202 700 4003 600 3604 400 290You may ship at most 20, 16, 25, and 23 tons of cargo 1, 2, 3, and 4, respectively. Formulate(but do not solve) a linear program to determine how many tons of each cargo you shouldship so as to maximize profit. Use only the following 12 decision variables. It’s not necessaryto put it into standard form.Fi= tons of cargo i to assign to the front compartmentCi= tons of cargo i to assign to the middle compartmentBi= tons of cargo i to assign to the back compartmentPut your answer to on the facing page and circle your final answer.COS 226 FINAL, SPRING 2004 11Put your answer to question 9 here. Don’t forget to do question number 10.10. Reductions. (8 points)Given an undirected graph with V vertices, E edges, two distinguished vertices s and t,andnonnegative weights on the remaining vertices, find a path from s to t that minimizes thesum of the vertex weights. Devise an O(E log V ) algorithm for this problem by reducing it tostandard shortest path problem on directed graphs.To demonstrate your reduction, draw the shortest path network (directed graph + edgeweights) associated with the following input. Assuming it is clear from the picture how yourreduction extends to arbitrary graphs, you need not describe it
View Full Document
Unlocking...