Algorithms in a Nutshell

(^42) | Chapter 3: Patterns and Domains
Pseudocode Pattern Format
Each algorithm in this book is presented with code examples that show an imple-
mentation in a major programming language, such as C, C++, Java, Scheme, and
Ruby. For readers who are not familiar with all of these languages, we first intro-
duce each algorithm in pseudocode with a small example showing its execution.
Consider the sample fact sheet shown in Figure 3-1. Each algorithm is named, and
its performance is clearly marked for all three behavior cases (best, average, and
worst). The upper-right corner of the fact sheet lists a set of concepts used by the
algorithm. This is a place that can be used to rapidly see commonalities among
different algorithms (e.g., “these two algorithms use a priority queue”).
The “glyphs” that appear in this region of the fact sheet are depicted in Figure 3-2.
Some of these concepts relate to the data structure(s) used by the algorithm (e.g.,
“Queue”), while others refer to an overall approach to solving the problem (e.g.,
“Divide and Conquer”).
The pseudocode description is intentionally kept brief and should fill up no more
than 3/4 of a page. Keywords and function names are described in boldface text.
All variables are in lowercase characters, whereas arrays are capitalized and their
elements are referred to usingA[i] notation. The indentation in the pseudocode
describes the scope of conditionalifstatements and loopingwhileandforstate-
ments. All statements within a function are numbered for reference (if necessary)
in descriptions in the individual chapters.
Figure 3-1. Sequential Search fact sheet
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use