CMSC 435 Algorithms
Answers to Homework # 8
Due October 29
Solve the following recurrence relations
1 if n = 1
5T(n/4) + n2 otherwise
Answer
a = 5, b = 4, f(n) = n2
n2 ó nlog45 log45 = log105/log104 = 0.6990/0.602 = 1.16
case 3: f(n) >= c nlog45 + e chose c = 1, n0 = 4, e = 0.34
f(n) = n2 >= n3/2 for all n >= 4
must also show that there exist a constant 0 < k such that a f(n/b) < k f(n)
5(n/4)2 < k n2 choose k = 1/2 è 5/16 n2 < 1/2 n2
Then T(n) = Q(n2)
1 if n = 1
2. T(n) =
3T(n/2) + n2 otherwise
Answer
a = 3, b = 2, f(n) = n2
n2 ó nlg 3 lg(3) = log10(3)/log10(2) = 0.477/0.301 = 1.59
n2 = W(nlg 3 + e) choose e = 0.16
n2 >= n1.75 for all n >= 4
case 3: must again show that there exists a k >0 such that af(n/b) < kf(n)
3(n/2)2 < k n2 choose k = 7/8
then T(n) = Q(n2)
1 if n = 1
3. T(n) =
4T(n/2) + 3n2 otherwise
Answer
a = 4, b = 2, f(n) = 3n2
3n2 ó nlg 4 lg 4 = 2 and f(n) = Q(n2)
case 2:
then T(n) = Q(nlg 4 lg n) è T(n) = Q(n2 lg n)
1 if n = 1
4. T(n) =
2T(n/2) + n lgn otherwise
Answer
a = 2, b = 2, f(n) = n lg(n)
n lg(n) ó nlg 2 lg 2 = 1
This is none of the three cases
There are no constants c, n0, and e such that
n lg(n) < c n1-e for all n >= n0 nor
n lg(n) > c n1+e for all n >= n0
The Master Theorem does not apply to this problem
1 if n = 1
5. T(n) =
Answer
a = 4, b = 2, f(n) = n
n ó nlg 4 lg 4 = 2
case 1: choose e = 1/2 n < n3/2 for all n >= 4
then T(n) = Q(n2)
1 if n = 1
6. T(n) =
2T(n/2) + lg n otherwise
Answer
a = 2, b = 2, f(n) = lg(n)
lg(n) ó nlg 2 = n
case 1: f(n) = lg(n) = O(n)
then T(n) = Q(n)
1 if n = 1
7. T(n) =
7 T(n/4) + n lgn otherwise
Answer
a = 7, b = 4, f(n) = nlg(n)
nlg(n) ó nlog47 log47 = log107/log104 = 0.84/0.602 = 1.4
case 1: nlg(n) < c n1.4 - e choose c = 1, n0 = 216, e = 0.15
then T(n) = Q(n1.4)
8. Given the Diagram shown below illustrating an intermediate stage of the bubbleSort algorithm , and the strategy of "bubbling" the largest remaining element to the top of the front segment of the list, complete the description of the invariants before and after each iteration of the inner and outer loops and list the start and stop conditions for locating each segment boundary. Use these invariants to write the algorithm for bubbleSort.
All elements in the back segment are sorted in ascending order and all elements in the back segment are greater than or equal to any of the elements in the front segment.
The initial value of i is n - 1. The back segment is empty.
All of the elements in the array between indices 0 and j (not inclusive of j) are less than or equal to the element at
array[j].
At each stage of the inner loop, you compare the elements at array[j] and array[j+1] and swap if
array[j] > array[j+1]. In either case you will then increment j
The initial value of j is 0, the final value of j is i - 1.
Note! If no swaps occur during an iteration of the inner loop, then the array will be already sorted and we can terminate the algorithm.
public void bubbleSort(Comparable[ ] array) {
boolean flag = false; // flag is true when list is sorted, no swaps occur during iteration of inner loop
int i = array.length - 1;
while (i > 0 && !flag) {
flag = true;
for (int j = 0; j < i; j++)
if (array[j].compareTo(array[j+1]) > 0) {
swap(array[j], array[j+1]);
flag = false;
}
if (flag) return;
i--;
}
}