212
Recursion, Recurrence Relations, and Analysis of Algorithms
exercISeS 3.3
1. Modify the algorithm of Example 27 so that in addition to dropping the student’s lowest quiz grade, the
highest quiz grade is counted twice (like the old version, your new algorithm should do no operations
besides addition and subtraction).
2. What is the total number of arithmetic operations done in the algorithm of Exercise 1?
3. The following algorithm adds all the entries in a square n × n array A. Analyze this algorithm where the
work unit is the addition operation.
sum = 0
for i = 1 to n do
for j = 1 to n do
sum = sum + A[i, j]
end for
end for
write (“Total of all array elements is”, sum)
4. The following algorithm adds all the entries in the “upper triangular” part of a square n × n array A.
Analyze this algorithm where the work unit is the addition operation.
sum = 0
for k = 1 to n do
for j = k to n do
sum = sum + A[k, j]
end for
end for
write (“Total of all upper triangular array elements is”, sum)
5. Analyze the following algorithm where the work unit is the output statement. Assume that n = 2
m
for
some positive integer m.
integer j, k
for k = 1 to n do
j = n;
while j ≥ 2 do
write j
j = j/2
end while
end for
S e c t I o n 3 . 3 Review
technIQue
• Do a worst-case analysis of an algorithm either
directly from the algorithm description or from a
recurrence relation.
maIn IDeaS
• Analysis of an algorithm estimates the number of
basic operations that the algorithm performs, which
is dependent on the size of the input.
• Analysis of recursive algorithms often leads to recurrence relations.
• Lacking an exact expression for the number of operations an algorithm performs, it may be possible
to find an upper bound.