algorithm questions

Intro to Algorithms T, 11:00 AM - 12:15 PM/Lectures online Spring 2021 HW 2 Exercise 1 (1 pt each). Solve the following recurrence relations and give a bound for each of them 1. T(n) 22T(n/3) +1 2. T(n) = 5T (n/4) + n 3. T(n) = 6T (7/7) +n 4. T(n) S9T(n/3) + m2 5. T(n) = 87(1/2) +m Exercise 2 (2 pts - Ipt each). Suppose you are choosing between the following three algo rithms; 1. Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. 2. Algorithm B solves problems of size n by recursively solving two subproblems of size n-1 and then combining the solutions in constant time. (Bonus (2pts: not i master theorem-treed to use substitution method, consult the CLRS book!) 3. Algorithm C solves problems of size ni boy dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n) time. What is the running time of each of these algorithms (in asymptotic notation), and which would you choose? Exercise 3 (3 pts). Consider the following program: function 1 if n > 1: print.line("still going) 1 (n/2) (n/2) How many lines, as a function of n (in e() form), does this program print? Write a recurrente relation and solve it. You may assume that is a power of 2. Exercise 2 (2 pts - lpt each). Suppose you are choosing between the following three algo rithms: 1. Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. 2. Algorithm B solves problems of size n by recursively solving two subproblems of size n - 1 and then combining the solutions in constant time. (Bonus (2pts): not a master theorem - need to use substitution method, consult the CLRS book!) 3. Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n) time. What is the running time of each of these algorithms (in asymptotic notation), and which would you choose? Exercise 3 (3 pts). Consider the following program: function f if n > 1: print.line(''still going!) f(n/2) f(n/2) How many lines, as a function of n (in (s) form), does this program print? Write a recurrence relation and solve it. You may assume that n is a power of 2. Exercise 4 (Bonus exercise, 3 pts). Describe an O(n) algorithm that takes as input an array A of n real numbers sorted in nondecreasing order and a values. The algorithm returns "true" if there are distinct indexes i and j such that A[i] + AG] =and "false" otherwise. 1