0. Consider the following divide-and-conquer algorithm: (15pt)
float myFunc(X){ n = X.length; if (n==1){
return X[0];
}
// let X1,X2 be arrays of size n/2
for (i=0; i <= (n/2)-1; i++){
X1[i] = A[i];
X2[i] = A[n/2 + i];
}
for (i=0; i<=(n/2)-1; i++){
for (j=0; j<=(n/2)-1; j++){
if (X1[i] == X2[j])
X2[j] = 0;
}
}
r1 = myFunc(X1);
r2 = myFunc(X2);
return max(r1,r2);
}
(a) Obtain a recurrence relation for the algorithm’s basic operation count. (5pt)
(b) Solve the recurrence relation found in part (a) to nd a tight bound. (10pt)
Note that you don’t need to consider what does the algorithm compute; just focus on the basic operations.
1
Homework 1
CS301
2. Consider the following statements as True or False. If True, explain; if False, give a counterex-ample. (20pt)
(a) f(n) = (f(n=2))
(b) f(n) + o(f(n)) = (f(n))
(c) f(n) = O((f(n))2)
(d) f(n) + g(n) = (min(f(n); g(n)))
(e) f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) >= 1 and f(n) >= 1 for all su ciently large n.
3. Find an asymptotically tight bound for the following recurrence relation using substitution method. (25pt)
T (n) = T (n 5) + 2n2
4. Find the tight bound for the following recurrence by changing the variables: (20pt)
p
T (n) = 2T ( n) + log n
5. Find the time complexity for the following recurrence using the master theorem. (20pt)
(a) T (n) = 4T (n=2) + n2
(b) T (n) = 16T (n=4) + n
(c) T (n) = 0:75T (n=4) + 1=3n
(d) T (n) = 3T (n=4) + n log n
2
