Foundations of Algorithms

0004/E4th edition.

Neapolitan, Richard E. 저자(글)

Jones & Bartlett Publishers · 2009년 12월 28일

책 소개

작가정보

저자(글) Neapolitan, Richard E.

목차

• 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.

기본정보

ISBN	9780763782504 ( 0763782505 )
발행(출시)일자	2009년 12월 28일
쪽수	627쪽
크기	188 * 229 * 36 mm / 1224 g
총권수	1권
언어	영어