Foundations of Algorithms Using Java Pseudocode / Edition 1

Foundations of Algorithms Using Java Pseudocode / Edition 1

by Richard Neapolitan
     
 

View All Available Formats & Editions

ISBN-10: 0763721298

ISBN-13: 2900763721298

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

Overview

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.

Product Details

ISBN-13:
2900763721298
Publisher:
Jones & Bartlett Learning
Publication date:
02/13/2004
Edition description:
1E
Pages:
544

Table of Contents

Prefacev
Chapter 1Algorithms: Efficiency, Analysis, and Order1
1.1Algorithms2
1.2The Importance of Developing Efficient Algorithms9
1.3Analysis of Algorithms17
1.4Order25
1.5Outline of This Book41
Exercises42
Chapter 2Divide-and-Conquer47
2.1Binary Search48
2.2Mergesort53
2.3The Divide-and-Conquer Approach59
2.4Quicksort (Partition Exchange Sort)60
2.5Strassen's Matrix Multiplication Algorithm67
2.6Arithmetic with Large Integers72
2.7Determining Thresholds78
2.8When Not to Use Divide-and-Conquer82
Exercises83
Chapter 3Dynamic Programming91
3.1The Binomial Coefficient92
3.2Floyd's Algorithm for Shortest Paths97
3.3Dynamic Programming and Optimization Problems105
3.4Chained Matrix Multiplication107
3.5Optimal Binary Search Trees116
3.6The Traveling Salesperson Problem125
Exercises133
Chapter 4The Greedy Approach137
4.1Minimum Spanning Trees140
4.2Dijkstra's Algorithm for Single-Source Shortest Paths156
4.3Scheduling159
4.4Huffman Code169
4.5The Greedy Approach versus Dynamic Programming: The Knapsack Problem175
Exercises181
Chapter 5Backtracking187
5.1The Backtracking Technique188
5.2The n-Queens Problem196
5.3Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm200
5.4The Sum-of-Subsets Problem204
5.5Graph Coloring209
5.6The Hamiltonian Circuits Problem214
5.7The 0-1 Knapsack Problem217
Exercises227
Chapter 6Branch-and-Bound233
6.1Illustrating Branch-and-Bound with the 0-1 Knapsack Problem235
6.2The Traveling Salesperson Problem246
6.3Abductive Inference (Diagnosis)255
Exercises264
Chapter 7Introduction to Computational Complexity: The Sorting Problem267
7.1Computational Complexity268
7.2Insertion Sort and Selection Sort270
7.3Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison275
7.4Mergesort Revisited277
7.5Quicksort Revisited283
7.6Heapsort285
7.7Comparison of Mergesort, Quicksort, and Heapsort296
7.8Lower Bounds for Sorting Only by Comparison of Keys297
7.9Sorting by Distribution (Radix Sort)308
Exercises312
Chapter 8More Computational Complexity: The Searching Problem319
8.1Lower Bounds for Searching Only by Comparisons of Keys320
8.2Interpolation Search330
8.3Searching in Trees333
8.4Hashing339
8.5The Selection Problem: Introduction to Adversary Arguments344
Exercises370
Chapter 9Computational Complexity and Intractability: An Introduction to the Theory of NP375
9.1Intractability376
9.2Input Size Revisited378
9.3The Three General Problems382
9.4The Theory of NP384
9.5Handling NP-Hard Problems406
Exercises416
Chapter 10Number-Theoretic Algorithms419
10.1Number Theory Review420
10.2Computing the Greatest Common Divisor427
10.3Modular Arithmetic Review434
10.4Solving Modular Linear Equations448
10.5Computing Modular Powers454
10.6Finding Large Prime Numbers456
10.7The RSA Public-Key Cryptosystem476
Exercises480
Chapter 11Introduction to Parallel Algorithms485
11.1Parallel Architectures488
11.2The PRAM Model495
Exercises508
Appendix AReview of Necessary Mathematics511
A.1Notation511
A.2Functions513
A.3Mathematical Induction514
A.4Theorems and Lemmas521
A.5Logarithms522
A.6Sets526
A.7Permutations and Combinations528
A.8Probability531
Exercises542
Appendix BSolving Recurrence Equations: With Applications to Analysis of Recursive Algorithms549
B.1Solving Recurrences Using Induction549
B.2Solving Recurrences Using the Characteristic Equation553
B.3Solving Recurrences by Substitution571
B.4Extending Results for n, a Power of a Positive Constant b, to n in General573
B.5Proofs of Theorems579
Exercises582
Appendix CData Structures for Disjoint Sets589
References599
Index605

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >