CS 331-01 Design and Analysis of Algorithms
Homework #2
1. Solve the following recurrence relations and get the equivalent non-recursive definition for T(n) in terms of n. Show steps. No credit will be given if you apply directly the theorem given in class.
(a) T(n) = T(n/3) + n for n > 1
T(1) = 1
(b) T(n) = 4T(n/2) + n2 for n > 1
T(1) = 1
2. There are different ways to perform partition in quicksort,
(a) Trace the Partition algorithm given in class on A = {5,6,1,3,7,2,8,4,9}. Show steps.
(b) Given an alternative algorithm for partition, we call it Partition1, as follows. Trace Partition1 on A = {5,6,1,3,7,2,8,4,9}. Show steps.
procedure Partition1 (first, last) {
pivot = A[first];
vacant = first;
for (unknown = first+1; unknown £ last; unknown++)
if (A[unknown] < pivot) {
A[vacant] = A[unknown];
A[unknown] = A[vacant+1];
vacant++;
}
A[vacant] = pivot;
return vacant; //pivot position
}
(c) How many key comparisons does Partition1 do on a subrange of A with k elements?
(d) Given another alternative algorithm for partition, we call it Partition2, as follows. Trace Partition2 on the same array A = {5,6,1,3,7,2,8,4,9}. Show steps.
procedure Partition2 (low, high)
{
v ¬ A[low];
j ¬ low;
for i ¬ (low + 1) to high {
if A(i) < v {
j++;
A[i] « A[j];
}
}
pivotposition ¬ j;
A[low] « A[pivotposition];
}
3. Given two vectors X = (x1,...,xn), Y = (y1,...,yn), then X < Y if there exists an i,
1 £ i £ n such that xj = yj for 1 £ j < i and xi < yi.
(a) Given m vectors each of size n, use divide-and-conquer strategy to write a recursive algorithm RMIN which determines the minimum vector.
(b) Let T(m) denote the number of key comparisons RMIN needs to find the minimum vector among m vectors. Define and solve the recurrence relation of T(m) in terms of m and n.
4. Let x1 < x2 < … < xn be an array of integers in increasing order.
(a) Give a straightforward algorithm to determine if any xi = i, finding such an i if one exists. What is the time complexity of your algorithm in the worst case (use q)?
(b) Write a non-recursive algorithm using divide-and-conquer strategy to solve the problem with q (logn) worst-case complexity.