Foundations of Algorithms

by Neapolitan, Richard E.

• ISBN13: 9780763782504
• ISBN10: 0763782505
• Edition: 4th
• Format: Hardcover
• Copyright: 2009-12-28
• Publisher: Jones & Bartlett Learning

Summary

Revised and updated, the Fourth Edition of Foundations of Algorithms continues to offer a well-balanced presentation of algorithm design, complexity of algorithms and computational complexity. Perfect for mainstream computer science students with a background in college algebra and discrete structures, this edition presents mathematical concepts using lucid explanations and a simpler notation than is found in most texts. The authors reinforce key algorithmic explanations with numerous concrete examples to help students grasp theoretical concepts.

Table of Contents

Algorithms: Efficiency, Analysis, and Order	p. 1
Algorithms	p. 2
The Importance of Developing Efficient Algorithms	p. 9
Sequential Search Versus Binary Search	p. 9
The Fibonacci Sequence	p. 12
Analysis of Algorithms	p. 17
Complexity Analysis	p. 17
Applying the Theory	p. 24
Analysis of Correctness	p. 24
Order	p. 25
An Intuitive Introduction to Order	p. 25
A Rigorous Introduction to Order	p. 28
Using a Limit to Determine Order	p. 39
Outline of This Book	p. 41
Exercises	p. 42
Divide-and-Conquer	p. 47
Binary Search	p. 48
Mergesort	p. 53
The Divide-and-Conquer Approach	p. 59
Quicksort (Partition Exchange Sort)	p. 60
Strassen's Matrix Multiplication Algorithm	p. 67
Arithmetic with Large Numbers	p. 72
Representation of Large Integers: Addition and Other Linear-Time Operations	p. 72
Multiplication of Large Integers	p. 72
Determining Thresholds	p. 78
When Not to Use Divide-and-Conquer	p. 82
Exercises	p. 83
Dynamic Programming	p. 91
The Binomial Coefficient	p. 92
Floyd's Algorithm for Shortest Paths	p. 97
Dynamic Programming and Optimization Problems	p. 105
Chained Matrix Multiplication	p. 107
Optimal Binary Search Trees	p. 116
The Traveling Salesperson Problem	p. 125
Sequence Alignment	p. 133
Exercises	p. 141
The Greedy Approach	p. 145
Minimum Spanning Trees	p. 148
Prim's Algorithm	p. 152
Kruskal's Algorithm	p. 158
Comparing Prim's Algorithm with Kruskal's Algorithm	p. 163
Final Discussion	p. 163
Dijkstra's Algorithm for Single-Source Shortest Paths	p. 164
Scheduling	p. 167
Minimizing Total Time in the System	p. 167
Scheduling with Deadlines	p. 170
Huffman Code	p. 177
Prefix Codes	p. 178
Huffman's Algorithm	p. 179
The Greedy Approach Versus Dynamic Programming: The Knapsack Problem	p. 183
A Greedy Approach to the 0-1 Knapsack Problem	p. 183
A Greedy Approach to the Fractional Knapsack Problem	p. 185
A Dynamic Programming Approach to the 0-1 Knapsack Problem	p. 185
A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem	p. 186
Exercises	p. 189
Backtracking	p. 197
The Backtracking Technique	p. 198
The n-Queens Problem	p. 206
Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm	p. 210
The Sum-of-Subsets Problem	p. 214
Graph Coloring	p. 219
The Hamiltonian Circuits Problem	p. 224
The 0-1 Knapsack Problem	p. 227
A Backtracking Algorithm for the 0-1 Knapsack Problem	p. 227
Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem	p. 237
Exercises	p. 237
Branch-and-Bound	p. 243
Illustrating Branch-and-Bound with the 0-1 Knapsack Problem	p. 245
Breadth-First Search with Branch-and-Bound Pruning	p. 245
Best-First Search with Branch-and-Bound Pruning	p. 251
The Traveling Salesperson Problem	p. 26
Abductive Inference (Diagnosis)	p. 265
Exercises	p. 274
Introduction to Computational Complexity: The Sorting Problem	p. 277
Computational Complexity	p. 278
Insertion Sort and Selection Sort	p. 280
Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison	p. 285
Mergesort Revisited	p. 287
Quicksort Revisited	p. 293
Heapsort	p. 295
Heaps and Basic Heap Routines	p. 295
An Implementation of Heapsort	p. 299
Comparison of Mergesort, Quicksort, and Heapsort	p. 306
Lower Bounds for Sorting Only by Comparison of Keys	p. 307
Decision Trees for Sorting Algorithms	p. 307
Lower Bounds for Worst-Case Behavior	p. 310
Lower Bounds for Average-Case Behavior	p. 313
Sorting by Distribution (Radix Sort)	p. 318
Exercises	p. 322
More Computational Complexity: The Searching Problem	p. 329
Lower Bounds for Searching Only by Comparisons of Keys	p. 330
Lower Bounds for Worst-Case Behavior	p. 332
Lower Bounds for Average-Case Behavior	p. 334
Interpolation Search	p. 340
Searching in Trees	p. 343
Binary Search Trees	p. 344
B-Trees	p. 348
Hashing	p. 349
The Selection Problem: Introduction to Adversary Arguments	p. 354
Finding the Largest Key	p. 355
Finding Both the Smallest and Largest Keys	p. 356
Finding the Second-Largest Key	p. 363
Finding the kth-Smallest Key	p. 368
A Probabilistic Algorithm for the Selection Problem	p. 376
Exercises	p. 380
Computational Complexity and intractability: An Introduction to the Theory of NP	p. 385
Intractability	p. 386
Input Size Revisited	p. 388
The Three General Problems	p. 392
Problems for Which Polynomial-Time Algorithms Have Been Found	p. 392
Problems That Have Been Proven to Be Intractable	p. 392
Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found	p. 393
The Theory of NP	p. 394
The Sets P and NP	p. 396
NP-Complete Problems	p. 400
NP-Hard, NP-Easy, and NP-Equivalent Problems	p. 412
Handling NP-Hard Problems	p. 416
An Approximation Algorithm for the Traveling Salesperson Problem	p. 417
An Approximation Algorithm for the Bin-Packing Problem	p. 421
Exercises	p. 426
Number-Theoretic Algorithms	p. 429
Number Theory Review	p. 430
Composite and Prime Numbers	p. 430
Greatest Common Divisor	p. 431
Prime Factorization	p. 434
Least Common Multiple	p. 437
Computing the Greatest Common Divisor	p. 437
Euclid's Algorithm	p. 438
An Extension to Euclid's Algorithm	p. 442
Modular Arithmetic Review	p. 444
Group Theory	p. 444
Congruency Modulo n	p. 446
Subgroups	p. 452
Solving Modular Linear Equations	p. 458
Computing Modular Powers	p. 464
Finding Large Prime Numbers	p. 466
Searching for a Large Prime	p. 467
Checking if a Number Is Prime	p. 468
The RSA Public-Key Cryptosystem	p. 486
Public-Key Cryptosystems	p. 486
The RSA Cryptosystem	p. 487
Exercises	p. 490
Introduction to Parallel Algorithms	p. 495
Parallel Architectures	p. 498
Control Mechanism	p. 498
Address-Space Organization	p. 500
Interconnection Networks	p. 501
The PRAM Model	p. 505
Designing Algorithms for the CREW PRAM Model	p. 507
Designing Algorithms for the CRCW PRAM Model	p. 515
Exercises	p. 518
Review of Necessary Mathematics	p. 521
Notation	p. 521
Functions	p. 523
Mathematical Induction	p. 524
Theorems and Lemmas	p. 531
Logarithms	p. 532
Definition and Properties of Logarithms	p. 532
The Natural Logarithm	p. 534
Sets	p. 536
Permutations and Combinations	p. 538
Probability	p. 541
Randomness	p. 546
The Expected Value	p. 550
Exercises	p. 552
Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms	p. 559
Solving Recurrences Using Induction	p. 559
Solving Recurrences Using the Characteristic Equation	p. 563
Homogeneous Linear Recurrences	p. 563
Nonhomogeneous Linear Recurrences	p. 572
Change of Variables (Domain Transformations)	p. 578
Solving Recurrences by Substitution	p. 581
Extending Results for n, a Power of a Positive Constant b, to n in General	p. 583
Proofs of Theorems	p. 589
Exercises	p. 592
Data Structures for Disjoint Sets	p. 599
References	p. 609
Index	p. 615
Table of Contents provided by Ingram. All Rights Reserved.