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

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.