# Foundations of Algorithms Using Java Pseudocode / Edition 1

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)

## Related Subjects

 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:

Write a Review

and post it to your social network