 Shopping Bag ( 0 items )

All (19) from $45.75

New (14) from $64.05

Used (5) from $45.75
More About This Textbook
Overview
Foundations of Algorithms, Fourth Edition offers a wellbalanced presentation of algorithm design, complexity analysis of algorithms, and computational complexity. The volume is accessible to mainstream computer science students who have a background in college algebra and discrete structures. To support their approach, the authors present mathematical concepts using standard English and a simpler notation than is found in most texts. A review of essential mathematical concepts is presented in three appendices. The authors also reinforce the explanations with numerous concrete examples to help students grasp theoretical concepts.
Product Details
Related Subjects
Table of Contents
Chapter 1 Algorithms: Efficiency, Analysis, and Order 1
1.1 Algorithms 2
1.2 The Importance of Developing Efficient Algorithms 9
1.2.1 Sequential Search Versus Binary Search 9
1.2.2 The Fibonacci Sequence 12
1.3 Analysis of Algorithms 17
1.3.1 Complexity Analysis 17
1.3.2 Applying the Theory 24
1.3.3 Analysis of Correctness 24
1.4 Order 25
1.4.1 An Intuitive Introduction to Order 25
1.4.2 A Rigorous Introduction to Order 28
1.4.3 Using a Limit to Determine Order 39
1.5 Outline of This Book 41
Exercises 42
Chapter 2 DivideandConquer 47
2.1 Binary Search 48
2.2 Mergesort 53
2.3 The DivideandConquer Approach 59
2.4 Quicksort (Partition Exchange Sort) 60
2.5 Strassen's Matrix Multiplication Algorithm 67
2.6 Arithmetic with Large Numbers 72
2.6.1 Representation of Large Integers: Addition and Other LinearTime Operations 72
2.6.2 Multiplication of Large Integers 72
2.7 Determining Thresholds 78
2.8 When Not to Use DivideandConquer 82
Exercises 83
Chapter 3 Dynamic Programming 91
3.1 The Binomial Coefficient 92
3.2 Floyd's Algorithm for Shortest Paths 97
3.3 Dynamic Programming and Optimization Problems 105
3.4 Chained Matrix Multiplication 107
3.5 Optimal Binary Search Trees 116
3.6 The Traveling Salesperson Problem 125
3.7 Sequence Alignment 133
Exercises 141
Chapter 4 The Greedy Approach 145
4.1 Minimum Spanning Trees 148
4.1.1 Prim's Algorithm 152
4.1.2 Kruskal's Algorithm 158
4.1.3 Comparing Prim's Algorithm with Kruskal's Algorithm 163
4.1.4 Final Discussion 163
4.2 Dijkstra's Algorithm for SingleSource Shortest Paths 164
4.3 Scheduling 167
4.3.1 Minimizing Total Time in the System 167
4.3.2 Scheduling with Deadlines 170
4.4 Huffman Code 177
4.4.1 Prefix Codes 178
4.4.2 Huffman's Algorithm 179
4.5 The Greedy Approach Versus Dynamic Programming: The Knapsack Problem 183
4.5.1 A Greedy Approach to the 01 Knapsack Problem 183
4.5.2 A Greedy Approach to the Fractional Knapsack Problem 185
4.5.3 A Dynamic Programming Approach to the 01 Knapsack Problem 185
4.5.4 A Refinement of the Dynamic Programming Algorithm for the 01 Knapsack Problem 186
Exercises 189
Chapter 5 Backtracking 197
5.1 The Backtracking Technique 198
5.2 The nQueens Problem 206
5.3 Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm 210
5.4 The SumofSubsets Problem 214
5.5 Graph Coloring 219
5.6 The Hamiltonian Circuits Problem 224
5.7 The 01 Knapsack Problem 227
5.7.1 A Backtracking Algorithm for the 01 Knapsack Problem 227
5.7.2 Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 01 Knapsack Problem 237
Exercises 237
Chapter 6 BranchandBound 243
6.1 Illustrating BranchandBound with the 01 Knapsack Problem 245
6.1.1 BreadthFirst Search with BranchandBound Pruning 245
6.1.2 BestFirst Search with BranchandBound Pruning 251
6.2 The Traveling Salesperson Problem 26
6.3 Abductive Inference (Diagnosis) 265
Exercises 274
Chapter 7 Introduction to Computational Complexity: The Sorting Problem 277
7.1 Computational Complexity 278
7.2 Insertion Sort and Selection Sort 280
7.3 Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison 285
7.4 Mergesort Revisited 287
7.5 Quicksort Revisited 293
7.6 Heapsort 295
7.6.1 Heaps and Basic Heap Routines 295
7.6.2 An Implementation of Heapsort 299
7.7 Comparison of Mergesort, Quicksort, and Heapsort 306
7.8 Lower Bounds for Sorting Only by Comparison of Keys 307
7.8.1 Decision Trees for Sorting Algorithms 307
7.8.2 Lower Bounds for WorstCase Behavior 310
7.8.3 Lower Bounds for AverageCase Behavior 313
7.9 Sorting by Distribution (Radix Sort) 318
Exercises 322
Chapter 8 More Computational Complexity: The Searching Problem 329
8.1 Lower Bounds for Searching Only by Comparisons of Keys 330
8.1.1 Lower Bounds for WorstCase Behavior 332
8.1.2 Lower Bounds for AverageCase Behavior 334
8.2 Interpolation Search 340
8.3 Searching in Trees 343
8.3.1 Binary Search Trees 344
8.3.2 BTrees 348
8.4 Hashing 349
8.5 The Selection Problem: Introduction to Adversary Arguments 354
8.5.1 Finding the Largest Key 355
8.5.2 Finding Both the Smallest and Largest Keys 356
8.5.3 Finding the SecondLargest Key 363
8.5.4 Finding the kthSmallest Key 368
8.5.5 A Probabilistic Algorithm for the Selection Problem 376
Exercises 380
Chapter 9 Computational Complexity and intractability: An Introduction to the Theory of NP 385
9.1 Intractability 386
9.2 Input Size Revisited 388
9.3 The Three General Problems 392
9.3.1 Problems for Which PolynomialTime Algorithms Have Been Found 392
9.3.2 Problems That Have Been Proven to Be Intractable 392
9.3.3 Problems That Have Not Been Proven to Be Intractable but for Which PolynomialTime Algorithms Have Never Been Found 393
9.4 The Theory of NP 394
9.4.1 The Sets P and NP 396
9.4.2 NPComplete Problems 400
9.4.3 NPHard, NPEasy, and NPEquivalent Problems 412
9.5 Handling NPHard Problems 416
9.5.1 An Approximation Algorithm for the Traveling Salesperson Problem 417
9.5.2 An Approximation Algorithm for the BinPacking Problem 421
Exercises 426
Chapter 10 NumberTheoretic Algorithms 429
10.1 Number Theory Review 430
10.1.1 Composite and Prime Numbers 430
10.1.2 Greatest Common Divisor 431
10.1.3 Prime Factorization 434
10.1.4 Least Common Multiple 437
10.2 Computing the Greatest Common Divisor 437
10.2.1 Euclid's Algorithm 438
10.2.2 An Extension to Euclid's Algorithm 442
10.3 Modular Arithmetic Review 444
10.3.1 Group Theory 444
10.3.2 Congruency Modulo n 446
10.3.3 Subgroups 452
10.4 Solving Modular Linear Equations 458
10.5 Computing Modular Powers 464
10.6 Finding Large Prime Numbers 466
10.6.1 Searching for a Large Prime 467
10.6.2 Checking if a Number Is Prime 468
10.7 The RSA PublicKey Cryptosystem 486
10.7.1 PublicKey Cryptosystems 486
10.7.2 The RSA Cryptosystem 487
Exercises 490
Chapter 11 Introduction to Parallel Algorithms 495
11.1 Parallel Architectures 498
11.1.1 Control Mechanism 498
11.1.2 AddressSpace Organization 500
11.1.3 Interconnection Networks 501
11.2 The PRAM Model 505
11.2.1 Designing Algorithms for the CREW PRAM Model 507
11.2.2 Designing Algorithms for the CRCW PRAM Model 515
Exercises 518
Appendix A Review of Necessary Mathematics 521
A.l Notation 521
A.2 Functions 523
A.3 Mathematical Induction 524
A.4 Theorems and Lemmas 531
A.5 Logarithms 532
A.5.1 Definition and Properties of Logarithms 532
A.5.2 The Natural Logarithm 534
A.6 Sets 536
A.7 Permutations and Combinations 538
A.8 Probability 541
A.8.1 Randomness 546
A.8.2 The Expected Value 550
Exercises 552
Appendix B Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms 559
B.l Solving Recurrences Using Induction 559
B.2 Solving Recurrences Using the Characteristic Equation 563
B.2.1 Homogeneous Linear Recurrences 563
B.2.2 Nonhomogeneous Linear Recurrences 572
B.2.3 Change of Variables (Domain Transformations) 578
B.3 Solving Recurrences by Substitution 581
B.4 Extending Results for n, a Power of a Positive Constant b, to n in General 583
B.5 Proofs of Theorems 589
Exercises 592
Appendix C Data Structures for Disjoint Sets 599
References 609
Index 615