Java Reference
In-Depth Information
16
Patterns of Algorithms
This chapter presents several fundamental topics related to the theory of algorithms.
Included are dynamic programming (Section 16.1), randomized algorithms (Sec-
tion 16.2), and the concept of a transform (Section 16.3.5). Each of these can be
viewed as an example of an “algorithmic pattern” that is commonly used for a
wide variety of applications. In addition, Section 16.3 presents a number of nu-
merical algorithms. Section 16.2 on randomized algorithms includes the Skip List
(Section 16.2.2). The Skip List is a probabilistic data structure that can be used
to implement the dictionary ADT. The Skip List is no more complicated than the
BST. Yet it often outperforms the BST because the Skip List's efficiency is not tied
to the values or insertion order of the dataset being stored.
16.1
Dynamic Programming
Consider again the recursive function for computing the nth Fibonacci number.
/
**
Recursivelygenerateandreturnthen'thFibonacci
number
*
/
staticlongfibr(intn){
//fibr(91)isthelargestvaluethatfitsinalong
assert(n>0)&&(n<=91):"noutofrange";
if((n==1)||(n==2))return1; //Basecase
returnfibr(n-1)+fibr(n-2); //Recursivecall
}
The cost of this algorithm (in terms of function calls) is the size of the nth Fi-
bonacci number itself, which our analysis of Section 14.2 showed to be exponential
(approximately n
1:62
). Why is this so expensive? Primarily because two recursive
calls are made by the function, and the work that they do is largely redundant. That
is, each of the two calls is recomputing most of the series, as is each sub-call, and so
on. Thus, the smaller values of the function are being recomputed a huge number
of times. If we could eliminate this redundancy, the cost would be greatly reduced.
509
