2.1 Order the following functions by growth rate: N, ,N, N1.5, N2, N logN,
N log logN, N log2 N, N log(N2), 2/N, 2N, 2N/2, 37, N2 logN, N3. Indicate which
functions grow at the same rate. Get solution
2.2 Suppose T1(N) = O(f (N)) and T2(N) = O(f (N)). Which of the following are true?
a. T1(N) + T2(N) = O(f (N))
b. T1(N) − T2(N) = o(f (N))
c.
T1(N)
T2(N) = O(1)
d. T1(N) = O(T2(N)) Get solution
2.3 Which function grows faster: N logN or N1+(/,logN, ( > 0? Get solution
2.4 Prove that for any constant, k, logk N = o(N). Get solution
2.5 Find two functions f (N) and g(N) such that neither f (N) = O(g(N)) nor g(N) = O(f (N)). Get solution
2.6 In a recent court case, a judge cited a city for contempt and ordered a fine of $2 for the first day. Each subsequent day, until the city followed the judge’s order, the fine was squared (that is, the fine progressed as follows: $2, $4, $16, $256, $65, 536, . . .).
a. What would be the fine on day N?
b. How many days would it take the fine to reach D dollars? (A Big-Oh answer will do.) Get solution
2.7 For each of the following six program fragments:
a. Give an analysis of the running time (Big-Oh will do).
b. Implement the code in Java, and give the running time for several values of N.
c. Compare your analysis with the actual running times.
(1) sum = 0;
for( i = 0; i < n; i++ )
sum++;
(2) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
sum++;
(3) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n * n; j++ )
sum++;
(4) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i; j++ )
sum++;
Exercises 51
(5) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i * i; j++ )
for( k = 0; k < j; k++ )
sum++;
(6) sum = 0;
for( i = 1; i < n; i++ )
for( j = 1; j < i * i; j++ )
if( j % i == 0 )
for( k = 0; k < j; k++ )
sum++; Get solution
2.8 Suppose you need to generate a random permutation of the first N integers.
For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but{5, 4, 1, 2, 1} is not, because one number (1) is duplicated and another (3) is missing. This routine is often used in simulation of algorithms.We assume the existence of a random number generator, r, with method randInt(i, j), that generates integers between i and j with equal probability. Here are three algorithms:
1. Fill the array a from a[0] to a[n-1] as follows: To fill a[i], generate random numbers until you get one that is not already in a[0], a[1], . . . , a[i-1].
2. Same as algorithm (1), but keep an extra array called the used array. When a random number, ran, is first put in the array a, set used[ran] = true. This means that when filling a[i] with a random number, you can test in one step to see whether the random number has been used, instead of the (possibly) i steps in the first algorithm.
3. Fill the array such that a[i] = i + 1. Then
for( i = 1; i < n; i++ )
swapReferences( a[ i ], a[ randInt( 0, i ) ] );
a. Prove that all three algorithms generate only legal permutations and that all permutations are equally likely.
b. Give as accurate (Big-Oh) an analysis as you can of the expected running time of each algorithm.
c. Write (separate) programs to execute each algorithm 10 times, to get a good average. Run program (1) for N = 250, 500, 1,000, 2,000; program (2) for N = 25,000, 50,000, 100,000, 200,000, 400,000, 800,000; and program (3) for N = 100,000, 200,000, 400,000, 800,000, 1,600,000, 3,200,000, 6,400,000.
d. Compare your analysis with the actual running times.
e. What is the worst-case running time of each algorithm? Get solution
2.9 Complete the table in Figure 2.2 with estimates for the running times that were too long to simulate. Interpolate the running times for these algorithms and estimate the time required to compute the maximum subsequence sum of 1 million numbers. What assumptions have you made? Get solution
2.10 Determine, for the typical algorithms that you use to perform calculations by hand,
the running time to do the following:
a. Add two N-digit integers.
b. Multiply two N-digit integers.
c. Divide two N-digit integers. Get solution
2.11 An algorithm takes 0.5 ms for input size 100. How long will it take for input size
500 if the running time is the following (assume low-order terms are negligible):
a. linear
b. O(N logN)
c. quadratic
d. cubic Get solution
2.12 An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in
1 min if the running time is the following (assume low-order terms are negligible):
a. linear
b. O(N logN)
c. quadratic
d. cubic Get solution
2.15 Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integers A1 < A2 < A3 < · · · < AN. What is the running time of your algorithm? Get solution
value of B?
d. In terms of B, what is the worst-case running time of your program?
e. Compare the running times to determine if a 20-bit number and a 40-bit number
are prime.
f. Is it more reasonable to give the running time in terms of N or B? Why? Get solution
2.26 A majority element in an array, A, of size N is an element that appears more than N/2 times (thus, there is at most one). For example, the array 3, 3, 4, 2, 4, 4, 2, 4, 4 has a majority element (4), whereas the array
3, 3, 4, 2, 4, 4, 2, 4 does not. If there is no majority element, your program should indicate this. Here
is a sketch of an algorithm to solve the problem:
First, a candidate majority element is found (this is the harder part). This candidate is the
only element that could possibly be the majority element. The second step determines if
this candidate is actually the majority. This is just a sequential search through the array. To
find a candidate in the array, A, form a second array, B. Then compare A1 and A2. If they
are equal, add one of these to B; otherwise do nothing. Then compare A3 and A4. Again if
they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until
the entire array is read. Then recursively find a candidate for B; this is the candidate for
A (why?).
a. How does the recursion terminate?
#b. How is the case where N is odd handled?
#c. What is the running time of the algorithm?
d. How can we avoid using an extra array B?
#e. Write a program to compute the majority element. Get solution
2.27 The input is an N by N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix. Get solution
2.28 Design efficient algorithms that take an array of positive numbers a, and determine:
a. the maximum value of a[j]+a[i], with j ) i.
b. the maximum value of a[j]-a[i], with j ) i.
c. the maximum value of a[j]*a[i], with j ) i.
d. the maximum value of a[j]/a[i], with j ) i. Get solution
#2.29 Why is it important to assume that integers in our computer model have a fixed size? Get solution
2.31 Suppose that line 15 in the binary search routine had the statement low = mid instead of low = mid + 1. Would the routine still work? Get solution
