Introduction to the Design and Analysis of Algorithms, 3rd edition
Published by Pearson (September 29th 2011)  Copyright © 2012
3rd edition
Choose a format

eText
1 option(s)

Introduction to the Design and Analysis of Algorithms (Subscription)
ISBN13: 9780133001365
Includes: eTextA digital version of the text you can personalize and read online or offline.

Print
1 option(s)

Introduction to the Design and Analysis of Algorithms
ISBN13: 9780132316811
Includes: PaperbackYou'll get a bound printed text.
Overview
Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms presents the subject in a coherent and innovative manner. Written in a studentfriendly style, the book emphasizes the understanding of ideas over excessively formal treatment while thoroughly covering the material required in an introductory algorithms course. Popular puzzles are used to motivate students' interest and strengthen their skills in algorithmic problem solving. Other learningenhancement features include chapter summaries, hints to the exercises, and a detailed solution manual.
Table of contents
New to the Third Edition xvii
Preface xix
1Introduction 1
1.1 What Is an Algorithm? 3
Exercises 1.1 7
1.2 Fundamentals of Algorithmic Problem Solving 9
Understanding the Problem 9
Ascertaining the Capabilities of the Computational Device 9
Choosing between Exact and Approximate Problem Solving 11
Algorithm Design Techniques 11
Designing an Algorithm and Data Structures 12
Methods of Specifying an Algorithm 12
Proving an Algorithm’s Correctness 13
Analyzing an Algorithm 14
Coding an Algorithm 15
Exercises 1.2 17
1.3 Important Problem Types 18
Sorting 19
Searching 20
String Processing 20
Graph Problems 21
Combinatorial Problems 21
Geometric Problems 22
Numerical Problems 22
Exercises 1.3 23
1.4 Fundamental Data Structures 25
Linear Data Structures 25
Graphs 28
Trees 31
Sets and Dictionaries 35
Exercises 1.4 37
Summary 38
2 Fundamentals of the Analysis of Algorithm Efficiency 41
2.1 The Analysis Framework 42
Measuring an Input’s Size 43
Units for Measuring Running Time 44
Orders of Growth 45
WorstCase, BestCase, and AverageCase Efficiencies 47
Recapitulation of the Analysis Framework 50
Exercises 2.1 50
2.2 Asymptotic Notations and Basic Efficiency Classes 52
Informal Introduction 52
Onotation 53
notation 54
notation 55
Useful Property Involving the Asymptotic Notations 55
Using Limits for Comparing Orders of Growth 56
Basic Efficiency Classes 58
Exercises 2.2 58
2.3 Mathematical Analysis of Nonrecursive Algorithms 61
Exercises 2.3 67
2.4 Mathematical Analysis of Recursive Algorithms 70
Exercises 2.4 76
2.5 Example: Computing the nth Fibonacci Number 80
Exercises 2.5 83
2.6 Empirical Analysis of Algorithms 84
Exercises 2.6 89
2.7 Algorithm Visualization 91
Summary 94
3 Brute Force and Exhaustive Search 97
3.1 Selection Sort and Bubble Sort 98
Selection Sort 98
Bubble Sort 100
Exercises 3.1 102
3.2 Sequential Search and BruteForce String Matching 104
Sequential Search 104
BruteForce String Matching 105
Exercises 3.2 106
3.3 ClosestPair and ConvexHull Problems by Brute Force 108
ClosestPair Problem 108
ConvexHull Problem 109
Exercises 3.3 113
3.4 Exhaustive Search 115
Traveling Salesman Problem 116
Knapsack Problem 116
Assignment Problem 119
Exercises 3.4 120
3.5 DepthFirst Search and BreadthFirst Search 122
DepthFirst Search 122
BreadthFirst Search 125
Exercises 3.5 128
Summary 130
4 DecreaseandConquer 131
4.1 Insertion Sort 134
Exercises 4.1 136
4.2 Topological Sorting 138
Exercises 4.2 142
4.3 Algorithms for Generating Combinatorial Objects 144
Generating Permutations 144
Generating Subsets 146
Exercises 4.3 148
4.4 DecreasebyaConstantFactor Algorithms 150
Binary Search 150
FakeCoin Problem 152
Russian Peasant Multiplication 153
Josephus Problem 154
Exercises 4.4 156
4.5 VariableSizeDecrease Algorithms 157
Computing a Median and the Selection Problem 158
Interpolation Search 161
Searching and Insertion in a Binary Search Tree 163
The Game of Nim 164
Exercises 4.5 166
Summary 167
5 DivideandConquer 169
5.1 Mergesort 172
Exercises 5.1 174
5.2 Quicksort 176
Exercises 5.2 181
5.3 Binary Tree Traversals and Related Properties 182
Exercises 5.3 185
5.4 Multiplication of Large Integers and
Strassen’s Matrix Multiplication 186
Multiplication of Large Integers 187
Strassen’s Matrix Multiplication 189
Exercises 5.4 191
5.5 The ClosestPair and ConvexHull Problems
by DivideandConquer 192
The ClosestPair Problem 192
ConvexHull Problem 195
Exercises 5.5 197
Summary 198
6 TransformandConquer 201
6.1 Presorting 202
Exercises 6.1 205
6.2 Gaussian Elimination 208
LU Decomposition 212
Computing a Matrix Inverse 214
Computing a Determinant 215
Exercises 6.2 216
6.3 Balanced Search Trees 218
AVL Trees 218
23 Trees 223
Exercises 6.3 225
6.4 Heaps and Heapsort 226
Notion of the Heap 227
Heapsort 231
Exercises 6.4 233
6.5 Horner’s Rule and Binary Exponentiation 234
Horner’s Rule 234
Binary Exponentiation 236
Exercises 6.5 239
6.6 Problem Reduction 240
Computing the Least Common Multiple 241
Counting Paths in a Graph 242
Reduction of Optimization Problems 243
Linear Programming 244
Reduction to Graph Problems 246
Exercises 6.6 248
Summary 250
7 Space and Time TradeOffs 253
7.1 Sorting by Counting 254
Exercises 7.1 257
7.2 Input Enhancement in String Matching 258
Horspool’s Algorithm 259
BoyerMoore Algorithm 263
Exercises 7.2 267
7.3 Hashing 269
Open Hashing (Separate Chaining) 270
Closed Hashing (Open Addressing) 272
Exercises 7.3 274
7.4 BTrees 276
Exercises 7.4 279
Summary 280
8 Dynamic Programming 283
8.1 Three Basic Examples 285
Exercises 8.1 290
8.2 The Knapsack Problem and Memory Functions 292
Memory Functions 294
Exercises 8.2 296
8.3 Optimal Binary Search Trees 297
Exercises 8.3 303
8.4 Warshall’s and Floyd’s Algorithms 304
Warshall’s Algorithm 304
Floyd’s Algorithm for the AllPairs ShortestPaths Problem 308
Exercises 8.4 311
Summary 312
9 Greedy Technique 315
9.1 Prim’s Algorithm 318
Exercises 9.1 322
9.2 Kruskal’s Algorithm 325
Disjoint Subsets and UnionFind Algorithms 327
Exercises 9.2 331
9.3 Dijkstra’s Algorithm 333
Exercises 9.3 337
9.4 Huffman Trees and Codes 338
Exercises 9.4 342
Summary 344
10 Iterative Improvement 345
10.1 The Simplex Method 346
Geometric Interpretation of Linear Programming 347
An Outline of the Simplex Method 351
Further Notes on the Simplex Method 357
Exercises 10.1 359
10.2 The MaximumFlow Problem 361
Exercises 10.2 371
10.3 Maximum Matching in Bipartite Graphs 372
Exercises 10.3 378
10.4 The Stable Marriage Problem 380
Exercises 10.4 383
Summary 384
11 Limitations of Algorithm Power 387
11.1 LowerBound Arguments 388
Trivial Lower Bounds 389
InformationTheoretic Arguments 390
Adversary Arguments 390
Problem Reduction 391
Exercises 11.1 393
11.2 Decision Trees 394
Decision Trees for Sorting 395
Decision Trees for Searching a Sorted Array 397
Exercises 11.2 399
11.3 P, NP, and NPComplete Problems 401
P and NP Problems 402
NPComplete Problems 406
Exercises 11.3 409
11.4 Challenges of Numerical Algorithms 412
Exercises 11.4 419
Summary 420
12 Coping with the Limitations of Algorithm Power 423
12.1 Backtracking 424
nQueens Problem 425
Hamiltonian Circuit Problem 426
SubsetSum Problem 427
General Remarks 428
Exercises 12.1 430
12.2 BranchandBound 432
Assignment Problem 433
Knapsack Problem 436
Traveling Salesman Problem 438
Exercises 12.2 440
12.3 Approximation Algorithms for NPHard Problems 441
Approximation Algorithms for the Traveling Salesman Problem 443
Approximation Algorithms for the Knapsack Problem 453
Exercises 12.3 457
12.4 Algorithms for Solving Nonlinear Equations 459
Bisection Method 460
Method of False Position 464
Newton’s Method 464
Exercises 12.4 467
Summary 468
Epilogue 471
APPENDIX A
Useful Formulas for the Analysis of Algorithms 475
Properties of Logarithms 475
Combinatorics 475
Important Summation Formulas 476
Sum Manipulation Rules 476
Approximation of a Sum by a Definite Integral 477
Floor and Ceiling Formulas 477
Miscellaneous 477
APPENDIX B
Short Tutorial on Recurrence Relations 479
Sequences and Recurrence Relations 479
Methods for Solving Recurrence Relations 480
Common Recurrence Types in Algorithm Analysis 485
References 493
Hints to Exercises 503
Index 547
Preface xix
1Introduction 1
1.1 What Is an Algorithm? 3
Exercises 1.1 7
1.2 Fundamentals of Algorithmic Problem Solving 9
Understanding the Problem 9
Ascertaining the Capabilities of the Computational Device 9
Choosing between Exact and Approximate Problem Solving 11
Algorithm Design Techniques 11
Designing an Algorithm and Data Structures 12
Methods of Specifying an Algorithm 12
Proving an Algorithm’s Correctness 13
Analyzing an Algorithm 14
Coding an Algorithm 15
Exercises 1.2 17
1.3 Important Problem Types 18
Sorting 19
Searching 20
String Processing 20
Graph Problems 21
Combinatorial Problems 21
Geometric Problems 22
Numerical Problems 22
Exercises 1.3 23
1.4 Fundamental Data Structures 25
Linear Data Structures 25
Graphs 28
Trees 31
Sets and Dictionaries 35
Exercises 1.4 37
Summary 38
2 Fundamentals of the Analysis of Algorithm Efficiency 41
2.1 The Analysis Framework 42
Measuring an Input’s Size 43
Units for Measuring Running Time 44
Orders of Growth 45
WorstCase, BestCase, and AverageCase Efficiencies 47
Recapitulation of the Analysis Framework 50
Exercises 2.1 50
2.2 Asymptotic Notations and Basic Efficiency Classes 52
Informal Introduction 52
Onotation 53
notation 54
notation 55
Useful Property Involving the Asymptotic Notations 55
Using Limits for Comparing Orders of Growth 56
Basic Efficiency Classes 58
Exercises 2.2 58
2.3 Mathematical Analysis of Nonrecursive Algorithms 61
Exercises 2.3 67
2.4 Mathematical Analysis of Recursive Algorithms 70
Exercises 2.4 76
2.5 Example: Computing the nth Fibonacci Number 80
Exercises 2.5 83
2.6 Empirical Analysis of Algorithms 84
Exercises 2.6 89
2.7 Algorithm Visualization 91
Summary 94
3 Brute Force and Exhaustive Search 97
3.1 Selection Sort and Bubble Sort 98
Selection Sort 98
Bubble Sort 100
Exercises 3.1 102
3.2 Sequential Search and BruteForce String Matching 104
Sequential Search 104
BruteForce String Matching 105
Exercises 3.2 106
3.3 ClosestPair and ConvexHull Problems by Brute Force 108
ClosestPair Problem 108
ConvexHull Problem 109
Exercises 3.3 113
3.4 Exhaustive Search 115
Traveling Salesman Problem 116
Knapsack Problem 116
Assignment Problem 119
Exercises 3.4 120
3.5 DepthFirst Search and BreadthFirst Search 122
DepthFirst Search 122
BreadthFirst Search 125
Exercises 3.5 128
Summary 130
4 DecreaseandConquer 131
4.1 Insertion Sort 134
Exercises 4.1 136
4.2 Topological Sorting 138
Exercises 4.2 142
4.3 Algorithms for Generating Combinatorial Objects 144
Generating Permutations 144
Generating Subsets 146
Exercises 4.3 148
4.4 DecreasebyaConstantFactor Algorithms 150
Binary Search 150
FakeCoin Problem 152
Russian Peasant Multiplication 153
Josephus Problem 154
Exercises 4.4 156
4.5 VariableSizeDecrease Algorithms 157
Computing a Median and the Selection Problem 158
Interpolation Search 161
Searching and Insertion in a Binary Search Tree 163
The Game of Nim 164
Exercises 4.5 166
Summary 167
5 DivideandConquer 169
5.1 Mergesort 172
Exercises 5.1 174
5.2 Quicksort 176
Exercises 5.2 181
5.3 Binary Tree Traversals and Related Properties 182
Exercises 5.3 185
5.4 Multiplication of Large Integers and
Strassen’s Matrix Multiplication 186
Multiplication of Large Integers 187
Strassen’s Matrix Multiplication 189
Exercises 5.4 191
5.5 The ClosestPair and ConvexHull Problems
by DivideandConquer 192
The ClosestPair Problem 192
ConvexHull Problem 195
Exercises 5.5 197
Summary 198
6 TransformandConquer 201
6.1 Presorting 202
Exercises 6.1 205
6.2 Gaussian Elimination 208
LU Decomposition 212
Computing a Matrix Inverse 214
Computing a Determinant 215
Exercises 6.2 216
6.3 Balanced Search Trees 218
AVL Trees 218
23 Trees 223
Exercises 6.3 225
6.4 Heaps and Heapsort 226
Notion of the Heap 227
Heapsort 231
Exercises 6.4 233
6.5 Horner’s Rule and Binary Exponentiation 234
Horner’s Rule 234
Binary Exponentiation 236
Exercises 6.5 239
6.6 Problem Reduction 240
Computing the Least Common Multiple 241
Counting Paths in a Graph 242
Reduction of Optimization Problems 243
Linear Programming 244
Reduction to Graph Problems 246
Exercises 6.6 248
Summary 250
7 Space and Time TradeOffs 253
7.1 Sorting by Counting 254
Exercises 7.1 257
7.2 Input Enhancement in String Matching 258
Horspool’s Algorithm 259
BoyerMoore Algorithm 263
Exercises 7.2 267
7.3 Hashing 269
Open Hashing (Separate Chaining) 270
Closed Hashing (Open Addressing) 272
Exercises 7.3 274
7.4 BTrees 276
Exercises 7.4 279
Summary 280
8 Dynamic Programming 283
8.1 Three Basic Examples 285
Exercises 8.1 290
8.2 The Knapsack Problem and Memory Functions 292
Memory Functions 294
Exercises 8.2 296
8.3 Optimal Binary Search Trees 297
Exercises 8.3 303
8.4 Warshall’s and Floyd’s Algorithms 304
Warshall’s Algorithm 304
Floyd’s Algorithm for the AllPairs ShortestPaths Problem 308
Exercises 8.4 311
Summary 312
9 Greedy Technique 315
9.1 Prim’s Algorithm 318
Exercises 9.1 322
9.2 Kruskal’s Algorithm 325
Disjoint Subsets and UnionFind Algorithms 327
Exercises 9.2 331
9.3 Dijkstra’s Algorithm 333
Exercises 9.3 337
9.4 Huffman Trees and Codes 338
Exercises 9.4 342
Summary 344
10 Iterative Improvement 345
10.1 The Simplex Method 346
Geometric Interpretation of Linear Programming 347
An Outline of the Simplex Method 351
Further Notes on the Simplex Method 357
Exercises 10.1 359
10.2 The MaximumFlow Problem 361
Exercises 10.2 371
10.3 Maximum Matching in Bipartite Graphs 372
Exercises 10.3 378
10.4 The Stable Marriage Problem 380
Exercises 10.4 383
Summary 384
11 Limitations of Algorithm Power 387
11.1 LowerBound Arguments 388
Trivial Lower Bounds 389
InformationTheoretic Arguments 390
Adversary Arguments 390
Problem Reduction 391
Exercises 11.1 393
11.2 Decision Trees 394
Decision Trees for Sorting 395
Decision Trees for Searching a Sorted Array 397
Exercises 11.2 399
11.3 P, NP, and NPComplete Problems 401
P and NP Problems 402
NPComplete Problems 406
Exercises 11.3 409
11.4 Challenges of Numerical Algorithms 412
Exercises 11.4 419
Summary 420
12 Coping with the Limitations of Algorithm Power 423
12.1 Backtracking 424
nQueens Problem 425
Hamiltonian Circuit Problem 426
SubsetSum Problem 427
General Remarks 428
Exercises 12.1 430
12.2 BranchandBound 432
Assignment Problem 433
Knapsack Problem 436
Traveling Salesman Problem 438
Exercises 12.2 440
12.3 Approximation Algorithms for NPHard Problems 441
Approximation Algorithms for the Traveling Salesman Problem 443
Approximation Algorithms for the Knapsack Problem 453
Exercises 12.3 457
12.4 Algorithms for Solving Nonlinear Equations 459
Bisection Method 460
Method of False Position 464
Newton’s Method 464
Exercises 12.4 467
Summary 468
Epilogue 471
APPENDIX A
Useful Formulas for the Analysis of Algorithms 475
Properties of Logarithms 475
Combinatorics 475
Important Summation Formulas 476
Sum Manipulation Rules 476
Approximation of a Sum by a Definite Integral 477
Floor and Ceiling Formulas 477
Miscellaneous 477
APPENDIX B
Short Tutorial on Recurrence Relations 479
Sequences and Recurrence Relations 479
Methods for Solving Recurrence Relations 480
Common Recurrence Types in Algorithm Analysis 485
References 493
Hints to Exercises 503
Index 547
For teachers
All the material you need to teach your courses.
Discover teaching material