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.