Algorithm Analysis Final Exam CSI 3108-01, Fall 2020 Due at 3:00pm, Friday, December 18 This problem set consists of four written problems. The point breakdown is as follows: 1 = 2 points 2 = 12 points 3 = 26 points (3a = 18, 3b = 8) 4 = 20 points You are not allowed to collaborate with anyone on this problem set. Read the final exam instructions posted on YSCEC. When a problem asks you to design an algorithm, you must present a full description of the algorithm, an analysis of its running time, and a proof of its correctness, unless the problem says that you are allowed to skip one of those parts. Your algorithm must be efficient unless the problem specifies otherwise. If you solve a problem by reducing to an algorithm from the textbook (ex- cluding exercises) or lectures, then you do not need to re-derive the running time or proof of correctness for the algorithm you are reducing to. However, you must say which algorithm you are reducing to, and you must correctly account for that algorithm’s running time when determining the overall run- ning time of your own algorithm. You must also prove that your reduction is correct, under the assumption that the algorithm you are reducing to is correct. You are also allowed to quote any theorem from the textbook (again, ex- cluding exercises) or lectures, without re-deriving the proof of that theorem. This, in particular, includes the NP-completeness of various problems from the textbook (excluding exercises) or lectures. If any corrections need to be made, we will post them on YSCEC. Regularly check the course page on YSCEC. Write your solution in English. Good luck, and have a nice winter break! 한 학기 동안 수고 많으셨습니다. (1) (2 points) Let f be a function defined on the nonnegative integers. We have f(0) = f(1) = 1 and, for all n ≥ 2, f(n) = 2f(⌊n/2⌋) + f(⌈n/2⌉) + n⌊√n⌋. What is the asymp- totic growth of f? Use big-theta notation. You do not need to provide any justification for your answer. (2) (12 points) Design an algorithm that, given a number k and a digraph G = (V,E) where each edge e has an associated color ce ∈ Z, determines if there exists a subset of edges F ⊆ E that satisifies the following properties. • The number of edges |F | is at least k. • The colors of the edges in F are distinct. • For all vertex v ∈ V , at most one edge in F is incident from v. For this problem, you do not need to prove the correctness of your algorithm; just present a full description of your algorithm and analyze its running time. Your algorithm must be efficient. Example 1. Consider an instance defined by k = 3, V := {p, q, r, s, t, u}, E := {〈p, q〉, 〈r, s〉, 〈t, u〉} and edge colors c〈p,q〉 = 1, c〈r,s〉 = 1, c〈t,u〉 = 2. The answer is no because, in order to satisfy |F | ≥ k, we must include all three edges in F , but then F would have two edges of the same color, namely 〈p, q〉 and 〈r, s〉. If we modify the instance so that k = 2, the correct answer is yes. Example 2. Consider an instance defined by k = 1, V := {p, q, r}, E := {〈p, q〉, 〈p, r〉} and edge colors c〈p,q〉 = 1, c〈p,r〉 = 2. The answer is yes because F = {〈p, q〉} satisifies the given conditions. If we modify the instance so that k = 2, the answer is no. (3) (26 points) (3a) (18 points) Consider the following game. Let Z≥0 be the set of all nonnegative integers. We have n cards, each of which has a tuple written on it. Let (mi, ai) ∈ Z≥0×Z≥0 denote the tuple on the i-th card. The goal of this game is to achieve as large score as possible. We begin with the initial score of 0 points. A card with a tuple (m, a) can be played only when the current score is at least m. When it is played, a is added to the current score. Once we play a card, the card cannot be played again. The cards can be played in any order, and we do not need to play all cards. Design an algorithm that, given n and the tuples (m1, a1), · · · , (mn, an) written on the n cards, determines the largest score we can achieve by playing some or all of these cards. You need to also prove the correctness of your algorithm and analyze its running time. Example. Consider an instance defined by n = 3, (m1, a1) = (99, 99), (m2, a2) = (2, 5), and (m3, a3) = (0, 3). The correct answer is 8: you can achieve 8 points by playing the third card and then the second. (3b) (8 points) Now we revise the rule of the game slightly as follows: when a card with a tuple (m, a) is played, • if a > 0, a is added to the current score; • if a = 0, the current score is doubled. All other rules remain the same. Design an algorithm that, given n and the tuples (m1, a1), · · · , (mn, an) written on the n cards, determines the largest score we can achieve by playing some or all of these cards. For this problem, you do not need to prove the correctness of your algorithm; just present a full description of your algorithm and analyze its running time. Your grade for this problem will depend on the asymptotic running time of your algorithm, unlike other problems where you only need to give an efficient algorithm. Try to give an asymptotically fast algorithm, and carefully analyze its running time. Example. Consider an instance defined by n = 3, (m1, a1) = (0, 0) and (m2, a2) = (0, 1), and (m3, a3) = (2, 1). The correct answer is 3: you can achieve 3 points by playing the second card, the first card, and the third card in that order. (4) (20 points) Given a finite set U , consider a collection of subsets of U . This collection is initialized to be the collection of the |U | singletons, {{u} | u ∈ U}: for example, if U = {a, b, c}, the initial collection is {{a}, {b}, {c}}. An evolution is the following operation that can be performed on a collection: we pick two subsets from the collection, take their union, and add it to the collection. We can choose which two subsets to pick from the collection, but each time an evolution is performed, we choose only two subsets. Consider the following problem. Problem 1 (Evolving Collection). Given a finite set U , a number k > 0, and a list S1, . . . , Sm ⊆ U of m subsets of U , can we perform at most k evolutions, starting from the collection of the singletons, so that all of S1, . . . , Sm are in the collection at the end? For each evolution, we are free to choose the two subsets to pick from the collection. Prove that Evolving Collection is NP-complete. Example. Consider an instance defined by k = 4, U := {a, b, c, d},m = 3, S1 := {a, b, c}, S2 := {a, b, d}, and S3 := {a, b, c, d}. The answer is yes. The collection initially contains four singletons: {{a}, {b}, {c}, {d}}. We perform the first evolution by picking {a} and {b}. Then the collection becomes: {{a}, {b}, {c}, {d}, {a, b}}. We then perform the second evolution by picking {c} and {a, b}. The collection becomes: {{a}, {b}, {c}, {d}, {a, b}, {a, b, c}}. Now we pick {d} and {a, b} to perform the third evolution, which yields {{a}, {b}, {c}, {d}, {a, b}, {a, b, c}, {a, b, d}}. Finally, we perform the fourth evolution by picking {d} and {a, b, c}. The collection becomes: {{a}, {b}, {c}, {d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d}}. Note that, after performing these four evolutions, the collection contains all S1 = {a, b, c}, S2 = {a, b, d}, and S3 = {a, b, c, d}. Recall that k = 4. The correct answer is therefore yes. If we modify the instance so that k = 3, the answer is no because whichever two sets we may choose for at most three evolution operations, we cannot make all S1, S2, and S3 included in the collection. 欢迎咨询51作业君
