### CS2223 Algorithms Homework 5 - D Term 2008

#### PROF. CAROLINA RUIZ

Due Date: April 18, 2008 at 1:00 PM
See course policy regarding late homework submissions

• Homework Instructions:
• Read Chapter 5 of the textbook in detail.
• See Useful logarithm and exponential facts.
• This is an individual homework. No collaboration is allowed.
• Submit a hardcopy of your written homework solutions at the beginning of class the day the homework is due.
• Remember to show your work and explain your answers. Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.
• See the course webpage for the late homework submission policy.

• Homework Problems:

1. (50 Points) Problem 1. Quicksort. Quicksort uses a divide-and-conquer approach to sort a list of elements. It works as follows:

#### Input:

An array A of n elements: A[1...n]

#### Output:

The array A in which the ORIGINAL elements have been sorted. That is, A[i] ≤ A[j], for all i,j, 1 ≤ i,j ≤ n.

#### Algorithmic Strategy:

• Divide: Select an element in the array A[p...r] (initially p=1, r=n), say for instance x=A[r], which we will call the pivot, and rearrange the elements in the array A such that for some index q, p ≤ q ≤ r, x is located in A[q], all the elements in A that are less than or equal to x are located to the left of x (i.e., in A[p...q-1])., and all the elements in A greater to x are located to the right of x (i.e., in A[q+1...r]).

• Conquer: Recursively call quicksort to sort the subarrays A[p...q-1] and A[q+1...r].

• Combine: No need to do anything additional, since after A[p...q-1] and A[q+1...r] are sorted then A[p...q-1 q q+1...r] will be sorted.

#### Algorithm:

The initial call to quicksort will be: quicksort(A,1,n).
```quicksort(A,p,r) {

If p < r then {
q := partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
}
}

partition(A,p,r) {
x := A[r]
i := p-1
For j := p to r-1 do {
If A[j] ≤ x then {
i := i+1
exchange A[i] with A[j]
}
}
exchange A[i+1] with A[r]
return i+1
}
```
During the iteration of the For loop in partition, the property that is maintained (the invariance) is represented by the following picture:
```       p         i           j             r
-------------------------------------
| | | | | | | | | | | | | | | | | | |x|
-------------------------------------
|...........|.........|.............|
≤ x        > x    not processed
yet
```

• (10 Points). Follow the full quicksort algorithm (including the partition function) by hand showing step by step the values of the array A and all the variables used in quicksort and partition during the sorting of the array below. Be as neat as possible.
```       ---------------
A |7|6|5|4|8|2|3|6|
---------------
```

• (10 Points). Prove that quicksort is correct, that is, prove that it always returns the original elements of the input array A correctly sorted.

• (10 Points). Show in detail that the runtime of the partition algorithm is Θ(n).

• (10 Points). Consider the worst-case partitioning for quicksort. In this case, the array is partitioned into two subarrays, one with n-1 elements and the other one with 0 elements. Assume that this worst-case behavior happens on each one of the recursive calls. Since you showed above that the partition algorithm is Θ(n), then quicksort's runtime for this worst-case is T(n) = T(n-1) + T(0) + Θ(n) = T(n-1) + Θ(1) + Θ(n) = T(n-1) + Θ(n) Use either the recursion-tree method (= "unrolling" the recurrence) or the substitution method (= "guess + induction") to show that T(n) = O(n2).

• (10 Points). Consider the best-case partitioning for quicksort. In this case, the array is partitioned into two subarrays, of equal size (or nearly equal size if n is odd). Provide a recurrence for T(n) in this best-case and determine the tightest upper bound you can for T(n) (here you can reuse results proven in class or in the textbook (without proving them again) to determine this tightest upper bound, if appropriate).

2. (30 Points) Problem 2. Recurrences. Let T(n) = 4T(n/3)+n. You can assume that n is a power of 3.

• (15 Points). Use the recursion-tree method (= "unrolling" the recurrence) to prove in detail that T(n) = O(nlog34).

• (15 Points). Use the substitution method (= "guess + induction") to prove in detail that T(n) = O(nlog34).

3. (20 Points) Problem 3. Matrix Multiplication. See the textbook slides for a description of a divide-and-conquer approach to multiplying two matrices A and B. Consider here the problem of squaring a matrix. Let the square of a matrix A be the product of the matrix A by itself, AxA. Using a divide-and-conquer approach, show that five multiplications are enough to find the square of a 2x2 matrix (note that the 4 elements in a 2x2 matrix are numbers).

[However, for your information, squaring matrices is not more efficient in general than multiplying two matrices A and B. If nxn matrices can be squared in time O(nc), then any two nxn matrices can be multiplied in time O(nc) as well.]