CHAPTER 2
Algorithm Analysis
2.2 (a) True.
2.3 We claim that N log N is the slower growing function. To see this, suppose otherwise. Then,
log N
N
2.4 Clearly,
12
log (log )
kk
N o N=
if k1 < k2, so we need to worry only about positive integers. The claim is
2.5 Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is
2.7 For all these programs, the following analysis will agree with a simulation:
(VI) The if statement is executed at most N3 times, by previous arguments, but it is true only O(N2) times
2.8 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have tests
to guarantee no duplicates; the third algorithm works by shuffling an array that initially has no duplicates, so
none can occur. It is also clear that the first two algorithms are completely random, and that each permutation
(b) For the first algorithm, the time to decide if a random number to be placed in a[i] has not been used
earlier is O(i). The expected number of random numbers that need to be tried is N/(N – i). This is obtained as
2.9 Algorithm 1 at 10,000 is about 38 minutes and at 100,000 is about 26 days. Algorithms 1–4 at 1 million are
2.11 (a) Five times as long, or 2.5 ms.
2.12 (a) 12000 times as large a problem, or input size 1,200,000.
2.14
a) Below are the values of poly at each iteration
poly = 0
2.15
bool indexIsValue( int A[], int low, int high)
2.16
2.17
a)
/**
b)
{
vector<int> partialSum;
int minPosSum = –1;
int sum;
c)
/**
* linear time maximum contiguous subsequence product algorithm.
*/
double maxSubProd( const vector<double> & a )
{
double maxVal = 1, maxPos = 1, maxNeg = 0;
for (auto i = 0; i < a.size(); i++)
2.18
/*
bisection method
assumes (f(low)*f(high) < 0 and only 1 zero between low and high)
termination ensured by choosing a tolerance (tol).
*/
#include<iostream>
using namespace std;
2.19
struct MaxSeq
{
int value;
int startIndex;
int endIndex;
MaxSeq operator + (const MaxSeq & rhs) const
{
MaxSeq sum;
MaxSeq max(const MaxSeq & a, const MaxSeq & b)
*/
MaxSeq maxSubSum1( const vector<int> & a )
{
}
return maxSum;
}
/**
* Quadratic maximum contiguous subsequence sum algorithm.
}
/**
}
}
int center = ( left + right ) / 2;
MaxSeq maxLeftSum = maxSumRec( a, left, center );
MaxSeq maxRightSum = maxSumRec( a, center + 1, right );
MaxSeq maxLeftBorderSum, leftBorderSum;
maxLeftBorderSum.value = leftBorderSum.value = 0;
leftBorderSum.startIndex = left;
leftBorderSum.endIndex = center;
for( int i = center; i >= left; —i )
{
}
return max( max(maxLeftSum, maxRightSum),
maxLeftBorderSum + maxRightBorderSum );
}
/**
maxSum.value = thisSum.value = 0;
maxSum.startIndex = maxSum.endIndex = 0;
thisSum.startIndex = 0;
for( int j = 0; j < a.size( ); ++j )
{
2.20 (a) Test to see if N is an odd number (or 2) and is not divisible by
3, 5, 7, , .N
2.21 The running time is proportional to N times the sum of the reciprocals of the primes less than N. This is O(N
2.23 Maintain an array that can be filled in a for loop. The array will contain X, X2, X4, up to
log
2.
N
X
The binary
2.24 For N = 0 or N = 1, the number of multiplies is zero. If b(N) is the number of ones in the binary
2.25 (a) A.
2.26 (a) Recursion is unnecessary if there are two or fewer elements.
(d) One copy of the original needs to be saved. After this, the B array, and indeed the recursion, can be
(b, d) Similar solutions; (b) is described here. The maximum difference is at least zero (i j), so that can be
2.29 Otherwise, we could perform operations in parallel by cleverly encoding several integers into one. For
2.30
a) There are RC squares to start a search. For each starting square there are 8 directions in which to
2.32
/**
* Performs the standard binary search using two comparisons per level.
* Returns index where item is found or -1 if not found.
if( a[ mid ] <= x )
low = mid + 1;
else