214
Recursion, Recurrence Relations, and Analysis of Algorithms
Horner(real a n , real a n−1 , … , real a 0 , real c, integer n)
//evaluates polynomial a n x
n
+ a n−1 x
n−1
+ c + a 0 for x = c
//using Horner’s method
Local variables:
integer i
real result = a n
for i = 1 to n do
result = result * c + a n−i
end for
return result
end function Horner
a. Walk through this algorithm to compute the value of 2x
3
− 7x
2
+ 5x − 14 for x = 4.
b. Analyze this algorithm where addition and multiplication operations are the work units.
c. In evaluating a polynomial of degree n = 98 for some value of x, how many operations have been saved
by using Horner’s method over the method of Exercise 9?
11. For the algorithm of Example 27, count the total number of assignments and comparisons done in the best
case (least work) and the worst case (most work); describe each of these cases.
12. a. Write a function to convert a binary string b n b n−1 … b 1 b 0 to its decimal equivalent.
b. Test your function on the binary string 10011
c. Describe the worst case for this algorithm and find the number of multiplications and additions done in
this case.
d. Describe the best case for this algorithm and find the number of multiplications and additions done in
this case.
Exercises 13 and 14 relate to a recursive sorting algorithm called BubbleSort.
13. Algorithm BubbleSort works by making repeated passes through a list; on each pass, adjacent elements
that are out of order are exchanged. At the end of pass 1, the maximum element has “bubbled up” to the
end of the list and does not participate in subsequent passes. The following algorithm is called initially
with j = n.
BubbleSort(list L; integer j)
//recursively sorts the items from 1 to j in list L into increasing order
if j = 1 then
sort is complete, write out the sorted list
else
for i = 1 to j − 1 do
if L[i] > L[i + 1] then
exchange L[i] and L[i + 1]
end if
end for
BubbleSort(L, j − 1)
end if
end function BubbleSort
Recursion, Recurrence Relations, and Analysis of Algorithms
Horner(real a n , real a n−1 , … , real a 0 , real c, integer n)
//evaluates polynomial a n x
n
+ a n−1 x
n−1
+ c + a 0 for x = c
//using Horner’s method
Local variables:
integer i
real result = a n
for i = 1 to n do
result = result * c + a n−i
end for
return result
end function Horner
a. Walk through this algorithm to compute the value of 2x
3
− 7x
2
+ 5x − 14 for x = 4.
b. Analyze this algorithm where addition and multiplication operations are the work units.
c. In evaluating a polynomial of degree n = 98 for some value of x, how many operations have been saved
by using Horner’s method over the method of Exercise 9?
11. For the algorithm of Example 27, count the total number of assignments and comparisons done in the best
case (least work) and the worst case (most work); describe each of these cases.
12. a. Write a function to convert a binary string b n b n−1 … b 1 b 0 to its decimal equivalent.
b. Test your function on the binary string 10011
c. Describe the worst case for this algorithm and find the number of multiplications and additions done in
this case.
d. Describe the best case for this algorithm and find the number of multiplications and additions done in
this case.
Exercises 13 and 14 relate to a recursive sorting algorithm called BubbleSort.
13. Algorithm BubbleSort works by making repeated passes through a list; on each pass, adjacent elements
that are out of order are exchanged. At the end of pass 1, the maximum element has “bubbled up” to the
end of the list and does not participate in subsequent passes. The following algorithm is called initially
with j = n.
BubbleSort(list L; integer j)
//recursively sorts the items from 1 to j in list L into increasing order
if j = 1 then
sort is complete, write out the sorted list
else
for i = 1 to j − 1 do
if L[i] > L[i + 1] then
exchange L[i] and L[i + 1]
end if
end for
BubbleSort(L, j − 1)
end if
end function BubbleSort