Homework answers / question archive / Foundations of Algorithms, Fall 2020 Homework #1  All members of the collaboration group are expected to participate fully in solving collaborative problems, and peers will assess performance at the end of the assignment

Foundations of Algorithms, Fall 2020 Homework #1  All members of the collaboration group are expected to participate fully in solving collaborative problems, and peers will assess performance at the end of the assignment

Computer Science

Share With

Foundations of Algorithms, Fall 2020 Homework #1 
All members of the collaboration group are expected to participate fully in solving collaborative problems, and peers will assess performance at the end of the assignment. Note, however, that each student is required to write up their solutions individually. Common solution descriptions from a collaboration group will not be accepted. Furthermore, to receive credit for a collaboration problem, each student in the collaboration group must actively and substantially contribute to the collaboration. This implies that no single student should post a complete solution to any problem at the beginning of the collaboration process. 1. [10 points] Describe the time complexity of the this linear search algorithm. Choose the tightest asymptotic representation, from e, O, or Ω, and argue why that is the tightest bound. 
LINEAR-SEARCH(x, A) 1 i = 1 //Arrays in the text begin at 1 in all but one case this semester 2 while i ≤ n and x =? A[i] 3 
i = i + 1 4 if i ≤ n 5 location = i 6 else location = 0 7 return location 
2. [15 points] Consider this binary search algorithm. This algorithm is different than the algorithm on page 799 of the CLRS text. Array A is a sorted list of elements. x may or may not be in A. 
BINARY-SEARCH(x, A) 1 i = 1 //Arrays in the text begin at 1 in all but one case this semester 2 j = n 3 while i < j 4 m = [(i + j)/2] 5 if x > A[m] 6 i = m + 1 7 else j = m 8 if x = A[i] 9 location = i 10 else location = 0 11 return location 
(a) [10 points] Describe the time complexity of the binary search algorithm in terms of number of comparisons used (ignore the time required to compute m = [(i + j)/2] in each iteration of the loop in the algorithm). Choose the tightest asymptotic representation, from e, O, or Ω, and argue why that is the tightest bound. 
(b) [5 points] Make one small change to the algorithm above to improve its runtime, and give the revised tightest asymptotic representation, from e, O, or Ω. Show your change using proper pseudocode. If the asymptotic representation changed from your answer to 2a, argue why it is different. 3. [10 points] Give asymptotic upper and lower bounds for T(n) = 4T(n/4) + n2, assuming T(n) is constant for sufficiently small n. Make your bounds as tight as possible. Prove that your bounds are correct. 4. [15 points] Give asymptotic upper and lower bounds for T(n) = 3T (n 3 + 1) + n, assuming T(n) is constant for sufficiently small n. Make your bounds as tight as possible. Prove that your bounds are correct. 5. [15 points] Give asymptotic upper and lower bounds for T(n) = T(√n) + 1, assuming T(n) is constant for sufficiently small n. Make your bounds as tight as possible. Prove that your bounds are correct.