Georgia Institute Of Technology CS 8803 A Exam 1 Solutions-ALL CORRECT

Document Content and Description Below

CS 8803GA Exam 1 Solutions February 6, 2018 Problem 1: Majority Element You are given as an input a list of n objects A = [a1; a2; :::; an] where n is a power of 2. In O(1) time you can check if tw... o objects are the same or not. We say there is a majority element if there is an element which appears in the list A more than n=2 times. Give a divide and conquer algorithm to check if there is a majority element. Your algorithm should run in O(n log n) time. Note, for two objects ai and aj you can check in constant time if ai == aj? But you cannot order them such as ai < aj or ai > aj, that does not make sense with these objects (think of them as new symbols). Hence, you cannot sort these objects or find their median. Explain your algorithm in words, and analyze the running time of your algorithm including stating the recurrence. And explain why your algorithm is correct. Note, there is an O(n) time algorithm for this problem, but you will not receive extra credit for that solution, so we suggest aiming for the simpler O(n log n) time algorithm. Solution. First, note that if there is a majority element in the entire array, then it must be the majority element in either the first half of the array or the second half of the array (or both). This suggests the following divide and conquer algorithm. We first divide the array into 2 halves: the left half and the right half. We recursively find the majority element in the left half, if there is one, and in the right half, if there is one. Let ‘ denote the majority element in the left half and r the majority in the right half. We then scan through the entire array A and count the number of occurrences of ‘ and the number of occurrences of r. If one of these two candidates occurs > n=2 times then we return it as the majority element of the entire array, otherwise we return NULL. Solution. Running time: The running time of this algorithm satisfies the recurrence: T(n) = 2T(n2) + O(n), since there are two recursive calls on half the input, plus O(n) work to determine which candidate element (if any) is the majority element. This recurrence solves to O(n log n), as desired. Since a majority element must appear > n=2 times there can be ≤ 1 majority element. Note that any element that appears ≤ n=4 times in the left half and ≤ n=4 times in the right half will appear ≤ n=2 times in the entire array and hence is not a majority element. Therefore, if there is a majority element m in the entire array A then it must be a majority element in the left half or in the right half, or in both halves. So the only possible majority element for the entire array A are the 2 majority elements of the left and right halves, this is why the algorithm is correct. 1Problem 2: Neighboring-product sum Given a list of n positive integers A = [a1; :::; an], we are looking for the largest neighboringproduct sum. Adjacent elements can be multiplied together (but don’t have to) and then we sum up. Each element can be matched with at most one of its neighbors. Here are some examples. Given the list A = [1; 4; 2; 3; 7; 4; 1], the max neighboring-product sum is 41 = 1 + (4 × 2) + 3 + (7 × 4) + 1 Note, in this example you cannot use something like (4 × 2 × 3) since 2 can get paired with at most one neighbor. Given A = [2; 2; 1; 3; 2; 1; 2; 2; 1; 2] the max neighboring-product sum is 19 = (22) + 1 + (32) + 1 + (22) + 1 + 2 Hence, we pair some elements with one of their neighbors, these pairs are multiplied together, and then we add up the new numbers (either original unpaired elements or product of paired elements). Design a dynamic programming algorithm to find the max neighboring-product sum. (Faster (and correct) algorithm in O(·) notation is worth more credit.) (a) Define the entries of your table in words. E.g., T(i) is ..., or T(i; j) is .... Hint: Your table T should be one-dimensional. Solution. T(i) is the maximum neighboring-product sum for elements a1; :::ai. (b) State the recurrence for the entries of your table in terms of smaller subproblems. Hint: Express T(i) in terms of T(i1) and T(i2). Solution. T(i) = maxfT(i − 1) + ai; T(i − 2) + (ai × ai−1)g (c) Write pseudocode for your algorithm to solve this problem. Solution. T(0) = 0 T(1) = a1 for i = 2 ! n do: T(i) = maxfT(i − 1) + ai; T(i − 2) + (ai × ai−1)g return T(n) (d) Analyze the running time of your algorithm. 2Solution. There are n + 1 entries in table T , each of which requires constant work to compute (comparing two easily computable expressions). Therefore, the algorithm is O(n) [Show More]

Last updated: 2 years ago

Preview 1 out of 8 pages