Class on Design and Analysis of Algorithms, Solutions to Quiz 1

March 16, 2015 6.046J/18.410J Quiz 1 Solutions Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas, and Nancy Lynch Quiz 1 Solutions • • • • • • • • • Do not open this quiz booklet until you are directed to do so. Read all the instructions first. The quiz contains 7 problems, with multiple parts. You have 120 minutes to earn 120 points. This quiz booklet contains 12 pages, including this one. "" This quiz is closed book. You may use one double-sided letter (8 12 × 11"" ) or A4 crib sheet. No calculators or programmable devices are permitted. Cell phones must be put away. Do not waste time deriving facts that we have studied. Just cite results from class. When we ask you to “give an algorithm” in this quiz, describe your algorithm in English or pseudocode, and provide a short argument for correctness and running time. You do not need to provide a diagram or example unless it helps make your explanation clearer. Do not spend too much time on any one problem. Generally, a problem’s point value is an indication of how many minutes to spend on it. Show your work, as partial credit will be given. You will be graded not only on the correct­ ness of your answer, but also on the clarity with which you express it. Please be neat. Good luck! Problem Title Parts 1 True or False 40 10 2 Fast Fourier Transform 5 1 3 Yellow Brick Road 10 1 4 Amortized Analysis 15 1 5 Verifying Polynomial Multiplication 15 4 6 Dynamic Programming 15 2 7 Median of Sorted Arrays 20 3 Total Name: Points 120 Grade Initials 6.046J/18.410J Quiz 1 Solutions Name 2 Problem 1. True or False. [40 points] (10 parts) Circle T or F for each of the following statements to indicate whether the statement is true or false and briefly explain why. (a) T F [4 points] With all equal-sized intervals, a greedy algorithm based on earliest start time will always select the maximum number of compatible intervals. Solution: True. The algorithm is equivalent to the earliest finish time algorithm. (b) T F [4 points] The problem of weighted interval scheduling can be solved in O(n log n) time using dynamic programming. Solution: True. The algorithm was covered in recitation. (c) T F [4 points] If we divide an array into groups of 3, find the median of each group, recursively find the median of those medians, partition, and recurse, then we can obtain a linear-time median-finding algorithm. Solution: False. T (n) = T (n/3) + T (2n/3) + O(n) does not solve to T (n) = O(n). The array has to be broken up into groups of at least 5 to obtain a lineartime algorithm. (d) T F [4 points] If we used the obvious Θ(n2 ) merge algorithm in the divide-and­ conquer convex-hull algorithm, the overall time complexity would be Θ(n2 log n). Solution: False. The time complexity would satisfy the recurrence T (n) = 2T (n/2) + Θ(n2 ), which solves to Θ(n2 ) by the Master Theorem. (e) T F [4 points] Van Emde Boas sort (where we insert all numbers, find the min, and then repeatedly call S UCCESSOR) can be used to sort n = lg u numbers in O(lg u· lg lg lg u) time. Solution: False. Inserting into the tree and then finding all the successors will take n lg lg(u) time, which in terms of u is lg(u) · lg lg(u). 6.046J/18.410J Quiz 1 Solutions Name (f) T F [4 points] Van Emde Boas on n integers between 0 and u − 1 supports successor queries in O(lg lg u) worst-case time using O(n) space. Solution: False. We use Θ(u) space or do randomization. (g) T F [4 points] In the potential method for amortized analysis, the potential energy should never go negative. Solution: True. (h) T F [4 points] The quicksort algorithm that uses linear-time median finding to run in worst-case O(n log n) time requires Θ(n) auxiliary space. Solution: False. It can be implemented with O(log n) auxiliary space. (i) T F [4 points] Searching in a skip list takes Θ(log n) time with high probability, but could take Ω(2n ) time with nonzero probability. Solution: True. A skip list could be of any height with nonzero probability, depending on its random choices. Alternative solution: False. We can limit the height of the skip list to O(n) or O(lg n) to get O(n) worse-case cost. Common mistake 1: We go through each element at least once. (Wrong because we also need to “climb up” the skip lists. Common mistake 2: The worst case is when none of the elements is promoted, or all of the elements are promoted to the same level, in which cases skip lists become a linked list. (j) T F [3 points] The following collection H = {h1 , h2 , h3 } of hash functions is uni­ versal, where each hash function maps the universe U = {A, B, C, D} of keys into the range {0, 1, 2} according to the following table: x h1 (x) h2 (x) h3 (x) A 1 0 2 B C D 0 1 1 1 0 1 2 1 0 Solution: False. A and C collide with probability 2/3. 3 6.046J/18.410J Quiz 1 Solutions Name 4 Problem 2. Fast Fourier Transform (FFT). [5 points] (1 part) Ben Bitdiddle is trying to multiply two polynomials using the FFT. In his trivial example, Ben sets a = (0, 1) and b = (0, 1), both representing 0 + x, and calculates: A = F(a) = B = F(b) = (1, −1), C = A ∗ B = (1, 1), c = F −1 (C) = (1, 0). So c represents 1 + 0 · x, which is clearly wrong. Point out Ben’s mistake in one sentence; no calculation needed. (Ben swears he has calculated FFT F and inverse FFT F −1 correctly.) Solution: The resulting polynomial is of degree 2, so Ben need to pad a and b with zeroes. (Or Ben need at least 3 samples to do FFT). Here is the correct calculaton (not required in the solution). Let a = b = (0, 1, 0, 0); then, A = F(a) = B = F(b) = (1, −i, −1, i) C = A ∗ B = (1, −1, 1, −1) c = F −1 (C) = (0, 0, 1, 0) which represents x2 . It is also OK to set a = b = (0, 1, 0). Common mistake 1: A ∗ B should be convolution. Common mistake 2: Ben should reverse b. Both mistakes confuse the relation between convolution, polynomial multiplication and FFT cal­ culation. If one computes convolution directly (without FFT), one needs to reverse the second vector. FFT provides a faster way to compute convolution and polynomial multiplication (these two are the same thing). Using the FFT, one should perform FFT on the two original vectors (no reversal). Then, after the FFT, one only needs to do element-wise multiplication (as opposed to convolution), which Ben performed correctly. 6.046J/18.410J Quiz 1 Solutions Name 5 Problem 3. Yellow Brick Road. [10 points] (1 part) Prof. Gale is developing a new Facebook app called “Yellow Brick Road” for maintaining a user’s timeline, here represented as a time-ordered list e0 , e1 , . . . , en−1 of n (unchanging) events. (In Facebook, events can never be deleted, and for the purposes of this problem, don’t worry about insertions either.) The app allows the user to mark an event ei as yellow (important) or grey (unimportant); initially all events are grey. The app also allows the user to jump to the next yellow event that comes after the event ei currently on the screen (which may be yellow or grey). More formally, you must support the following operations: 1. M ARK -Y ELLOW(i): Mark ei yellow. 2. M ARK -G REY(i): Mark ei grey. 3. N EXT-Y ELLOW(i): Find the smallest j > i such that ej is yellow. Give the fastest data structure you can for this problem, measured according to worst-case time. The faster your data structure, the better. Hint: Use a data structure you have seen in either 6.006 or 6.046 as a building block. Solution: Initialization takes O(n lg(lg(n))) time to insert all the yellow elements into a VEB tree, V . More importantly, each operation takes O(lg lg(n)) time. When a user asks to M ARK -Y ELLOW(i), then call V.insert(i) which takes O(lg lg(n)) time. When a user asks to M ARK -G REY(i), then call V.delete(i) which takes O(lg lg(n)) time. When a user asks to N EXT-Y ELLOW(i), then call V.successor(i) which takes O(lg lg(n)) time. Another slower solution used an AVL tree in place of a vEB for an O(lg(n)) runtime for the operations. Common mistake 1: Claiming operations took O(lg lg(u)). The universe size is exactly n, and the term u was undefined. Common mistake 2: Inserting both yellow and grey elements into the same data structure without an augmentation to keep track of whether any yellow elements existed within children. NextYellow could take O(n) in the worst case. Common mistake 3: Use a skip list to keep track of all yellow elements. Some operations would take O(lg(n)) with high probability, but O(n) worst case. Common mistake 4: Using a skip list capped at 2 levels, doubly linked list, or hash table. Some operations would take O(n) worst case. 6.046J/18.410J Quiz 1 Solutions Name 6 Problem 4. Amortized Analysis. [15 points] (1 part) Design a data structure to maintain a set S of n distinct integers that supports the following two operations: 1. I NSERT (x, S): insert integer x into S. 2. R EMOVE - BOTTOM - HALF (S): remove the smallest n 2 integers from S. Describe your algorithm and give the worse-case time complexity of the two operations. Then carry out an amortized analysis to make I NSERT (x, S) run in amortized O(1) time, and R EMOVE ­ BOTTOM - HALF (S) run in amortized 0 time. Solution: Use a singly linked list to store those integers. To implement I NSERT (x, S), we append the new integer to the end of the linked list. This takes Θ(1) time. To implement R EMOVE - BOTTOM ­ HALF (S), we use the median finding algorithm taught in class to find the median number, and then go through the list again to delete all the numbers smaller or equal than the median. This takes Θ(n) time. Suppose the runtime of R EMOVE - BOTTOM - HALF (S) is bounded by cn for some constant c. For amortized analysis, use Φ = 2cn as our potential function. Therefore, the amortized cost of an insertion is 1 + ΔΦ = 1 + 2c = Θ(1). The amortized cost of R EMOVE - BOTTOM - HALF (S) is cn + ΔΦ = cn + (−2c × n2 ) = 0. 6.046J/18.410J Quiz 1 Solutions Name 7 Problem 5. Verifying Polynomial Multiplication. [15 points] (4 parts) This problem will explore how to check the product of two polynomials. Specifically, we are given three polynomials: p(x) = an xn + an−1 xn−1 + · · · + a0 , q(x) = bn xn + bn−1 xn−1 + · · · + b0 , r(x) = c2n x2n + c2n−1 x2n−1 + · · · + c0 . We want to check whether p(x) · q(x) = r(x) (for all values x). Via FFT, we could simply compute p(x) · q(x) and check in O(n log n) time. Instead, we aim to achieve O(n) time via randomization. (a) [5 points] Describe an O(n)-time randomized algorithm for testing whether p(x) · q(x) = r(x) that satisfies the following properties: 1. If the two sides are equal, the algorithm outputs YES. 2. If the two sides are unequal, the algorithm outputs NO with probability at least 12 . Solution: Pick a value a ∈ [1, 4n], and check whether p(a)q(a) = r(a). The algo­ rithm outputs YES if the two sides are equal, and NO otherwise. It takes O(n) time to evaluate the three polynomials of degree O(n). Thus the overall running time of the algorithm is O(n). (b) [2 points] Prove that your algorithm satisfies Property 1. Solution: If p(x) · q(x) = r(x), then both sides will evaluate to the same thing for any input. 6.046J/18.410J Quiz 1 Solutions Name (c) [3 points] Prove that your algorithm satisfies Property 2. Hint: Recall the Fundamental Theorem of Algebra: A degree-d polynomial has (at most) d roots. Solution: s(x) = r(x) − p(x) · q(x) is a degree-2n polynomial, and thus has at most 2n roots. Then 2n 1 Pr{s(a) = 0} ≤ = 4n 2 since a was picked from a set of size 4n. (d) [5 points] Design a randomized algorithm to check whether p(x) · q(x) = r(x) that is correct with probability at least 1 − ε. Analyze your algorithm in terms of n and 1/ε. Solution: We run part a m times, and output YES if and only if all answers output YES . In other words, we amplify the probability of success via repetition. m Our test works with probability ≥ 1 − 12 . Thus we need � �m 1 ≤ε 2 1 ⇒ m ≥ log . ε 8 6.046J/18.410J Quiz 1 Solutions Name 9 Problem 6. Dynamic Programming. [15 points] (2 parts) Prof. Child is cooking from her garden, which is arranged in grid with n rows and m columns. Each cell (i, j) (1 ≤ i ≤ n, 1 ≤ j ≤ m) has an ingredient growing in it, with tastiness given by a positive value Ti,j . Prof. Child doesn’t like cooking “by the book”. To prepare dinner, she will stand at a cell (i, j) and pick one ingredient from each quadrant relative to that cell. The tastiness of her dish is the product of the tastiness of the four ingredients she chooses. Help Prof. Child find an O(nm) dynamic programming algorithm to maximize the tastiness of her dish. Here the four quadrants relative to a cell (i, j) are defined as follows: top-left bottom-left top-right bottom-right = = = = {all cells (a, b) | a < i, b < j}, {all cells (a, b) | a > i, b < j}, {all cells (a, b) | a < i, b > j}, {all cells (a, b) | a > i, b > j}. Because Prof. Child needs all four quadrants to be non-empty, she can only stand on cells (i, j) where 1 < i < n and 1 < j < m. (a) [10 points] Define TLi,j to be maximum tastiness value in the top-left quadrant of cell (i, j): TLi,j = max{Ta,b | 1 ≤ a ≤ i, 1 ≤ b ≤ j}. Find a dynamic programming algorithm to compute TLi,j , for all 1 < i < n and 1 < j < m, in O(nm) time. Solution: When trying to calculate TLi,j , we see that the maximum can be at cell (i, j). If not, it must lie either in the rectangle from (1, 1) to (i, j − 1), or the rectangle from (1, 1) to (i − 1, j), or both. These three overlapping cases cover our required rectangle. We have then, TLi,j = max{Ti,j , TLi−1,j , TLi,j−1 } For the base cases, we can just set TL0,j = TLi,0 = 0 for all valid values of i and j. We can compute the DP value for each state in O(1) time. There are nm states, so our algorithm is O(nm). 6.046J/18.410J Quiz 1 Solutions Name 10 (b) [5 points] Use the idea in part (a) to obtain an O(nm) algorithm to find the tastiest dish. Solution: In part (a) we calculated range maximum for the top-left quadrant. We can similarly define range maximums for the other quadrants. Let BLi,j = max{Ta,b | i ≤ a ≤ n, 1 ≤ b ≤ j}, TR i,j = max{Ta,b | 1 ≤ a ≤ i, j ≤ b ≤ m}, and BR i,j = max{Ta,b | i ≤ a ≤ n, j ≤ b ≤ m}. Each of these can be computed in O(nm) time similar to TL. To calculate the tastiest dish Prof. Child can cook when she stands at cell (i, j) (1 < i < n and 1 < j < m), we now just need to compute the product TLi−1,j−1 BLi+1,j−1 TR i−1,j+1 BR i+1,j+1 and pick the maximum product. This can be done in O(nm) time. 6.046J/18.410J Quiz 1 Solutions Name 11 Problem 7. Median of two sorted arrays. [20 points] (3 parts) Finding the median of a sorted array is easy: return the middle element. But what if you are given two sorted arrays A and B, of size m and n respectively, and you want to find the median of all the numbers in A and B? You may assume that A and B are disjoint. (a) [3 points] Give a naı̈ve algorithm running in Θ(m + n) time. Solution: Merge the two sorted arrays (which takes O(m + n) time) and find the median using linear-time selection. (b) [10 points] If m = n, give an algorithm that runs in Θ(lg n) time. Solution: Pick the median m1 for A and median m2 for B. If m1 = m2 , return m1 . If m1 > m2 , remove the second half of A and the first half of B. Then we get two subarrays with size n/2. Repeat until both arrays are smaller than a constant. m1 < m2 is symmetric. 6.046J/18.410J Quiz 1 Solutions Name (c) [7 points] Give an algorithm that runs in O(lg(min{m, n})) time, for any m and n. Don’t spend too much time on this question! Solution: Without loss of generality, assume |A| = m > n = |B|. We can safely n n remove elements A[0 : m− ] and A[ m+ : m − 1] because none of these elements can 2 2 be the median of A + B. After this process, we get two arrays of size approximately n. Then we can run part (b). The complexity is Θ(lg(min(m, n))) 12