2023年11月25日

数据结构与算法代写 | CSE 582 Data Structures and Algorithms Homework 4

本次美国代写主要为数据结构和算法相关的计算机基础作业

CSE 582 Data Structures and Algorithms Homework 4

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 dide-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 dide 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
dide-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
dide-and-conquer matrix multiplication algorithm.