Problem 1.

(a)  Determine the strongest asymptotic relation between the functions

f (n) = 2log n      and   g(n) = (log n)4 ,

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.                                                                (15 points)

(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) < 4 . T (n/3) + O(n3 )

Problem 2.  Consider the algorithm below for checking whether a string represented in an array A of n characters is a palindrome. A palindrome is defined as a word that is spelled the same forward and backward (e.g. rotor, kayak).

CHECK-PALINDROME(A[1 : n]):

1. If n = 0 or n = 1, return True.

2.  Otherwise, if A[1] = A[n] and CHECK-PALINDROME(A[2 : n _ 1]) returns True, return True.

3.  Return False.

We analyze CHECK-PALINDROME  in this question.

(a)  Use induction to prove the correctness of this algorithm.                                                   (15 points)

(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)

Problem 3. You are given an unsorted array A[1 : n] of n distinct positive integers.  Design an algorithm that in O(n + M) worst-case time, where M is the maximum possible integer within A finds the h-index of

A. The h-index is defined as the maximum integer h such that A[1 : n] has at least h indices whose entry is at least h.       (25 points)

Remember to separately write your algorithm (10 points), the proof of correctness (10 points), and runtime analysis (5 points).

Example .  For n = 8 and A = [9, 8, 70, 30, 2, 7, 4, 5] the correct answer is 5 (because the largest integer, h, such that h of the integers in A are at least h is 5).

Bonus part. If instead of an O(n + M) worst-case time algorithm, you design an algorithm with worst-case runtime of O(n), i.e., with no dependence on M, you receive +5 extra credit points.

Problem 4. We want to give our dog a collection of treats with total satisfaction value exactly equal to S . For that, we have a collection of n different treats in an array T [1 : n] where T [i] is the satisfaction value of the i-th treat (all treats have distinct satisfaction values).  Our goal is to give our dog treat satisfaction of exactly S by giving her the smallest possible number of treats or outputting that it is not possible with this collection of treats.  Design a dynamic programming algorithm for this problem of outputting the number of treats we should give our dog with worst-case runtime of O(n . S).                  (25 points)

Remember to separately  write your specification of recursive formula in plain English (7.5 points), your recursive solution for the formula and its proof of correctness  (7.5  points), the algorithm using either

memoization or bottom-up dynamic programming (5 points), and runtime analysis (5 points). Example:

● Given S = 15, n = 7, and T = [4, 9, 3, 2, 7, 5, 6], the correct answer is 2 by picking T [2] = 9 and T [7] = 6 which add up to 15.

● Given S = 11, n = 4, and T = [4, 3, 5, 9], the correct answer is that ‘the satisfaction cannot be met’ as no combination of these treats adds up to a value of 11 (recall that we can only use each treat once).

Problem 5  (Extra credit).  You are given 3 unsorted  arrays, A[1 : n], B[1 : n], and C[1 : n], each of n integers, and a integer called target.  Design an algorithm that in O(n2 ) worst case runtime finds a tuple (i, j, k) such that A[i] + B[j] + C[k] is equal to target. If there are multiple tuples, you only have to output

one of them. If there exists no tuple, output “no solution.”                                                        (+10 points)

Example:   Given A =  [3, 2, 7, 8, 1, 4, 5, 6], B  =  [1, 2, 5, 2, _20, _3, 10, 0], C =  [17, _2, 3, 9, 11, _4, 8, 8], and target= 17 one right answer is to output (1, 3, 4).  This is because A[1] = 3, B[3] = 5, and C[4] = 9, and 3 + 5 + 9 = 17.