数据结构与算法代写 | 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.

 


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论