The second written assignment for this course consists of some exercises on the analysis of algorithms. You can discuss this assignment with other people in the course, but you should write up your own solutions to turn in.
This assignment is due in class on Monday, September 24.
Suppose that K and M are two-dimensional arrays of double, and that each array has n rows and n columns (where n is a positive integer). The following algorithm computes the product, P, of K and M:
P = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double sum = 0;
for (int k = 0; k < n; k++)
sum = sum + (M[i][k] * M[k][j]);
P[i][j] = sum;
}
}
Give a run-time analysis of this algorithm. Explain your reasoning.
(For example: Find a function f(n) such that the run time is Θ(f(n)). If that is not possible, at least find a function that gives only an upper bound, that is, such that the run time is O(f(n)). Does your analysis apply to the average case run time or to the worst case run time, or both? Can you say anything about the best case run time? Your explanations can be somewhat informal, but should be convincing.)
Consider the standard selection sort algorithm for sorting an array of n numbers into non-decreasing order:
for (int top = n-1; top > 0; top--) {
int m = 0;
for (int i = 1; i <= top; i++) {
if ( A[i] > A[m] )
m = i;
}
int temp = A[i];
A[i] = A[m];
A[m] = temp;
}
Give a run-time analysis of this algorithm. Explain your reasoning.
The obvious algorithm for finding the maximum in an array of length n clearly has run time Θ(n). Consider the following funny recursive algorithm for doing the same thing:
/**
* Returns the largest number among A[low], A[low+1], ...
* A[high]. Note that high must be >= low. To find the
* maximum of the entire array, call recursive_max(A, 0, A.length).
int recursive_max( int[] A, int low, int high ) {
if (high == low)
return A[low]; // There is only one item to consider
else {
int mid = (low + high) / 2; // Note: mid >= low and mid < high
int m1 = recursive_max(A, low, mid);
int m2 = recursive_max(A, mid+1, high);
if (m2 > m1)
return m2;
else
return m1;
}
}
Give a run-time analysis of this algorithm. How does its run time compare to the run time of the usual algorithm for finding the maximum value in A? (This is a tough question, and your answer will have to be pretty informal. Try to figure out how the algorithm works. Try working it through when the length of the array is 8.)
Let n be a positive integer, and let x be a real number. Here are two algorithms that both compute the value of x raised to the power n. Give a run-time analysis of each algorithm, and compare the efficiency of the two algorithms. Recall that in Java, when the "/" operator is applied to integers, the result is also an integer; the fractional part of the quotient is discarded.
Algorithm A: Algorithm B:
double p = 1; double p = 1;
for (int i = 0; i < n; i++) while (n > 0) {
p = p * x; if (n % 2 == 1)
System.out.println(p); p = p * x;
x = x*x;
n = n / 2;
}
System.out.println(p);