Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
SOLUTIONS MANUAL
All Chapters Included
, Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.1
1) Write an algorithm that finds the largest number in a list (an array) of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: the maximum element in the list S
number findMax(int n, const keytype S[ ])
{ index i;
number max = S[1];
for(i =2; i<=n; i++)
if(S[i] > max)
max = S[i];
return max;
}
2) Write an algorithm that finds the m smallest numbers in a list of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n, empty list of numbers
Small indexed from 1 to m.
Output: the list Small with the smallest m numbers in it.
void find_m_Smallest(int n, const keytype S[ ], keytype Small[])
{ index i, j, k;
Small[1] = S[1];
for(i =2; i<=n; i++) {
if (j <=m)
find index j where S[i] needs to be inserted in Small, such that\
Small stays sorted in non-decreasing order;
for (k = m-1; k>=j, k--)
Small[k+1) = Small[k]; //shift right
Small[j] = Small[i]; //insert S[i]
}
}
SOLUTIONS MANUAL
All Chapters Included
, Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.1
1) Write an algorithm that finds the largest number in a list (an array) of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: the maximum element in the list S
number findMax(int n, const keytype S[ ])
{ index i;
number max = S[1];
for(i =2; i<=n; i++)
if(S[i] > max)
max = S[i];
return max;
}
2) Write an algorithm that finds the m smallest numbers in a list of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n, empty list of numbers
Small indexed from 1 to m.
Output: the list Small with the smallest m numbers in it.
void find_m_Smallest(int n, const keytype S[ ], keytype Small[])
{ index i, j, k;
Small[1] = S[1];
for(i =2; i<=n; i++) {
if (j <=m)
find index j where S[i] needs to be inserted in Small, such that\
Small stays sorted in non-decreasing order;
for (k = m-1; k>=j, k--)
Small[k+1) = Small[k]; //shift right
Small[j] = Small[i]; //insert S[i]
}
}
