UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 1

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: 2016-09-22, 16:30AM 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 n is the number of bits in the input.

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). Give a recursive function to compute I(A) by considering the two halves of A.

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.