Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
1. [15 points] Find the complexity of the following recurrences by expanding. Assume
T(1) = 1. The following recurrences are given for n > 1.
(i) T(n) = T(n / 2) + 1
(ii) T(n) = T(n / 2) + n
(iii) T(n) = T(n / 2) + n^2
(iv) T(n) = 2 T(n / 2) + 1
(v) T(n) = 2 T(n / 2) + n
() T(n) = 2 T(n / 2) + n^2
(i) T(n) = 3 T(n / 2) + n^(log
2 3)
2. [5 points] For each of the following recurrences, give an expression for the runtime
T(n) if the recurrence can be solved using the master theorem as discussed in the
class. Otherwise, indicate that the master theorem does not apply and give reasons.
Assume T(1) = 1. The following recurrences are given for n > 1. Assume that all
logarithms are taken to base 2.
(i) T(n) = 2.5 T(n / log n) + n^(0.5)
(ii) T(n) = 3 T(n / 2) + n log n
(iii) T(n) = 1.5 T(sqrt(n)) + n^(4.8)
(iv) T(n) = (7/3) T((4n+1) / 3.89) + n^(1/3)
(v) T(n) = (5/4) T(n / 8) + n / log log n
() T(n) = (2 / 3) T (n / 4.1) + n^(0.00001)
(i) T(n) = 4 T(n / 3) + 2^n
(ii) T(n) = 6 T(2n) + n^(0.3)
(ix) T(n) = (9/8) T(n / 0.39) + n^2
(x) T(n) = 3.14 T(n / 4.5) – n
3. [5 points] Give a dide-and-conquer algorithm pseudocode to count the number of
positive integers in an integer array.
4. [5 points] Diagrammatically show how merge sort sorts the array [40 30 10 20 30 40
60 20 50]. Use the example diagram similar to the one in the lecture slides.
5. [5 points] Diagrammatically show how quicksort sorts the array [40 30 10 20 30 40
60 20 50]. Use the example diagram similar to the one in the lecture slides.
6. [5 points] Let’s extend the 2-way merge sort to a 3-way merge sort algorithm.
Suppose you dide the array into three subarrays, sort them recursively, and merge
the three sorted subarrays, what will be the complexity of this new algorithm?
Explain how you can merge three sorted subarrays. Pseudocode is not required.
7. [5 points] Show how to multiply 110100 and 101 using Karatsuba’s
dide-and-conquer integer multiplication algorithm. (Hint: Assume that the
numbers are 8-bit binary numbers and then apply the algorithm.)
8. [5 points] Show how to compute the following matrix product using the 8-way
dide-and-conquer matrix multiplication algorithm.