Foundations of Algorithms Using C++ Pseudocode

by Neapolitan, Richard

• ISBN13: 9780763723873
• ISBN10: 0763723878
• Edition: 3rd
• Format: Hardcover
• Copyright: 2003-11-01
• Publisher: Jones & Bartlett

Summary

Foundations of Algorithms Using C++ Pseudocode, Third Edition  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 presented in three appendices. The authors also reinforce the explanations with numerous concrete examples to help students grasp theoretical concepts. After Foundations of Algorithms using C++ Pseudocode, Third Edition introduces students to algorithms and analysis of algorithms in Chapter 1, The authors have developed separate chapters on the divide-and-conquer approach, dynamic programming, greedy algorithms, backtracking algorithms, and branch-and-bound algorithms. Immediately after, The author's explore analysis of problems, and in particular, a chapter on analyzing the sorting problem followed by one on analyzing the searching problem. Following this progression, The authors introduce the theory of NP in a rigorous but yet intuitive, lucid fashion. it is at this point that the book then takes a shift in pedagogy and presents a chapter that is concerned with solving a certain type of problem rather than algorithms that share a common technique. Specifically, numerical algorithms are discussed, As well as the inclusion of the new polynomial-time algorithm for determining whether a number is prime. Finally, The authors provide a final chapter concerning parallel algorithms and applications to cryptography.

Table of Contents

