B403 Introduction to Algorithm Design and Analysis Final Exam Date: May 8, 2020 Duration: 12:00am -11:59pm Total points: 40 Instruction: Please submit your answers via Canvas. If you have any questions, please email ALL of us and we will reply as soon as possible: • Qin Zhang: [email protected] • Mohsen Sayyadiharikandeh: [email protected] • Harshad Badiyani: [email protected] • Jong Sung Park: [email protected] Note: when you describe an algorithm, please use English words. Do NOT write code with language-specific notations Name: IU Username: 1 Q.1 4pts Q.2 6pts Q.3 6pts Q.4 6pts Q.5 6pts Q.6 6pts Q.7 6pts Total 40pts 2 Q.1 (4 pts) Concepts of NP For each of the following questions, choose the unique correct answer. There is no need to justify the answers. a) (2 pts) Assuming P 6= NP, which one of the following is TRUE? (A) P = NP-complete (B) NP ∩ P = ∅ (C) NP-complete ∩ P = ∅ (D) NP-complete = NP Your answer: b) (2 pts) For problems X and Y , Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE? (A) X is in P (B) X is in NP, but not necessarily NP-complete (C) If X can be solved in polynomial time, then so can Y (D) X is NP-complete Your answer: 3 Q.2 (6 pts) Finding the Second Lightest Egg Suppose Bob has n eggs, indexed by 1, 2, . . . , n. Each time, you can specify a set S ⊆ {1, 2, …, n} of size at most √ n and ask Bob the index of the lightest egg in S. Your goal is to find the second lightest egg with the least number of queries. Give an algorithm that solves this question using o(n) questions. 4 Q.3 (6 pts) Watering Your Garden You have recently bought a 1D “garden” of size n: n shrubs planted at positions 1, 2, . . . , n in a line. Before you bought the garden, the previous owner has installed n taps at position 1, 2, . . . , n, with each tap located at position j (1 ≤ j ≤ n) in the coordinate map. The taps have different working ranges, represented by an array range[n]. When tap j is open, it can water a line segment [j − range[j], j + range[j]]. As you are planning to water the entire garden for the very first time, you realize that the water bill is going to be very high if you simply turn on all taps. Therefore, you are trying to minimize the number of taps that should be open so that the whole garden is watered. Design a greedy algorithm that yields the minimum number of taps which you need to open to water the whole garden. Here you can assume that there is always at least one way of opening the taps such that the garden can be watered. Prove the correctness of your algorithm. 5 Q.4 (6 pts) Maximum Interval Given a sequence of n numbers: a1, a2, . . . , an, try to find an interval [p, q] (1 ≤ p ≤ q ≤ n) so that ∑q i=p ai is maximized. For example, if the input sequence is 3,−4, 6, 2,−3, 1, 4,−8, 7, then the output should be [3, 7] with the maximum sum being 6 + 2 + (−3) + 1 + 4 = 10. Give a divide-and-conquer algorithm that runs in time O(n log n). You need to analyze the running time of your algorithm. 6 Q.5 (6 pts) Number of Shortest Path Given an n×m matrix A where one needs to traverse from A[0][0] to A[n−1][m−1]. From a given cell [i][j] we could only move to the cell to the right or below the current cell, i.e., A[i+ 1][j] or A[i][j+ 1]. Each valid path has an associated cost, which is defined to be the sum of all the cells in the path (including the two end cells). We are interested in the path with the lowest cost. Note that there could be multiple such paths with the lowest cost. Design a dynamic programming algorithm that outputs the total number of paths that have the lowest cost. 7 Q.6 (6 pts) Minimum Spanning Tree Suppose you have an undirected graph G = (V,E) with |V | = n vertices and |E| = n+ 99 edges, and distinct edge-costs. Design and analyze an O(n) time algorithm which on such input graphs G returns a minimum spanning tree of G. (Hint: using the cycle property of the MST) 8 Q.7 (6 pts) Travelling in Europe Suppose that you are traveling in Europe from city 1 to city n via the cities 2, 3, . . . , n− 1 in this order, and only by using rented cars. You know in advance that for every 1 ≤ i < j ≤ n the cost of renting from city i to city j is cij . These costs are arbitrary: there is no order relation between the costs of any 2 pairs of cities, so for example c12 = 30 and c14 = 5 is allowed. Your goal is to get to location n while spending as little as possible on car rental. Give an efficient dynamic programming algorithm that outputs the choices that you should make to achieve this goal. Please analyze the running time of your algorithm. To get full points, the running time of your algorithm should be O(n2). 9 This page is intentionally left blank. 10
