Hw2 practice solutions PDF

Preview

Summary

Download Hw2 practice solutions PDF

Description

Solutions to Homework 2 Practice Problems [DPV] Problem 2.5 – Recurrence Solution: (a) T (n) = 2T (n/3) + 1 = O(nlog3 2 ) by the Master theorem. (b) T (n) = 5T (n/4) + n = O(nlog4 5 ) by the Master theorem. (c) T (n) = 7T (n/7) + n = O(n log7 n) by the Master theorem. (d) T (n) = 9T (n/3) + n2 = O(n2 log3 n) by the Master theorem. (e) T (n) = 8T (n/2) + n3 = O(n3 log2 n) by the Master theorem. 49 i ) O(n3/2 log n). (f) T (n) = O(n3/2 log n). Hint: the contribution of level i of the recursion is (125

(g) T (n) = T (n − 1) + 2 = O(n). (h) T (n) = T (n − 1) + nc = (i) T (n) = T (n − 1) + cn = (j) T (n) = 2T (n − 1) + 1 =

Pn

i=1

Pn

i=1

ci + T (0) = O(cn ).

Pn−1 i=0

ic + T (0) = O(nc+1 ).

2i + 2n T (0) = O(2n ).

Pk 1 √ (k) T (n) = T ( n) + 1 = i=0 1 + T (b), where k is an integer such that n2k is a small constant b (the size of the base case). This implies that k = O(log log n) and T (n) = O(log log n).

1

[DPV] Problem 2.7 – Roots of unity Solution: For the sum, use the geometric series equality to get 1 + ω + ω 2 + · · · + ω n−1 = For the product, since 1 + 2 + · · · + (n − 1) =

ωn − 1 = 0. ω−1

(n−1)n 2

1ωω 2 . . . ωn−1 = ω

we get

(n−1)n 2

n

which equals 1 if n is odd and ω 2 = −1 for n even (remember that ω = e

2πi n

).

[DPV] Problem 2.14 – Duplicates Solution: This is a straight forward application of the MergeSort algorithm. STEP1: Sort the given list. The running time of this step is O(n log (n)). STEP2: For i = 1 to n − 1: if ai = ai+1 , delete ai from the list. Output the final list. This list has no repeated terms. The running time of this step is O(n). Why the algorithm is correct: the list after step 1 is sorted, so if there are repeated terms of aj for some j, they are all consecutive. STEP2 guarantees a comparison of all elements with both of its neighbors and elimination of one of the copies every time we found one. Hence no copies survived after STEP2 is completed. The running time is O(n log (n) + n) = O(n log (n)). (Alternatively, you can modify the Merge subroutine to eliminate copies at the same time that the merging is done.)

2...