Algorithms in a Nutshell

(^40) | Chapter 3: Patterns and Domains
patterns to programming at that year’s Conference on Object-Oriented Program-
ming Systems, Languages, and Applications (OOPSLA). The idea caught on and
people began to think about software design patterns. In 1995, the seminal Gang
of Four (GoF) book,Design Patterns: Elements of Reusable Object-Oriented Soft-
ware(Gamma et al., 1995) was published, and a frenzy of research activity and
application of patterns began.
As with any good idea, the software industry embraced patterns and their use
became ubiquitous, to the point where everything could be described by a
pattern. Using coding standards was a pattern. Sitting together with a partner to
debug a program was a pattern. Well, you get the idea. Patterns are a great way to
communicate precisely and concisely well-formed concepts. We will—at the risk
of applying patterns to yet another area of computer science—use patterns as a
way to communicate the algorithms in this book.
Before describing how we structure the pattern language for the algorithms
herein, let’s look at what a pattern is and why it’s so good. We prefer the
following definition for design patterns:
A design pattern is a proven solution to a commonly occurring problem.
This definition is short and conveys the absolute essence of design patterns. First
and foremost, a design pattern is a solution to a real problem. In fact, it’s a solu-
tion to a general set of problems. But, a pattern is not a template where you
simply fill in the blanks. It is an approach, or a plan, for solving a particular class
of problems. Armed with a set of design patterns in your toolbox, you are on your
way to becoming a master craftsman of software design.
We can think of algorithms in different ways. Many practitioners are happy to
look up an algorithm in a book or on some website, copy some code, run it,
maybe even test it, and then move on to the next task. In our opinion, this process
does not improve one’s understanding of algorithms. In fact, this approach can
lead you down the wrong path where you select a specific implementation of an
algorithm. Remember how in Chapter 1 Graham blindly selected a binary tree and
didn’t bother to balance it? That’s what can happen when you just take the first
idea that seems to solve your problem.
So, the question is, how do you locate the right algorithm for the job quickly and
understand it well enough to ensure that you’ve made a good choice? Patterns can
help. Algorithms are, in fact, proven solutions to known problems, so they fit our
definition of a pattern.
The Form of an Algorithm Pattern
Design patterns are typically presented in a stylized manner that makes it easy to
understand and communicate to others. Not all pattern writers or books on
patterns agree on the specific form, but they have many elements in common. We
have adopted a style for presenting algorithms as patterns that we believe will be
effective for the reader. Feel free to recast them to your favorite form if that helps
you get a better understanding of the material.
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