Sample Problems: Divide & Conquer Chapter 5

COMP 482 Sample Problems: Divide & Conquer Problem 1. (10 points) For each of the following statements determine whether it is true of false. (+1 for a correct answer, -0.5 for an incorrect answer, 0 for a blank). Divide and Conquer algorithms often perform run more quickly than brute force. ClosestPairOfPoints has a O(lg(n)) time algorithm. The Master Theorem can be used to find the time complexity of all algorithms. Merge Sort is an O(lg(n)) time algorithm. Every algorithm to multiply n-bit numbers requires ⌦(n2 ) bit operations. There is an O(n) time divide and conquer algorithm for CountingInversions. Brute force algorithms are a special case of divide and conquer algorithms. The binary search algorithm works even if the array is not sorted. T T T T T T T T F F F F F F F F Problem 2. (10 points) In class, we presented an O(N lg(N )) algorithm to solve CountingInversions. Use this algorithm to determine the number of inversions in the array below (perhaps note that the array has size 20 and the first 10 entries and second 10 entries of the array are sorted). Show enough work to convince me that you are using the algorithm and that your answer isn’t just a guess or arrived at via brute force. 3 6 7 12 15 17 25 30 32 43 1 4 9 10 19 21 23 27 29 36 Problem 3. (10 points) MissingNumber is a problem that you (probably) have not seen. The input is a sorted array with size N that contains all but one number from the set {0, 1, 2, 3, . . . , N }. The goal is to find which one value is not included in the array. For example, if N = 15 and the array contained 0 1 2 3 4 5 6 7 8 10 11 12 13 14 15 then the answer is 9. Describe a O(lg(N )) time, divide and conquer algorithm which solves MissingNumber. Problem 4. (10 points) Use the divide and conquer method described in class to solve the following instance of CountingInversions: (2,6,4,1,3,7,8,5). Problem 5. (10 points) Let S = S1 [ S2 where S1 = {( 8, 1), ( 7, 5), ( 7, 10), ( 5, 0), ( 5, 7), ( 5, 4), ( 4, 6), ( 2, 2), (0, 12), (1, 5)}, and S2 = {(3, 6), (4, 2), (4, 3), (5, 9), (6, 5), (8, 2), (8, 2), (8, 6), (9, 9), (9, 9)}. Note that every element of S1 has an x-value less than 2, every element of S2 has an x-value greater than 2, the closest pair of points in S1 is (-5,7) and (-5,4), and the closest pair of points in S2 is (8,6) and (9,9). Describe a O(n lg(n)) time algorithm to find the closest pair of points in a plane. Use your algorithm to find the closest pair of points in S. Problem 6. (10 points) Imagine that you have an algorithm where the number of steps satisfies the following equation T (n) = 8T (n/2) + n lg(n) + 2n and T (1) = 3. Use any of the 3 techniques taught in class to show that T (n) = O(n3 ). Problem X 7. (10 points) Imagine that you have an algorithm where the number of steps satisfies the following equation T (n) = 9T (n/3) + n lg(n) + n2 and T (1) = 3. Use the Master Theorem to determine the asymptotic runtime (ie find the function f(n) such that T (n) = ⇥(f (n))). Problem 8. (10 points) Find the number of inversions in the following array without applying brute force. You may want to note that the first 10 items are sorted in reverse order and the last 10 items are sorted in order. Show enough work or explanation to see that you aren’t using an O(n2 ) brute force algorithm. 81 77 73 69 66 62 52 41 36 23 12 31 33 57 61 68 75 Problem 9. (10 points) Imagine that an array was created by the following process: 1) Create a sequence of n distinct integers. 76 78 79 2) Append the sequence to itself. 3) Remove one of the entries from the second half. For example: Step 1: 3 7 Step 2: 3 7 Step 3: 3 7 2 2 2 1 1 1 8 8 8 3 3 7 7 2 1 1 8 8 Find (describe) an O(lg n) time divide and conquer algorithm which receives an array created by the process above and determines which entry was removed. Problem 10. (10 points) Imagine that an array was created by the following process: 1) An even length palindrome without repeated characters is selected. 2) One of the entries was removed For example: Step 1: a ! Step 2: a ! E E d d * * * * d d E E ! a a Find (describe) an O(lg n) time divide and conquer algorithm which receives an array created by the process above and determines which entry was removed. 11. (10 points) Assume that you have an algorithm for problem X which works by splitting into three XProblem problems each half as big as the original and combining the solutions in time 4n . 3 Write a recurrence for T (n) (the amount of time necessary to run the algorithm on a problem of size n) and solve the recurrence using the master theorem. X Problem 12. (10 points) Determine the f(n) for which T (n) = ⇥(f (n)) (show enough work that I can determine you didn’t just guess an answer). T (n) = T (2n/3) + n2 + nlg 2 (n) X Problem 13. (10 points) Assume that you have an algorithm which works by splitting the problem into 3 equal sized subproblems, solving each seperately, and then performing a linear amount of work on the results of the subproblems to get the solution to the original version. Find the time complexity (big-⇥) for this algorithm. Time 0(Nlog (N) algorithm = 3167112 CountingInversions . 1149110 19121232 131172513032143 , 29s , o 31617/1215(1/251302432/439/101921 23122/29136 0+ 0 + 0 0 8 4 34679 IS 1012 0 + 12 + 8 + 7 + + 0 + 0 2 + 2 + 2 + 2 17192125 5 + 5 + 41 2 + 2 + + 4 + = · 0 + 0 0 0 +0 + 0 +o + 0 30132143 23/27/29/3 0 + 0 + 0 0 +0 + 0 + 0 + 0 151719212325272930323643 346791012 1 0 + 24 9 10 19.21324323/27/29/3 316/7/12/18/17125/30 1 2 + 2 0 + 0 + 00 + o + 4 +3 + 3 +1 inversions 53 1234567891011 12 13 14 D & public static findmissing No int int low int high while Missing Number & class public = (low int mid N = 3 = ; (low == mid + 1 ; thigh) ; 2 mid) [ // missing 3 return low ; ; //missing [ T no is in right else high-mid 3 intros high) < if (aur [mid] low Lintca 0 ; = no is in the left = = = & 7 v I just nigh = 11 [= high = q 8 819 mid 8 low , * = = = = z 8+ 1 While = 9 (99) return o a 6413785: n/2 n/z 3578 1246 2 3+ 1 1234567 = 4 + 2 + 2 9 = Algorithm + 8 1 inversi for pair of points closest in a plane . So in the ↑, Pz = (X , - Xz) = + (y - , yz)2 strip , we sort it by . y coordinate 7816973 41522336 12131335761687576 6766 , , , , 7879 69737781416262661223313633376168757628k9 1 + 1 + 2 + 2 ( + 1 + 2+ 2 + 0 + 2+ 1 415262666973778812 6+ 6 + . 1 0 + 0 0+0 23343336576168757628k9 4 + 4+4+ 4 4 + 1 + 0+0 6 12 12233135364192376162666869737781757628k9 28 + 5 +2 2 + + 8 +8 +2 +6+ 6+ 4 0+0 1223313536415237616266686973757677787981 89 + 2 + 2 left = right while + 1 +1 n = 2n-2 right) [ mid (leftright, if (A [mid] A[mid-n]) (Left < = = else left = mid : right return A = +1 ; mid ; [left-n] ;