Preface

xv

intelligence (planning, game playing, Hopﬁeld networks), computer vision

(image segmentation), data mining (change-point detection, clustering), op-

erations research (airline scheduling), and computational biology (sequence

alignment, RNA secondary structure).

The notion of computational intractability, and NP-completeness in par-

ticular, plays a large role in the book. This is consistent with how we think

about the overall process of algorithm design. Some of the time, an interest-

ing problem arising in an application area will be amenable to an efﬁcient

solution, and some of the time it will be provably NP-complete; in order to

fully address a new algorithmic problem, one should be able to explore both

of these options with equal familiarity. Since so many natural problems in

computer science are NP-complete, the development of methods to deal with

intractable problems has become a crucial issue in the study of algorithms,

and our book heavily reﬂects this theme. The discovery that a problem is NP-

complete should not be taken as the end of the story, but as an invitation to

begin looking for approximation algorithms, heuristic local search techniques,

or tractable special cases. We include extensive coverage of each of these three

approaches.

Problems and Solved Exercises

An important feature of the book is the collection of problems. Across all

chapters, the book includes over 200 problems, almost all of them developed

and class-tested in homework or exams as part of our teaching of the course

at Cornell. We view the problems as a crucial component of the book, and

they are structured in keeping with our overall approach to the material. Most

of them consist of extended verbal descriptions of a problem arising in an

application area in computer science or elsewhere out in the world, and part of

the problem is to practice what we discuss in the text: setting up the necessary

notation and formalization, designing an algorithm, and then analyzing it and

proving it correct. (We view a complete answer to one of these problems as

consisting of all these components: a fully explained algorithm, an analysis of

the running time, and a proof of correctness.) The ideas for these problems

come in large part from discussions we have had over the years with people

working in different areas, and in some cases they serve the dual purpose of

recording an interesting (though manageable) application of algorithms that

we haven’t seen written down anywhere else.

To help with the process of working on these problems, we include in

each chapter a section entitled “Solved Exercises,” where we take one or more

problems and describe how to go about formulating a solution. The discussion

devoted to each solved exercise is therefore signiﬁcantly longer than what

would be needed simply to write a complete, correct solution (in other words,