Description
Problem 1. (a) Determine the strongest asymptotic relation between the functions f(n) = p log n and g(n) = n 2 (log log n) , i.e., whether f(n) = o(g(n)), f(n) = O(g(n)), f(n) = Ω(g(n)), f(n) = ω(g(n)), or f(n) = Θ(g(n)). Remember to prove the correctness of your choice. (10 points) 2 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. (b) Use the recursion tree method to solve the following recurrence T(n) by finding the tightest function f(n) such that T(n) = O(f(n)): (10 points) T(n) ≤ 8 · T(n/2) + O(n 3 ). (You do not have to prove that your function is the tightest one.) 3 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. Problem 2. Consider the algorithm below for finding the total sum of the numbers in any array A[1 : n]. TOTAL-SUM(A[1 : n]): 1. If n = 0: return 0. 2. If n = 1: return A[1]. 3. Otherwise, let m1 ← TOTAL-SUM(A[1 : n 2 ]) and m2 ← TOTAL-SUM(A[ n 2 + 1 : n]). 4. Return m1 + m2. We analyze TOTAL-SUM in this question. (a) Use induction to prove the correctness of this algorithm. (10 points) 4 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. (b) Write a recurrence for this algorithm and solve it to obtain a tight upper bound on the worst case runtime of this algorithm. You can use any method you like for solving this recurrence. (10 points) 5 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. Problem 3. You are given a collection of n integers a1, . . . , an with positive weights w1, . . . , wn. For any number ai , we define the bias of ai as: bias(ai) = | X j:aj B[n]. Design and analyze an algorithm that in O(log n) time finds an index j ∈ [1 : n] such that A[j] < B[j] but A[j + 1] > B[j + 1]. Hint: Start by convincing yourself that such an index j always exist in the first place. (+10 points) 14 Only for the personal use of students registered in CS 344, Spring 2021 at Rutgers University. Redistribution out of this class is strictly prohibited. Extra Workspace 15
