CMPS 356 Final, Fall 2003

EMCAN CNIVERUT LIBRARY OF BEIRUT American University of Beirut CMPS 356 Advanced Algorithms and Data Structures Fall 2003-2004 Final Exam Date: Jan. 24" 8:00 — 10:00am. Instructor: Jihad Boulos ID #: This is an open-book, open-note exam. Your exam should have 12 pages, and there are 12 questions totaling 116 points. You may use your notes, class handouts, and the main course textbook. YOU ARE NOT ALLOWED TO USE ANY OTHER EXTERNAL MATERIAL. Your answers should be concise, and when possible should be a list of important points rather than prose. Solve as much problems as you can. I advise each one of you to pick the problems that he/she thinks are easiest for him/her and work on them. I also 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 Tun out of time for other problems. You can use any problem that we saw in class to be NP-Complete in any of your solutions. 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] could not read your writing, I will just give a ZERO without bothering myself trying to understand what you are writing. Prob. 1Prob. 2Prob. 3 Prob. 8Prob.9 Prob. 10 Prob. 11 Prob. 12 Max Grade 4 4 6 10 15 15 15 35 fYour Grade Problem 1 (4 points): It is known that if a solution to Problem A exists, then a solution to Problem B exists also. (a) Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable. If his proof turns out to be valid, can we conclude that Problem B is also unsolvable? Answer yes or no (or don’t know). Answer: (b) Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable. If the proof turns out to be valid, can we conclude that problem A is unsolvable as well? Answer yes or no (or don’t know). Answer: Problem 2 (4 points): Consider the following statement: If 5 points are placed anywhere on or inside a unit square, then there must exist two that are no more than V2, / 2 units apart. Here are two attempts to prove this statement. Proof (a): Place 4 of the points on the vertices of the square; that way they are maximally separated from one another. The 5th point must then lie within V2, 2 units of one of the other points, since the furthest from the corners it can be is the center, which is exactly V2, / 2 units from each of the four corners. Proof (b): Partition the square into 4 squares, each with a side of 1/2 unit. If any two points are on or inside one of these smaller squares, the distance between these two points will be at most V2/2 units. Since there are 5 points and only 4 squares, at least two points must fall on or inside one of the smaller squares, giving a set of points that are no more than V2, / 2 apart. Which of the proofs are correct: (a), (b), both, or neither (or don’t know)? Answer: Problem 3 (6 points): Linear Programming Minimize Xyt+ X2—%3, Subject to: = 2x; -— 4x) +x3 +24 =4 3x) + 5x2 + x3 + x5 =2 which of x;, x2, x3 should enter the basis, and which of xs, xs should leave? Compute the new pair of basic variables and find the cost at the new corner. Problem 4 (6 points): You are a very rich person, who has a priceless jewel. You want to send this jewel to me via postal mail. You have a set of tamper-proof boxes and locks, which you can put on the boxes. I have my own set of boxes and locks. We assume that the adversary cannot tamper with the locked boxes or delay them. However, if a jewel is sent in an unlocked box, the adversary will gladly expropriate it from the box. Similarly, if a key to the box is sent via regular mail, the adversary will pocket the key. Design an algorithm to transmit the jewel. Problem 5 (8 points): Alice and Bob want to agree on a party to go to, but are afraid that their mothers might overhear their conversation and ground them. Bob decides to use RSA to encrypt their conversation: He chooses the prime factors p = 11 and g = 23 so that n= 11 - 23 = 253 and ¢(n) = (p- 1): (g- 1) =10-22=4-5-11. He recalls from bygone days that e has to be relatively prime to n and picks e = 3. What will the secret key d be? Suppose Alice wants to tell Bob that the party will be at “165 Park Avenue” and needs to encrypt m = 165. What will the ciphertext be? Problem 6 (8 points): Calculate 10°” mod 77. Explain your method. Do not use a calculator. Problem 7 (10 points): Dominating Set In the dominating set problem the input is an undirected graph G, the problem is to find the smallest dominating set in G. A dominating set is a collection S of vertices with the property that every vertex v in G is either in S, or there is an edge between a vertex in S and v. Show that the dominating set problem is NP-hard using a reduction from the vertex cover problem. Problem 8 (10 points): Rectangles You certainly enjoy painting pictures of overlapping rectangles. For your latest painting, you have chosen a set of n rectangles in the plane, each of which is specified by three numbers, given to you in arrays x;[1 7], x2[1 n], and y{1 nj. The corners of the 7th rectangle will be (x,[i], 0), (fi, yL), (x2[#], yLi]), and (x2[#], 0). The rectangles may overlap each-other. You are curious how much paint you will need to buy in order to color in all of the rectangles. Devise an algorithm that computes, in O(n log m) time, the area of the union of all n rectangles. Problem 9 (15 points): Suppose you are given a set S of » points. A point p in S is extreme if there exists a line L that passes through p such that the remaining points of S all lie strictly to one side of L. The set S is extreme if every point of S is extreme. a) Outline an O(n log n) algorithm to check whether S is extreme. b) Suppose we are given the points in S sorted by their x-coordinates. Can you solve the same problem in O(n) time? Problem 10 (15 points): Zaatar every Day Let’s assume that you decided that you must eat a zaatar sandwich every day for the remaining days, d;,d2,__, d, of the fall semester. You have exactly two choices for acquiring a zaatar sandwich: 1, On day dj, you can buy a zaatar sandwich (for consumption on day d;) from Z&W at price p;. These prices are announced in advance. i.e. on day d). You should understand here that the prices of zaatar sandwiches are not the same over all days. 2. On day dj, you can place an order with bulk-zaatar.com to have a zaatar sandwich delivered to you every evening for days d,, dj}, di+2,__, di+1}. The cost of this contract is Q. Note that Q is fixed and does not vary from day to day. Let’s assume also that you like to eat only fresh zaatar sandwich, and hence you cannot stockpile zaatar sandwiches; you must eat each sandwich on the day that you get it. Also, because you hate to waste food and because you can only stomach exactly one zaatar sandwich per day, you may not get two sandwiched on the same day. For example, you cannot order from bulk-zaatar.com three days after placing a previous bulk-zaatar.com order, Finally, you are not allowed to order from bulk-zaatar.com on day d, if there are Coe oT Tia waa ‘1 5 4 less than 12 days remaining (including d)), i.e. you can not have leftover zaatar sandwich at the end of the n day period. The problem is to find the cost of the optimal zaatar-ordering schedule. a. Consider the following greedy algorithm for this problem. This algorithm takes as input Q, the price of 12 zaatar sandwiches from bulk-zaatar.com, and the prices p,, P2, 5 Pm, the price of a zaatar sandwich from S&W on each of the n days. At day d;, it checks if the total cost of buying a zaatar sandwich from Z&W for that day and each of the next 11 days (i.e. days d, through d;.;;) is less than Q. If so, it buys a zaatar sandwich for day d, at price p; and goes on to the next day. Otherwise, it orders 12 zaatar sandwiches (for day d, though day d;,;;) from bulk-zaatar.com at price 0 and goes on to day dj+ 2. The pseudocode for this algorithm is provided below. BuyZaatarGreedily(Q, p;, , Pn) 1 2 3 4 5 6 7 8 Let cost = 0. Go from day d; to day d,. On day d;: If Q is greater than the sum of p; though p;.1; or if there are fewer than 12 days (sandwiches) left, Then buy a zaatar sandwich from Z&W, let cost <- cost + p; and go to day djs). Else Place an order with bulk-zaatar.com, let cost <- cost + Q and go to day dis 72. Output cost. Prove that BuyZaatarGreedily does not produce an optimal solution to the problem. b. Give a dynamic programming formula to find the cost of an optimal zaatar-ordering schedule. Analyze the running time of the algorithm implementing your formula. Problem 11 (15 points): What kind of problems is this? Let’s say we augment linear programs to allow constraints to include absolute values (e.g. [x1 + 3)x2| < ). Can we solve all such problems in polynomial time? Show why or why not. Problem 12 (15 points): Rectangles (again) Consider the following rectangle covering problem: - ad eat) Input: A collection of rectangles /={R,, , Rn} in the plane such that each rectangle is aligned with the axes (all sides are horizontal or perpendicular). Rectangles may overlap. Feasible solution: A collection of points P = {p;, _ , Pm} such that each rectangle in J contains at least one point from P. © Goal: Minimize the number of points |P|. Provide the best (polynomial time) approximation algorithm you can for this problem.