Foundations of Algorithms Using Java Pseudocode / Edition 1
by Richard Neapolitan, Kumarss NaimipourView All Available Formats & Editions
ISBN-10: 0763721298
ISBN-13: 9780763721299
Pub. Date: 02/13/2004
Publisher: Jones & Bartlett Learning
Foundations of Algorithms Using Java Pseudocode offers a well-balanced presentation on designing algorithms, complexity analysis of algorithms, and computational complexity that 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
Overview
Foundations of Algorithms Using Java Pseudocode offers a well-balanced presentation on designing algorithms, complexity analysis of algorithms, and computational complexity that 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. In addition, they reinforce the explanations with numerous concrete examples to help students grasp theoretical concepts.
Product Details
- ISBN-13:
- 9780763721299
- Publisher:
- Jones & Bartlett Learning
- Publication date:
- 02/13/2004
- Edition description:
- 1E
- Pages:
- 544
- Product dimensions:
- 7.50(w) x 9.30(h) x 1.10(d)
Table of Contents
| Preface | v | |
| Chapter 1 | Algorithms: Efficiency, Analysis, and Order | 1 |
| 1.1 | Algorithms | 2 |
| 1.2 | The Importance of Developing Efficient Algorithms | 9 |
| 1.3 | Analysis of Algorithms | 17 |
| 1.4 | Order | 25 |
| 1.5 | Outline of This Book | 41 |
| Exercises | 42 | |
| Chapter 2 | Divide-and-Conquer | 47 |
| 2.1 | Binary Search | 48 |
| 2.2 | Mergesort | 53 |
| 2.3 | The Divide-and-Conquer Approach | 59 |
| 2.4 | Quicksort (Partition Exchange Sort) | 60 |
| 2.5 | Strassen's Matrix Multiplication Algorithm | 67 |
| 2.6 | Arithmetic with Large Integers | 72 |
| 2.7 | Determining Thresholds | 78 |
| 2.8 | When Not to Use Divide-and-Conquer | 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 |
| Exercises | 133 | |
| Chapter 4 | The Greedy Approach | 137 |
| 4.1 | Minimum Spanning Trees | 140 |
| 4.2 | Dijkstra's Algorithm for Single-Source Shortest Paths | 156 |
| 4.3 | Scheduling | 159 |
| 4.4 | Huffman Code | 169 |
| 4.5 | The Greedy Approach versus Dynamic Programming: The Knapsack Problem | 175 |
| Exercises | 181 | |
| Chapter 5 | Backtracking | 187 |
| 5.1 | The Backtracking Technique | 188 |
| 5.2 | The n-Queens Problem | 196 |
| 5.3 | Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm | 200 |
| 5.4 | The Sum-of-Subsets Problem | 204 |
| 5.5 | Graph Coloring | 209 |
| 5.6 | The Hamiltonian Circuits Problem | 214 |
| 5.7 | The 0-1 Knapsack Problem | 217 |
| Exercises | 227 | |
| Chapter 6 | Branch-and-Bound | 233 |
| 6.1 | Illustrating Branch-and-Bound with the 0-1 Knapsack Problem | 235 |
| 6.2 | The Traveling Salesperson Problem | 246 |
| 6.3 | Abductive Inference (Diagnosis) | 255 |
| Exercises | 264 | |
| Chapter 7 | Introduction to Computational Complexity: The Sorting Problem | 267 |
| 7.1 | Computational Complexity | 268 |
| 7.2 | Insertion Sort and Selection Sort | 270 |
| 7.3 | Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison | 275 |
| 7.4 | Mergesort Revisited | 277 |
| 7.5 | Quicksort Revisited | 283 |
| 7.6 | Heapsort | 285 |
| 7.7 | Comparison of Mergesort, Quicksort, and Heapsort | 296 |
| 7.8 | Lower Bounds for Sorting Only by Comparison of Keys | 297 |
| 7.9 | Sorting by Distribution (Radix Sort) | 308 |
| Exercises | 312 | |
| Chapter 8 | More Computational Complexity: The Searching Problem | 319 |
| 8.1 | Lower Bounds for Searching Only by Comparisons of Keys | 320 |
| 8.2 | Interpolation Search | 330 |
| 8.3 | Searching in Trees | 333 |
| 8.4 | Hashing | 339 |
| 8.5 | The Selection Problem: Introduction to Adversary Arguments | 344 |
| Exercises | 370 | |
| Chapter 9 | Computational Complexity and Intractability: An Introduction to the Theory of NP | 375 |
| 9.1 | Intractability | 376 |
| 9.2 | Input Size Revisited | 378 |
| 9.3 | The Three General Problems | 382 |
| 9.4 | The Theory of NP | 384 |
| 9.5 | Handling NP-Hard Problems | 406 |
| Exercises | 416 | |
| Chapter 10 | Number-Theoretic Algorithms | 419 |
| 10.1 | Number Theory Review | 420 |
| 10.2 | Computing the Greatest Common Divisor | 427 |
| 10.3 | Modular Arithmetic Review | 434 |
| 10.4 | Solving Modular Linear Equations | 448 |
| 10.5 | Computing Modular Powers | 454 |
| 10.6 | Finding Large Prime Numbers | 456 |
| 10.7 | The RSA Public-Key Cryptosystem | 476 |
| Exercises | 480 | |
| Chapter 11 | Introduction to Parallel Algorithms | 485 |
| 11.1 | Parallel Architectures | 488 |
| 11.2 | The PRAM Model | 495 |
| Exercises | 508 | |
| Appendix A | Review of Necessary Mathematics | 511 |
| A.1 | Notation | 511 |
| A.2 | Functions | 513 |
| A.3 | Mathematical Induction | 514 |
| A.4 | Theorems and Lemmas | 521 |
| A.5 | Logarithms | 522 |
| A.6 | Sets | 526 |
| A.7 | Permutations and Combinations | 528 |
| A.8 | Probability | 531 |
| Exercises | 542 | |
| Appendix B | Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms | 549 |
| B.1 | Solving Recurrences Using Induction | 549 |
| B.2 | Solving Recurrences Using the Characteristic Equation | 553 |
| B.3 | Solving Recurrences by Substitution | 571 |
| B.4 | Extending Results for n, a Power of a Positive Constant b, to n in General | 573 |
| B.5 | Proofs of Theorems | 579 |
| Exercises | 582 | |
| Appendix C | Data Structures for Disjoint Sets | 589 |
| References | 599 | |
| Index | 605 |
Customer Reviews
Average Review: