Foundations of algorithms using Java pseudocode / Richard Neapolitan, Kumarss Naimipour.

Format:

Book

Author/Creator:

Neapolitan, Richard E.

Contributor:

Naimipour, Kumarss.

Anne and Joseph Trachtman Memorial Book Fund.

Language:

English

Subjects (All):

Algorithms.

Computational complexity.

Physical Description:

xv, 618 pages : illustrations ; 24 cm

Place of Publication:

Sudbury, Mass. : Jones and Bartlett Publishers, 2004.

Summary:

Foundations of Algorithms Using Java Pseudocode offers a well-balanced presentation on designing algorithms, 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 provided in three appendices. The authors also reinforce the explanations with numerous concrete examples to help students grasp theoretical concepts.

Contents:

Chapter 1 Algorithms: Efficiency, Analysis, and Order 1

1.2 The Importance of Developing Efficient Algorithms 9

1.3 Analysis of Algorithms 17

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

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

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

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

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

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

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

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

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

Chapter 11 Introduction to Parallel Algorithms 485

11.1 Parallel Architectures 488

11.2 The PRAM Model 495

Appendix A Review of Necessary Mathematics 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

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

Appendix C Data Structures for Disjoint Sets 589.

Notes:

Includes bibliographical references (pages [599]-603) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Anne and Joseph Trachtman Memorial Book Fund.

ISBN:

0763721298

OCLC:

53138748