See also the general rules about assignments in this course.
[JE] refers to http://jeffe.cs.illinois.edu/teaching/algorithms/notes/01-recursion.pdf
DUE: 2018-01-17, 09:15AM in the assignment box.
Questions
1 Prove that the running time of the following algorithm is
Θ(n²)
[JE1.1] It's important to note that if n
is the number of bits
in the input, and in this model we pay Θ(n)
cost to add two n
bit
integers (and to divide an n
bit integer by 2).
PeasantMultiply(x,y)
while(x>0)
if x is odd:
prod ← prod + y
x ← ⌊ x/2 ⌋
y ← y + y
return prod
2 Counting inversions (related to [JE1.14])
An inversion in an array A[1 .. n] is a pair of indices (i, j) such
that i < j and A[i] > A[ j]. The number of inversions I(A)
in an
n-element array A
is between 0 (if the array is sorted) and n(n-1)/2
(if the array is sorted backward). Let J(A,p,q)
count the number of
inversions (i,j)
with p ≤ i < j ≤ q
(it follows that J(A,0,n-1)=I(A)
).
Consider the following recursive definition for J(A,p,q)
J(A,p,q) = J(A,p,⌊(p+q)/2⌋) + J(A,⌊(p+q)/2⌋+1,q) + S(A,p,⌊(p+q)/2⌋,q)
where S(a,b,c)
counts the number of inversions (i,j)
with a ≤ i ≤ b < j ≤ c
.
Give a divide and conquer algorithm based on this definition, and
analyse your algorithm. For full credit, the running time should be
O(n · (log₂ n)²)
; for extra challenge, try to find a O(n log₂ n)
algorithm.
3 Use the recursion tree method to solve the recursion relation T(n) = 49 T(n/25) + O(nᵏ log n) where k=3/2.