252 OTHER ALGORITHMIC TECHNIQUES
returned. How many times do you have to call this function before you get
the correct answer? (Start at the beginning of the list of random numbers for
each case.)- Show the first three boards that the Queens algorithm would generate in its
attempt at solving the eight queens problem. - Modify PivotList so that it is a Sherwood-based algorithm.
- Write the Sherwood search, based on binary search, that is described in
Section 9.2.4.
9.3 Dynamic Programming
Richard Bellman first used the term dynamic programming to describe a type of
problem in which the most efficient solution depended on choices that may
change with time instead of being predetermined. The key value of his ideas
was the use of a polynomial time computation in place of an exponential time
one. There are two applications of dynamic programming algorithms that we
will now consider: a method to improve the calculation efficiency of some
recursive algorithms and a method to decide the order in which to multiply a
series of matrices to reduce the calculation time. Another dynamic program-
ming application was discussed in Chapter 5, namely, the approximate string
matching algorithm.■ 9.3.1 Array-Based Methods
Array-based methods replace traditional recursive algorithms that may calculate
results multiple times. The classic example of a recursive function is the calcula-
tion of numbers in the Fibonacci sequence described in question 1 in Section
1.5.3. If you trace this calculation for the tenth Fibonacci number, you will see
that you need to calculate the ninth and eighth Fibonacci numbers and add
them together. The traditional method will wind up calculating the eighth
Fibonacci number as part of determining the ninth, but it then throws this
information away and calculates it again. The algorithm from Chapter 1 is
reproduced here:
Fibonacci( N )
N the Nth Fibonacci number should be returned