Algorithms: Efficiency, Analysis, and Order	1	(46)
Algorithms	2	(7)
The Importance of Developing Efficient Algorithms	9	(8)
Sequential Search Versus Binary Search	9	(3)
The Fibonacci Sequence	12	(5)
Analysis of Algorithms	17	(8)
Complexity Analysis	17	(7)
Applying the Theory	24	(1)
Analysis of Correctness	24	(1)
Order	25	(16)
An Intuitive Introduction to Order	25	(2)
A Rigorous Introduction to Order	27	(12)
Using a Limit to Determine Order	39	(2)
Outline of This Book	41	(6)
Exercises	42	(5)
Divide-and-Conquer	47	(44)
Binary Search	48	(5)
Mergesort	53	(6)
The Divide-and-Conquer Approach	59	(1)
Quicksort (Partition Exchange Sort)	60	(7)
Strassen's Matrix Multiplication Algorithm	67	(5)
Arithmetic with Large Numbers	72	(6)
Representation of Large Integers: Addition and Other Linear-Time Operations	72	(1)
Multiplication of Large Integers	72	(6)
Determining Thresholds	78	(4)
When Not to Use Divide-and-Conquer	82	(9)
Exercises	83	(8)
Dynamic Programming	91	(46)
The Binomial Coefficient	92	(5)
Floyd's Algorithm for Shortest Paths	97	(8)
Dynamic Programming and Optimization Problems	105	(2)
Chained Matrix Multiplication	107	(9)
Optimal Binary Search Trees	116	(9)
The Traveling Salesperson Problem	125	(12)
Exercises	133	(4)
The Greedy Approach	137	(50)
Minimum Spanning Trees	140	(16)
Prim's Algorithm	144	(6)
Kruskal's Algorithm	150	(5)
Comparing Prim's Algorithm with Kruskal's Algorithm	155	(1)
Final Discussion	155	(1)
Dijkstra's Algorithm for Single-Source Shortest Paths	156	(3)
Scheduling	159	(10)
Minimizing Total Time in the System	160	(2)
Scheduling with Deadlines	162	(7)
Huffman Code	169	(6)
Prefix Codes	170	(1)
Huffman's Algorithm	171	(4)
The Greedy Approach Versus Dynamic Programming: The Knapsack Problem	175	(12)
A Greedy Approach to the 0-1 Knapsack Problem	175	(2)
A Greedy Approach to the Fractional Knapsack Problem	177	(1)
A Dynamic Programming Approach to the 0-1 Knapsack Problem	177	(1)
A Refinement of the Dynamic Programming Algorithm for the 0-1 Knapsack Problem	178	(3)
Exercises	181	(6)
Backtracking	187	(46)
The Backtracking Technique	188	(8)
The n-Queens Problem	196	(4)
Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm	200	(4)
The Sum-of-Subsets Problem	204	(5)
Graph Coloring	209	(5)
The Hamiltonian Circuits Problem	214	(3)
The 0-1 Knapsack Problem	217	(16)
A Backtracking Algorithm for the 0-1 Knapsack Problem	217	(10)
Comparing the Dynamic Programming Algorithm and the Backtracking Algorithm for the 0-1 Knapsack Problem	227	(1)
Exercises	227	(6)
Branch-and-Bound	233	(34)
Illustrating Branch-and-Bound with the 0-1 Knapsack Problem	235	(11)
Breadth-First Search with Branch-and-Bound Pruning	235	(6)
Best-First Search with Branch-and-Bound Pruning	241	(5)
The Traveling Salesperson Problem	246	(9)
Abductive Inference (Diagnosis)	255	(12)
Exercises	264	(3)
Introduction to Computational Complexity: The Sorting Problem	267	(52)
Computational Complexity	268	(2)
Insertion Sort and Selection Sort	270	(5)
Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison	275	(2)
Mergesort Revisited	277	(6)
Quicksort Revisited	283	(2)
Heapsort	285	(11)
Heaps and Basic Heap Routines	285	(4)
An Implementation of Heapsort	289	(7)
Comparison of Mergesort, Quicksort, and Heapsort	296	(1)
Lower Bounds for Sorting Only by Comparison of Keys	297	(11)
Decision Trees for Sorting Algorithms	297	(3)
Lower Bounds for Worst-Case Behavior	300	(3)
Lower Bounds for Average-Case Behavior	303	(5)
Sorting by Distribution (Radix Sort)	308	(11)
Exercises	312	(7)
More Computational Complexity: The Searching Problem	319	(56)
Lower Bounds for Searching Only by Comparisons of Keys	320	(10)
Lower Bounds for Worst-Case Behavior	322	(2)
Lower Bounds for Average-Case Behavior	324	(6)
Interpolation Search	330	(3)
Searching in Trees	333	(6)
Binary Search Trees	334	(4)
B-Trees	338	(1)
Hashing	339	(5)
The Selection Problem: Introduction to Adversary Arguments	344	(31)
Finding the Largest Key	345	(1)
Finding Both the Smallest and Largest Keys	346	(7)
Finding the Second-Largest Key	353	(5)
Finding the kth-Smallest Key	358	(8)
A Probabilistic Algorithm for the Selection Problem	366	(4)
Exercises	370	(5)
Computational Complexity and Intractability: An Introduction to the Theory of NP	375	(44)
Intractability	376	(2)
Input Size Revisited	378	(4)
The Three General Problems	382	(2)
Problems for Which Polynomial-Time Algorithms Have Been Found	382	(1)
Problems That Have Been Proven to Be Intractable	382	(1)
Problems That Have Not Been Proven to Be Intractable but for Which Polynomial-Time Algorithms Have Never Been Found	383	(1)
The Theory of NP	384	(22)
The Sets P and NP	386	(4)
NP-Complete Problems	390	(12)
NP-Hard, NP-Easy, and NP-Equivalent Problems	402	(4)
Handling NP-Hard Problems	406	(13)
An Approximation Algorithm for the Traveling Salesperson Problem	407	(4)
An Approximation Algorithm for the Bin-Packing Problem	411	(5)
Exercises	416	(3)
Number-Theoretic Algorithms	419	(66)
Number Theory Review	420	(7)
Composite and Prime Numbers	420	(1)
Greatest Common Divisor	421	(3)
Prime Factorization	424	(3)
Least Common Multiple	427	(1)
Computing the Greatest Common Divisor	427	(7)
Euclid's Algorithm	428	(4)
An Extension to Euclid's Algorithm	432	(2)
Modular Arithmetic Review	434	(14)
Group Theory	434	(2)
Congruency Modulo n	436	(6)
Subgroups	442	(6)
Solving Modular Linear Equations	448	(6)
Computing Modular Powers	454	(2)
Finding Large Prime Numbers	456	(20)
Searching for a Large Prime	457	(1)
Checking if a Number Is Prime	458	(18)
The RSA Public-Key Cryptosystem	476	(9)
Public-Key Cryptosystems	476	(1)
The RSA Cryptosystem	477	(3)
Exercises	480	(5)
Introduction to Parallel Algorithms	485	(26)
Parallel Architectures	488	(7)
Control Mechanism	488	(2)
Address-Space Organization	490	(1)
Interconnection Networks	491	(4)
The PRAM Model	495	(16)
Designing Algorithms for the CREW PRAM Model	497	(8)
Designing Algorithms for the CRCW PRAM Model	505	(3)
Exercises	508	(3)
Appendix A Review of Necessary Mathematics	511	(38)
A.1 Notation	511	(2)
A.2 Functions	513	(1)
A.3 Mathematical Induction	514	(7)
A.4 Theorems and Lemmas	521	(1)
A.5 Logarithms	522	(4)
A.5.1 Definition and Properties of Logarithms	522	(2)
A.5.2 The Natural Logarithm	524	(2)
A.6 Sets	526	(2)
A.7 Permutations and Combinations	528	(3)
A.8 Probability	531	(18)
A.8.1 Randomness	536	(4)
A.8.2 The Expected Value	540	(2)
Exercises	542	(7)
Appendix B Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms	549	(40)
B.1 Solving Recurrences Using Induction	549	(4)
B.2 Solving Recurrences Using the Characteristic Equation	553	(18)
B.2.1 Homogeneous Linear Recurrences	553	(9)
B.2.2 Nonhomogeneous Linear Recurrences	562	(6)
B.2.3 Change of Variables (Domain Transformations)	568	(3)
B.3 Solving Recurrences by Substitution	571	(2)
B.4 Extending Results for n, a Power of a Positive Constant b, to n in General	573	(6)
B.5 Proofs of Theorems	579	(10)
Exercises	582	(7)
Appendix C Data Structures for Disjoint Sets	589	(10)
References	599	(6)
Index	605