[DPV] Problem 2.7 – Roots of unity Solution:
Solutions to Homework Practice Problems
For the sum, use the geometric series equality to get
1 + ω + ω2 + · · · + ωn−1 = ωn − 1 = 0.
Copyright By PowCoder代写 加微信 powcoder
ω−1 Fortheproduct,since1+2+···+(n−1)=(n−1)n weget
1ωω2 …ωn−1 = ω(n−1)n
whichequals1ifnisoddandω2 =−1forneven(rememberthatω=en ).
[DPV] Problem 2.8 Solution:
(a). Given four coefficients, the appropriate value of ω where n = 4 is e(2πi)/4 = i. We have FFT(1, 0, 0, 0) = (1, 1, 1, 1) Here’s the calculation:
Ae =(1,0)=1+0x,Ao =(0,0)=0+0x
A(ω40)=A(1) =Ae(12)+1(Ao(12)) =1+0(12)+1(0+0(12)) =1+1(0)=1 A(ω41)=A(i) =Ae(i2)+i(Ao(i2)) =1+0(i2)+i(0+0(i2)) =1+i(0) =1 A(ω42) = A(−1) = Ae((−1)2) − 1(Ao((−1)2)) = 1 + 0((−1)2) − 1(0 + 0((−1)2)) = 1 − 1(0) = 1 A(ω43) = A(−i) = Ae((−i)2) − i(Ao((−i)2)) = 1 + 0((−i)2) − i(0 + 0((−i)2)) = 1 − i(0) = 1
The inverse FFT of (1, 0, 0, 0) = (1/4, 1/4, 1/4, 1/4).
(b). FFT(1, 0, 1, −1) = (1, i, 3, −i). Here’s the matrix form of the calculation:
A ( ω 40 ) 1 1 1 1 1 1 A(ω1) 1 i −1 −i0 i
A(ω43) 1 −i −1 i −1 −i
[DPV] Problem 2.9(a) Solution:
We use 4 as the power of 2 and set ω = i.
The FFT of x + 1 is FFT(1, 1, 0, 0) = (2, 1 + i, 0, 1 − i).
The FFT of x2 + 1 is FFT(1, 0, 1, 0) = (2, 0, 2, 0).
The inverse FFT of their product (4, 0, 0, 0) corresponds to the polynomial 1 + x + x2 + x3.
4= = A(ω42) 1 −1 1 −11 3
Types of binary search Solution:
(a). Let’s begin the binary search by dividing the array into two subarrays defined as follows B1 = {10, 23, 36, 47, 59, 64, 71, 82} and B2 = {95, 100, 116, 127, 138, 141, 152, 163}. Since the number of entries is even we take the last element of B1 as our middle element. Since, 36 < 82 we take B1 and discard B2.
Next step, we divide B1 into two arrays. C1 = {10,23,36,47} and C2 = {59,64,71,82}. Now since 36 < 47, we keep C1 and discard C2.
We follow the same process for C1 by dividing it into D1 = {10,23} and D2 = {36,47}. Since 36 > 23, we keep D2 and discard D1.
Finally, we divide D2 into E1 = {36} and E2 = {47}. Since 36 is equal to the E1[1] we have found 36 and the process is over.
(b) If we have an array of length n we expect the numbers {1,2,3,…,n} to be in the array. Since, one number is missing this means there is at least one number such that its position does not match its value. If mid is the position of the middle element, we first check to see if A[mid] = mid. Since the array is sorted, if A[mid] = mid it means there are not numbers missing from 1, 2, . . . , mid, so we have to check the right half of the array. If there was a missing number, it would have been replaced by a bigger number. This means, if A[mid] > mid, we have to search the left half. As you reduce the input, track what the starting value should be (initially it’s 1), call that S. If A[1] ̸= S then the missing value is S. If they match, then you divide the current input in half based on the value of A[mid], update S accordingly, and recurse. If you get to a single element and A[i] = S then the missing value is A[i] + 1. To check the running time is logarithmic, note that the recurrence relation is T (n) = T ( n2 ) + O(1) which solves to O(log(n)) by the Master Theorem.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com