Solved: Give an efficient algorithm to determine if there exists an integer i such that

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

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))

Which function grows faster: N logN or N1+ /logN, > 0?

Prove that for any constant, k, logk N = o(N).

Find two functions f(N) and g(N) such that neither f(N) = O(g(N)) nor g(N) = O(f(N))

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 judges 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.)

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++; (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++;

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?

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?

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

1 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

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

How much time is required to compute f(x) = N i=0 aixi : a. Using a simple routine to perform exponentiation? b. Using the routine in Section 2.4.4?

Consider the following algorithm (known as Horners rule) to evaluate f(x) = N i=0 aixi : poly = 0; for( i = n; i >= 0; i-- ) poly = x * poly + a[i]; a. Show how the steps are performed by this algorithm for x = 3, f(x) = 4x4 + 8x3 + x + 2. b. Explain why this algorithm works. c. What is the running time of this algorithm?

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?

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?

Give efficient algorithms (along with running time analyses) to: a. Find the minimum subsequence sum. b. Find the minimum positive subsequence sum. c. Find the maximum subsequence product.

An important problem in numerical analysis is to find a solution to the equation f(X) = 0 for some arbitrary f. If the function is continuous and has two points low and high such that f(low) and f(high) have opposite signs, then a root must exist between low and high and can be found by a binary search. Write a function that takes as parameters f, low, and high and solves for a zero. (To implement a generic function as a parameter, pass a function object that implements the Function interface, which you can define to contain a single method f.) What must you do to ensure termination?

The maximum contiguous subsequence sum algorithms in the text do not give any indication of the actual sequence. Modify them so that they return in a single object the value of the maximum subsequence and the indices of the actual sequence.

a. Write a program to determine if a positive integer, N, is prime. b. In terms of N, what is the worst-case running time of your program? (You should be able to do this in O( N).) c. Let B equal the number of bits in the binary representation of N. What is the 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?

The Sieve of Eratosthenes is a method used to compute all primes less than N. We begin by making a table of integers 2 to N. We find the smallest integer, i, that is not crossed out, print i, and cross out i, 2i, 3i, . . . . When i > N, the algorithm terminates. What is the running time of this algorithm?

Show that X62 can be computed with only eight multiplications.

Write the fast exponentiation routine without recursion

Give a precise count on the number of multiplications used by the fast exponentiation routine. (Hint: Consider the binary representation of N.)

Programs A and B are analyzed and found to have worst-case running times no greater than 150N log2 N and N2, respectively. Answer the following questions, if possible: a. Which program has the better guarantee on the running time, for large values of N (N > 10,000)? b. Which program has the better guarantee on the running time, for small values of N (N < 100)? c. Which program will run faster on average for N = 1,000? d. Is it possible that program B will run faster than program A on all possible inputs?

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

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.

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

Why is it important to assume that integers in our computer model have a fixed size?

Consider the word puzzle problem described in Chapter 1. Suppose we fix the size of the longest word to be 10 characters. a. In terms of R and C, which are the number of rows and columns in the puzzle, and W, which is the number of words, what are the running times of the algorithms described in Chapter 1? b. Suppose the word list is presorted. Show how to use binary search to obtain an algorithm with significantly better running time.

Suppose that line 15 in the binary search routine had the statement low = mid instead of low = mid + 1. Would the routine still work?

Implement the binary search so that only one two-way comparison is performed in each iteration. (The text implementation uses three-way comparisons. Assume that only a lessThan method is available.)

3 Suppose that lines 15 and 16 in algorithm 3 (Fig. 2.7) are replaced by 15 int maxLeftSum = maxSubSum( a, left, center - 1 ); 16 int maxRightSum = maxSubSum( a, center, right ); Would the routine still work?

The inner loop of the cubic maximum subsequence sum algorithm performs N(N+1)(N+2)/6 iterations of the innermost code. The quadratic version performs N(N + 1)/2 iterations. The linear version performs N iterations. What pattern is evident? Can you give a combinatoric explanation of this phenomenon?