Description
Homework see the attachment. Each file have page number.
Unformatted Attachment Preview
Homework
Suggested Homework Problems
§3.2, p. 106 – 107, n. 2 – 8
Sorting
Selection Sort
Bubble Sort
0
00000
00000
Homework
Suggested Homework Problems
§3.1, p. 102 – 103, n. l(a), 3, 4, 7 -11, 13, 14
Homework
•
000000
Homework
Suggested Homework Problems
§2.5, p. 83 – 84, n. 3 – 4, 5, 8
This page intentionally left blank
Vice President and Editorial Director, ECS
Editor-in-Chief
Acquisitions Editor
Editorial Assistant
Vice President, Marketing
Marketing Manager
Senior Marketing Coordinator
Marketing Assistant
Vice President, Production
Managing Editor
Production Project Manager
Senior Operations Supervisor
Manufacturing Buyer
Art Director
Text Designer
Cover Designer
Cover Illustration
Media Editor
Full-Service Project Management
Composition
Printer/Binder
Cover Printer
Text Font
Marcia Horton
Michael Hirsch
Matt Goldstein
Chelsea Bell
Patrice Jones
Yezan Alayan
Kathryn Ferranti
Emma Snider
Vince O’Brien
Jeff Holcomb
Kayla Smith-Tarbox
Alan Fischer
Lisa McDowell
Anthony Gemmellaro
Sandra Rigney
Anthony Gemmellaro
Jennifer Kohnke
Daniel Sandin
Windfall Software
Windfall Software, using ZzTEX
Courier Westford
Courier Westford
Times Ten
Copyright © 2012, 2007, 2003 Pearson Education, Inc., publishing as Addison-Wesley. All rights
reserved. Printed in the United States of America. This publication is protected by Copyright,
and permission should be obtained from the publisher prior to any prohibited reproduction,
storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical,
photocopying, recording, or likewise. To obtain permission(s) to use material from this work,
please submit a written request to Pearson Education, Inc., Permissions Department, One Lake
Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290.
This is the eBook of the printed book and may not include any media, Website access codes or
print supplements that may come packaged with the bound book.
Many of the designations by manufacturers and sellers to distinguish their products are claimed
as trademarks. Where those designations appear in this book, and the publisher was aware of a
trademark claim, the designations have been printed in initial caps or all caps.
Library of Congress Cataloging-in-Publication Data
Levitin, Anany.
Introduction to the design & analysis of algorithms / Anany Levitin. — 3rd ed.
p. cm.
Includes bibliographical references and index.
ISBN-13: 978-0-13-231681-1
ISBN-10: 0-13-231681-1
1. Computer algorithms. I. Title. II. Title: Introduction to the design and analysis of
algorithms.
QA76.9.A43L48 2012
005.1—dc23
2011027089
15 14 13 12 11—CRW—10 9 8 7 6 5 4 3 2 1
ISBN 10: 0-13-231681-1
ISBN 13: 978-0-13-231681-1
Boston Columbus Indianapolis New York San Francisco Upper Saddle River
Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto
Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo
This page intentionally left blank
Brief Contents
New to the Third Edition
xvii
Preface
xix
1 Introduction
1
2 Fundamentals of the Analysis of Algorithm Efficiency
41
3 Brute Force and Exhaustive Search
97
4 Decrease-and-Conquer
131
5 Divide-and-Conquer
169
6 Transform-and-Conquer
201
7 Space and Time Trade-Offs
253
8 Dynamic Programming
283
9 Greedy Technique
315
10 Iterative Improvement
345
11 Limitations of Algorithm Power
387
12 Coping with the Limitations of Algorithm Power
423
Epilogue
471
APPENDIX A
Useful Formulas for the Analysis of Algorithms
475
APPENDIX B
Short Tutorial on Recurrence Relations
479
References
493
Hints to Exercises
503
Index
547
v
This page intentionally left blank
Contents
New to the Third Edition
xvii
Preface
xix
1 Introduction
1
1.1 What Is an Algorithm?
3
Exercises 1.1
1.2 Fundamentals of Algorithmic Problem Solving
Understanding the Problem
Ascertaining the Capabilities of the Computational Device
Choosing between Exact and Approximate Problem Solving
Algorithm Design Techniques
Designing an Algorithm and Data Structures
Methods of Specifying an Algorithm
Proving an Algorithm’s Correctness
Analyzing an Algorithm
Coding an Algorithm
Exercises 1.2
1.3 Important Problem Types
Sorting
Searching
String Processing
Graph Problems
Combinatorial Problems
Geometric Problems
Numerical Problems
Exercises 1.3
7
9
9
9
11
11
12
12
13
14
15
17
18
19
20
20
21
21
22
22
23
vii
viii
Contents
1.4 Fundamental Data Structures
Linear Data Structures
Graphs
Trees
Sets and Dictionaries
Exercises 1.4
Summary
25
25
28
31
35
37
38
2 Fundamentals of the Analysis of Algorithm
Efficiency
2.1 The Analysis Framework
41
Measuring an Input’s Size
Units for Measuring Running Time
Orders of Growth
Worst-Case, Best-Case, and Average-Case Efficiencies
Recapitulation of the Analysis Framework
42
43
44
45
47
50
Exercises 2.1
50
2.2 Asymptotic Notations and Basic Efficiency Classes
Informal Introduction
O-notation
-notation
-notation
Useful Property Involving the Asymptotic Notations
Using Limits for Comparing Orders of Growth
Basic Efficiency Classes
Exercises 2.2
2.3 Mathematical Analysis of Nonrecursive Algorithms
Exercises 2.3
2.4 Mathematical Analysis of Recursive Algorithms
Exercises 2.4
2.5 Example: Computing the nth Fibonacci Number
Exercises 2.5
2.6 Empirical Analysis of Algorithms
Exercises 2.6
2.7 Algorithm Visualization
Summary
52
52
53
54
55
55
56
58
58
61
67
70
76
80
83
84
89
91
94
Contents
3 Brute Force and Exhaustive Search
3.1 Selection Sort and Bubble Sort
Selection Sort
Bubble Sort
Exercises 3.1
3.2 Sequential Search and Brute-Force String Matching
Sequential Search
Brute-Force String Matching
Exercises 3.2
3.3 Closest-Pair and Convex-Hull Problems by Brute Force
Closest-Pair Problem
Convex-Hull Problem
Exercises 3.3
3.4 Exhaustive Search
ix
97
98
98
100
102
104
104
105
106
108
108
109
113
Traveling Salesman Problem
Knapsack Problem
Assignment Problem
115
116
116
119
Exercises 3.4
120
3.5 Depth-First Search and Breadth-First Search
Depth-First Search
Breadth-First Search
Exercises 3.5
Summary
122
122
125
128
130
4 Decrease-and-Conquer
131
4.1 Insertion Sort
134
Exercises 4.1
136
4.2 Topological Sorting
Exercises 4.2
4.3 Algorithms for Generating Combinatorial Objects
Generating Permutations
Generating Subsets
Exercises 4.3
138
142
144
144
146
148
x
Contents
4.4 Decrease-by-a-Constant-Factor Algorithms
Binary Search
Fake-Coin Problem
Russian Peasant Multiplication
Josephus Problem
150
150
152
153
154
Exercises 4.4
156
4.5 Variable-Size-Decrease Algorithms
Computing a Median and the Selection Problem
Interpolation Search
Searching and Insertion in a Binary Search Tree
The Game of Nim
Exercises 4.5
Summary
157
158
161
163
164
166
167
5 Divide-and-Conquer
169
5.1 Mergesort
172
Exercises 5.1
174
5.2 Quicksort
Exercises 5.2
5.3 Binary Tree Traversals and Related Properties
Exercises 5.3
5.4 Multiplication of Large Integers and
Strassen’s Matrix Multiplication
Multiplication of Large Integers
Strassen’s Matrix Multiplication
Exercises 5.4
5.5 The Closest-Pair and Convex-Hull Problems
by Divide-and-Conquer
The Closest-Pair Problem
Convex-Hull Problem
Exercises 5.5
Summary
176
181
182
185
186
187
189
191
192
192
195
197
198
Contents
6 Transform-and-Conquer
6.1 Presorting
Exercises 6.1
6.2 Gaussian Elimination
LU Decomposition
Computing a Matrix Inverse
Computing a Determinant
Exercises 6.2
6.3 Balanced Search Trees
xi
201
202
205
208
212
214
215
216
AVL Trees
2-3 Trees
218
218
223
Exercises 6.3
225
6.4 Heaps and Heapsort
Notion of the Heap
Heapsort
Exercises 6.4
6.5 Horner’s Rule and Binary Exponentiation
Horner’s Rule
Binary Exponentiation
Exercises 6.5
6.6 Problem Reduction
Computing the Least Common Multiple
Counting Paths in a Graph
Reduction of Optimization Problems
Linear Programming
Reduction to Graph Problems
Exercises 6.6
Summary
226
227
231
233
234
234
236
239
240
241
242
243
244
246
248
250
7 Space and Time Trade-Offs
253
7.1 Sorting by Counting
254
Exercises 7.1
7.2 Input Enhancement in String Matching
Horspool’s Algorithm
257
258
259
xii
Contents
Boyer-Moore Algorithm
263
Exercises 7.2
267
7.3 Hashing
Open Hashing (Separate Chaining)
Closed Hashing (Open Addressing)
Exercises 7.3
7.4 B-Trees
Exercises 7.4
Summary
269
270
272
274
276
279
280
8 Dynamic Programming
283
8.1 Three Basic Examples
285
Exercises 8.1
8.2 The Knapsack Problem and Memory Functions
290
Memory Functions
292
294
Exercises 8.2
296
8.3 Optimal Binary Search Trees
Exercises 8.3
8.4 Warshall’s and Floyd’s Algorithms
Warshall’s Algorithm
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem
Exercises 8.4
Summary
297
303
304
304
308
311
312
9 Greedy Technique
315
9.1 Prim’s Algorithm
318
Exercises 9.1
322
9.2 Kruskal’s Algorithm
Disjoint Subsets and Union-Find Algorithms
325
327
Exercises 9.2
331
9.3 Dijkstra’s Algorithm
Exercises 9.3
333
337
Contents
9.4 Huffman Trees and Codes
Exercises 9.4
Summary
10 Iterative Improvement
10.1 The Simplex Method
Geometric Interpretation of Linear Programming
An Outline of the Simplex Method
Further Notes on the Simplex Method
Exercises 10.1
10.2 The Maximum-Flow Problem
Exercises 10.2
10.3 Maximum Matching in Bipartite Graphs
Exercises 10.3
10.4 The Stable Marriage Problem
Exercises 10.4
Summary
11 Limitations of Algorithm Power
11.1 Lower-Bound Arguments
Trivial Lower Bounds
Information-Theoretic Arguments
Adversary Arguments
Problem Reduction
Exercises 11.1
11.2 Decision Trees
Decision Trees for Sorting
Decision Trees for Searching a Sorted Array
Exercises 11.2
11.3 P , NP , and NP-Complete Problems
P and NP Problems
NP -Complete Problems
Exercises 11.3
xiii
338
342
344
345
346
347
351
357
359
361
371
372
378
380
383
384
387
388
389
390
390
391
393
394
395
397
399
401
402
406
409
xiv
Contents
11.4 Challenges of Numerical Algorithms
Exercises 11.4
Summary
12 Coping with the Limitations of Algorithm Power
12.1 Backtracking
412
419
420
423
n-Queens Problem
Hamiltonian Circuit Problem
Subset-Sum Problem
General Remarks
424
425
426
427
428
Exercises 12.1
430
12.2 Branch-and-Bound
Assignment Problem
Knapsack Problem
Traveling Salesman Problem
432
433
436
438
Exercises 12.2
440
12.3 Approximation Algorithms for NP -Hard Problems
Approximation Algorithms for the Traveling Salesman Problem
Approximation Algorithms for the Knapsack Problem
Exercises 12.3
12.4 Algorithms for Solving Nonlinear Equations
441
443
453
457
Exercises 12.4
459
460
464
464
467
Summary
468
Epilogue
471
Bisection Method
Method of False Position
Newton’s Method
APPENDIX A
Useful Formulas for the Analysis of Algorithms
Properties of Logarithms
Combinatorics
Important Summation Formulas
Sum Manipulation Rules
475
475
475
476
476
Contents
Approximation of a Sum by a Definite Integral
Floor and Ceiling Formulas
Miscellaneous
xv
477
477
477
APPENDIX B
Short Tutorial on Recurrence Relations
Sequences and Recurrence Relations
Methods for Solving Recurrence Relations
Common Recurrence Types in Algorithm Analysis
479
479
480
485
References
493
Hints to Exercises
503
Index
547
This page intentionally left blank
New to the Third Edition
Reordering of chapters to introduce decrease-and-conquer before divideand-conquer
Restructuring of chapter 8 on dynamic programming, including all new introductory material and new exercises focusing on well-known applications
More coverage of the applications of the algorithms discussed
Reordering of select sections throughout the book to achieve a better alignment of specific algorithms and general algorithm design techniques
Addition of the Lomuto partition and Gray code algorithms
Seventy new problems added to the end-of-chapter exercises, including algorithmic puzzles and questions asked during job interviews
xvii
This page intentionally left blank
Preface
The most valuable acquisitions in a scientific or technical education are the
general-purpose mental tools which remain serviceable for a life-time.
—George Forsythe, “What to do till the computer scientist comes.” (1968)
A
lgorithms play the central role both in the science and practice of computing.
Recognition of this fact has led to the appearance of a considerable number
of textbooks on the subject. By and large, they follow one of two alternatives
in presenting algorithms. One classifies algorithms according to a problem type.
Such a book would have separate chapters on algorithms for sorting, searching,
graphs, and so on. The advantage of this approach is that it allows an immediate
comparison of, say, the efficiency of different algorithms for the same problem.
The drawback of this approach is that it emphasizes problem types at the expense
of algorithm design techniques.
The second alternative organizes the presentation around algorithm design
techniques. In this organization, algorithms from different areas of computing are
grouped together if they have the same design approach. I share the belief of many
(e.g., [BaY95]) that this organization is more appropriate for a basic course on the
design and analysis of algorithms. There are three principal reasons for emphasis
on algorithm design techniques. First, these techniques provide a student with
tools for designing algorithms for new problems. This makes learning algorithm
design techniques a very valuable endeavor from a practical standpoint. Second,
they seek to classify multitudes of known algorithms according to an underlying
design idea. Learning to see such commonality among algorithms from different
application areas should be a major goal of computer science education. After all,
every science considers classification of its principal subject as a major if not the
central point of its discipline. Third, in my opinion, algorithm design techniques
have utility as general problem solving strategies, applicable to problems beyond
computing.
xix
xx
Preface
Unfortunately, the traditional classification of algorithm design techniques
has several serious shortcomings, from both theoretical and educational points
of view. The most significant of these shortcomings is the failure to classify many
important algorithms. This limitation has forced the authors of other textbooks
to depart from the design technique organization and to include chapters dealing
with specific problem types. Such a switch leads to a loss of course coherence and
almost unavoidably creates a confusion in students’ minds.
New taxonomy of algorithm design techniques
My frustration with the shortcomings of the traditional classification of algorithm
design techniques has motivated me to develop a new taxonomy of them [Lev99],
which is the basis of this book. Here are the principal advantages of the new
taxonomy:
The new taxonomy is more comprehensive than the traditional one. It includes
several strategies—brute-force, decrease-and-conquer, transform-and-conquer, space and time trade-offs, and iterative improvement—that are rarely
if ever recognized as important design paradigms.
The new taxonomy covers naturally many classic algorithms (Euclid’s algorithm, heapsort, search trees, hashing, topological sorting, Gaussian elimination, Horner’s rule—to name a few) that the traditional taxonomy cannot
classify. As a result, the new taxonomy makes it possible to present the standard body of classic algorithms in a unified and coherent fashion.
It naturally accommodates the existence of important varieties of several
design techniques. For example, it recognizes three variations of decreaseand-conquer and three variations of transform-and-conquer.
It is better aligned with analytical methods for the efficiency analysis (see
Appendix B).
Design techniques as general problem solving strategies
Most applications of the design techniques in the book are to classic problems of
computer science. (The only innovation here is an inclusion of some material on
numerical algorithms, which are covered within the same general framework.)
But these design techniques can be considered general problem solving tools,
whose applications are not limited to traditional computing and mathematical
problems. Two factors make this point particularly important. First, more and
more computing applications go beyond the traditional domain, and there are
reasons to believe that this trend will strengthen in the future. Second, developing
students’ problem solving skills has come to be recognized as a major goal of
college education. Among all the courses in a computer science curriculum, a
course on the design and analysis of algorithms is uniquely suitable for this task
because it can offer a student specific strategies for solving problems.
I am not proposing that a course on the design and analysis of algorithms
should become a course on general problem solving. But I do believe that the
Preface
xxi
unique opportunity provided by studying the design and analysis of algorithms
should not be missed. Toward this goal, the book includes applications to puzzles
and puzzle-like games. Although using puzzles in teaching algorithms is certainly
not a new idea, the book tries to do this systematically by going well beyond a few
standard examples.
Textbook pedagogy
My goal was to write a text that would not trivialize the subject but would still be
readable by most students on their own. Here are some of the things done toward
this objective.
Sharing the opinion of George Forsythe expressed in the epigraph, I have
sought to stress major ideas underlying the design and analysis of algorithms.
In choosing specific algorithms to illustrate these ideas, I limited the number of
covered algorithms to those that demonstrate an underlying design technique
or an analysis method most clearly. Fortunately, most classic algorithms satisfy
this criterion.
In Chapter 2, which is devoted to efficiency analysis, the methods used for
analyzing nonrecursive algorithms are separated from those typically used for
analyzing recursive algorithms. The chapter also includes sections devoted to
empirical analysis and algorithm visualization.
The narrative is systematically interrupted by questions to the reader. Some
of them are asked rhetorically, in anticipation of a concern or doubt, and are
answered immediately. The goal of the others is to prevent the reader from
drifting through the text without a satisfactory level of comprehension.
Each chapter ends with a summary recapping the most important concepts
and results discussed in the chapter.
The book contains over 600 exercises. Some of them are drills; others make
important points about the material covered in the body of the text or introduce algorithms not covered there at all. A few exercises take advantage of
Internet resources. More difficult problems—there are not many of them—
are marked by special symbols in the Instructor’s Manual. (Because marking
problems as difficult may discourage some students from trying to tackle them,
problems are not marked in the book itself.) Puzzles, games, and puzzle-like
questions are marked in the exercises with a special icon.
The book provides hints to all the exercises. Detailed solutions, except for
programming projects, are provided in the Instructor’s Manual, available
to qualified adopters through Pearson’s Instructor Resource Center. (Please
contact your local Pearson sales representative or go to www.pearsonhighered
.com/irc to access this material.) Slides in PowerPoint are available to all
readers of this book via anonymous ftp at the CS Support site: http://cssupport
.pearsoncmg.com/.
xxii
Preface
Changes for the third edition
There are a few changes in the third edition. The most important is the new order of
the chapters on decrease-and-conquer and divide-and-conquer. There are several
advantages in introducing decrease-and-conquer before divide-and-conquer:
Decrease-and-conquer is a simpler strategy than divide-and-conquer.
Decrease-and-conquer is applicable to more problems than divide-and-conquer.
The new order makes it possible to discuss insertion sort before mergesort
and quicksort.
The idea of array partitioning is now introduced in conjunction with the
selection problem. I took advantage of an opportunity to do this via the onedirectional scan employed by Lomuto’s algorithm, leaving the two-directional
scan used by Hoare’s partitioning to a later discussion in conjunction with
quicksort.
Binary search is now considered in the section devoted to decrease-by-aconstant-factor algorithms, where it belongs.
The second important change is restructuring of Chapter 8 on dynamic programming. Specifically:
The introductory section is completely new. It contains three basic examples
that provide a much better introduction to this important technique than
computing a binomial coefficient, the example used in the first two editions.
All the exercises for Section 8.1 are new as well; they include well-known
applications not available in the previous editions.
I also changed the order of the other sections in this chapter to get a smoother
progression from the simpler applications to the more advanced ones.
The other changes include the following. More applications of the algorithms
discussed are included. The section on the graph-traversal algorithms is moved
from the decrease-and-conquer chapter to the brute-force and exhaustive-search
chapter, where it fits better, in my opinion. The Gray code algorithm is added to the
section dealing with algorithms for generating combinatorial objects. The divideand-conquer algorithm for the closest-pair problem is discussed in more detail.
Updates include the section on algorithm visualization, approximation algorithms
for the traveling salesman problem, and, of course, the bibliography.
I also added about 70 new problems to the exercises. Some of them are algorithmic puzzles and questions asked during job interviews.
Prerequisites
The book assumes that a reader has gone through an introductory programming
course and a standard course on discrete structures. With such a background,
he or she should be able to handle the book’s material without undue difficulty.
xxiii
Preface
Still, fundamental data structures, necessary summation formulas, and recurrence
relations are reviewed in Section 1.4, Appendix A, and Appendix B, respectively.
Calculus is used in only three sections (Section 2.2, 11.4, and 12.4), and to a very
limited degree; if students lack calculus as an assured part of their background, the
relevant portions of these three sections can be omitted without hindering their
understanding of the rest of the material.
Use in the curriculum
The book can serve as a textbook for a basic course on design and analysis of
algorithms organized around algorithm design techniques. It might contain slightly
more material than can be covered in a typical one-semester course. By and large,
portions of Chapters 3 through 12 can be skipped without the danger of making
later parts of the book incomprehensible to the reader. Any portion of the book
can be assigned for self-study. In particular, Sections 2.6 and 2.7 on empirical
analysis and algorithm visualization, respectively, can be assigned in conjunction
with projects.
Here is a possible plan for a one-semester course; it assumes a 40-class meeting
format.
Lecture
Topic
Sections
1
2, 3
4
5, 6
7
8
9
10, 11
12
Introduction
Analysis framework; O, , notations
Mathematical analysis of nonrecursive algorithms
Mathematical analysis of recursive algorithms
Brute-force algorithms
Exhaustive search
Depth-first search and breadth-first search
Decrease-by-one: insertion sort, topological sorting
Binary search and other decrease-by-a-constantfactor algorithms
Variable-size-decrease algorithms
Divide-and-conquer: mergesort, quicksort
Other divide-and-conquer examples
Instance simplification: presorting, Gaussian elimination, balanced search trees
Representation change: heaps and heapsort or
Horner’s rule and binary exponentiation
Problem reduction
Space-time trade-offs: string matching, hashing, Btrees
Dynamic programming algorithms
1.1–1.3
2.1, 2.2
2.3
2.4, 2.5 (+ App. B)
3.1, 3.2 (+ 3.3)
3.4
3.5
4.1, 4.2
4.4
13
14, 15
16
17–19
20
21
22–24
25–27
4.5
5.1–5.2
5.3 or 5.4 or 5.5
6.1–6.3
6.4 or 6.5
6.6
7.2–7.4
3 from 8.1–8.4
xxiv
Preface
28–30
31–33
34
35
36
37
38
39
40
Greedy algorithms: Prim’s, Kruskal’s, Dijkstra’s,
Huffman’s
Iterative improvement algorithms
Lower-bound arguments
Decision trees
P, NP, and NP-complete problems
Numerical algorithms
Backtracking
Branch-and-bound
Approximation algorithms for NP-hard problems
9.1–9.4
3 from 10.1–10.4
11.1
11.2
11.3
11.4 (+ 12.4)
12.1
12.2
12.3
Acknowledgments
I would like to express my gratitude to the reviewers and many readers who
have shared with me their opinions about the first two editions of the book and
suggested improvements and corrections. The third edition has certainly benefited from the reviews by Andrew Harrington (Loyola University Chicago),
David Levine (Saint Bonaventure University), Stefano Lombardi (UC Riverside),
Daniel McKee (Mansfield University), Susan Brilliant (Virginia Commonwealth
University), David Akers (University of Puget Sound), and two anonymous reviewers.
My thanks go to all the people at Pearson and their associates who worked
on my book. I am especially grateful to my editor, Matt Goldstein; the editorial
assistant, Chelsea Bell; the marketing manager, Yez Alayan; and the production
supervisor, Kayla Smith-Tarbox. I am also grateful to Richard Camp for copyediting the book, Paul Anagnostopoulos of Windfall Software and Jacqui Scarlott for
its project management and typesetting, and MaryEllen Oliver for proofreading
the book.
Finally, I am indebted to two members of my family. Living with a spouse
writing a book is probably more trying than doing the actual writing. My wife,
Maria, lived through several years of this, helping me any way she could. And help
she did: over 400 figures in the book and the Instructor’s Manual were created
by her. My daughter Miriam has been my English prose guru over many years.
She read large portions of the book and was instrumental in finding the chapter
epigraphs.
Anany Levitin
[email protected]
June 2011
This page intentionally left blank
1
Introduction
Two ideas lie gleaming on the jeweler’s velvet. The first is the calculus, the
second, the algorithm. The calculus and the rich body of mathematical
analysis to which it gave rise made modern science possible; but it has been
the algorithm that has made possible the modern world.
—David Berlinski, The Advent of the Algorithm, 2000
W
hy do you need to study algorithms? If you are going to be a computer
professional, there are both practical and theoretical reasons to study algorithms. From a practical standpoint, you have to know a standard set of important
algorithms from different areas of computing; in addition, you should be able to
design new algorithms and analyze their efficiency. From the theoretical standpoint, the study of algorithms, sometimes called algorithmics, has come to be
recognized as the cornerstone of computer science. David Harel, in his delightful
book pointedly titled Algorithmics: the Spirit of Computing, put it as follows:
Algorithmics is more than a branch of computer science. It is the core of
computer science, and, in all fairness, can be said to be relevant to most of
science, business, and technology. [Har92, p. 6]
But even if you are not a student in a computing-related program, there are
compelling reasons to study algorithms. To put it bluntly, computer programs
would not exist without algorithms. And with computer applications becoming
indispensable in almost all aspects of our professional and personal lives, studying
algorithms becomes a necessity for more and more people.
Another reason for studying algorithms is their usefulness in developing analytical skills. After all, algorithms can be seen as special kinds of solutions to
problems—not just answers but precisely defined procedures for getting answers.
Consequently, specific algorithm design techniques can be interpreted as problemsolving strategies that can be useful regardless of whether a computer is involved.
Of course, the precision inherently imposed by algorithmic thinking limits the
kinds of problems that can be solved with an algorithm. You will not find, for
example, an algorithm for living a happy life or becoming rich and famous. On
1
2
Introduction
the other hand, this required precision has an important educational advantage.
Donald Knuth, one of the most prominent computer scientists in the history of
algorithmics, put it as follows:
A person well-trained in computer science knows how to deal with algorithms:
how to construct them, manipulate them, understand them, analyze them.
This knowledge is preparation for much more than writing good computer
programs; it is a general-purpose mental tool that will be a definite aid to
the understanding of other subjects, whether they be chemistry, linguistics,
or music, etc. The reason for this may be understood in the following way:
It has often been said that a person does not really understand something
until after teaching it to someone else. Actually, a person does not really
understand something until after teaching it to a computer, i.e., expressing
it as an algorithm . . . An attempt to formalize things as algorithms leads to
a much deeper understanding than if we simply try to comprehend things in
the traditional way. [Knu96, p. 9]
We take up the notion of algorithm in Section 1.1. As examples, we use three
algorithms for the same problem: computing the greatest common divisor. There
are several reasons for this choice. First, it deals with a problem familiar to everybody from their middle-school days. Second, it makes the important point that
the same problem can often be solved by several algorithms. Quite typically, these
algorithms differ in their idea, level of sophistication, and efficiency. Third, one of
these algorithms deserves to be introduced first, both because of its age—it appeared in Euclid’s famous treatise more than two thousand years ago—and its
enduring power and importance. Finally, investigation of these three algorithms
leads to some general observations about several important properties of algorithms in general.
Section 1.2 deals with algorithmic problem solving. There we discuss several
important issues related to the design and analysis of algorithms. The different
aspects of algorithmic problem solving range from analysis of the problem and the
means of expressing an algorithm to establishing its correctness and analyzing its
efficiency. The section does not contain a magic recipe for designing an algorithm
for an arbitrary problem. It is a well-established fact that such a recipe does not
exist. Still, the material of Section 1.2 should be useful for organizing your work
on designing and analyzing algorithms.
Section 1.3 is devoted to a few problem types that have proven to be particularly important to the study of algorithms and their application. In fact, there
are textbooks (e.g., [Sed11]) organized around such problem types. I hold the
view—shared by many others—that an organization based on algorithm design
techniques is superior. In any case, it is very important to be aware of the principal problem types. Not only are they the most commonly encountered problem
types in real-life applications, they are used throughout the book to demonstrate
particular algorithm design techniques.
Section 1.4 contains a review of fundamental data structures. It is meant to
serve as a reference rather than a deliberate discussion of this topic. If you need
1.1
What Is an Algorithm?
3
a more detailed exposition, there is a wealth of good books on the subject, most
of them tailored to a particular programming language.
1.1 What Is an Algorithm?
Although there is no universally agreed-on wording to describe this notion, there
is general agreement about what the concept means:
An algorithm is a sequence of unambiguous instructions for solving a
problem, i.e., for obtaining a required output for any legitimate input in
a finite amount of time.
This definition can be illustrated by a simple diagram (Figure 1.1).
The reference to “instructions” in the definition implies that there is something or someone capable of understanding and following the instructions given.
We call this a “computer,” keeping in mind that before the electronic computer
was invented, the word “computer” meant a human being involved in performing numeric calculations. Nowadays, of course, “computers” are those ubiquitous
electronic devices that have become indispensable in almost everything we do.
Note, however, that although the majority of algorithms are indeed intended for
eventual computer implementation, the notion of algorithm does not depend on
such an assumption.
As examples illustrating the notion of the algorithm, we consider in this
section three met
