Algorithms In C++ 3e

The algorithms included here cover a broad range of fundamental and more advanced methods: sorting, searching, string-processing, geometric, graph, and mathematical algorithms. Readers will see how key algorithms can be implemented, run, debugged, and used in real applications--plus why some algorithms are to be preferred over others.
Table of Contents
Fundamentals
1. Introduction Algorithms. Outline of Topics.
2. C++ (and C) Example: Euclid's
Algorithm. Types of Data. Input/Output.
Concluding Remarks.
3. Elementary Data Structures Arrays.
Linked Lists. Storage Allocation. Pushdown
Stacks. Queues. Linked List Implementation
of Stacks. Abstract and Concrete Data Types.
4. Trees Glossary. Properties. Representing Binary Trees. Representing
Forests. Traversing Trees.
5. Recursion Recurrences.
Divide-and-Conquer. Recursive Tree Traversal. Removing Recursion. Perspective.
6. Analysis of Algorithms Framework.
Classification of Algorithms. Computational
Complexity. Average-Case Analysis. Approximate and Asymptotic Results. Basic
Recurrences. Perspective.
7. Implementation of Algorithms Selecting an Algorithm. Empirical Analysis. Program
Optimization. Algorithms and Systems.
Sorting Algorithms
8. Elementary Sorting Methods Rules of the
Game. Selection Sort. Insertion Sort.
Digression: Bubble Sort. Performance
Characteristics of Elementary Sorts. Sorting
Files with Large Records. Shellsort.
Distribution Counting.
9. Quicksort The Basic Algorithm.
Performance Characteristics of Quicksort. Removing Recursion. Small Subfiles.
Median-of-Three Partitioning. Selection.
10. Radix Sorting Bits. Radix Exchange Sort. Straight Radix Sort. Performance
Characteristics of Radix Sorts. A Linear Sort.
11. Priority Queues Elementary
Implementations. Heap Data Structure.
Algorithms on Heaps. Heapsort. Indirect
Heaps. Advanced Implementations.
12. Mergesort Merging. Mergesort. List
Mergesort. Bottom-Up Mergesort. Performance
Characteristics. Optimized Implementations. Recursion Revisited.
13. External Sorting Sort-Merge. Balanced
Multiway Merging. Replacement Selection.
Practical Considerations. Polyphase Merging. An Easier Way.
Searching Algorithms
14. Elementary Searching Methods Sequential Searching. Binary Search. Binary
Tree Search. Deletion. Indirect Binary Search Trees.
15. Balanced Trees Top-Down 2-3-4 Trees. Red-Black Trees. Other Algorithms.
16. Hashing Hash Functions. Separate
Chaining. Linear Probing. Double Hashing. Perspective.
17. Radix Searching Digital Search Trees.
Radix Search Tries. Multiway Radix Searching. Patricia.
18. External Searching Indexed Sequential Access. B-Trees. Extendible Hashing.
Virtual Memory.
String Processing
19. String Searching A Short History. Brute-Force Algorithm. Knuth-Morris-Pratt
Algorithm. Boyer-Moore Algorithm.
Rabin-Karp Algorithm. Multiple Searches.
20. Pattern Matching Describing Patterns.
Pattern Matching Machines. Representing the
Machine. Simulating the Machine.
21. Parsing Context-Free Grammars. Top-Down Parsing. Bottom-Up Parsing.
Compilers. Compiler-Compilers.
22. File Compression Run-Length Encoding.
Variable-Length Encoding. Building the
Huffman Code. Implementation.
23. Cryptology Rules of the Game. Simple
Methods. Encryption/Decryption Machines.
Public-Key Cryptosystems.
Geometric Algorithms
24. Elementary Geometric Methods Points,
Lines, and Polygons. Line Segment
Intersection. Simple Closed Path. Inclusion
in a Polygon. Perspective.
25. Finding the Convex Hull Rules of the Game. Package-Wrapping. The Graham Scan.
Interior Elimination. Performance Issues.
26. Range Searching Elementary Methods.
Grid Method. Two-Dimensional Trees.
Multidimensional Range Searching.
27. Geometric Intersection Horizontal and
Vertical Lines. Implementation. General
Line Intersection.
28. Closest-Point Problems Closest-Pair
Problem. Voronoi Diagrams.
Graph Algorithms
29. Elementary Graph Algorithms Glossary.
Representation. Depth-First Search.
Nonrecursive Depth-First Search.
Breadth-First Search. Mazes. Perspective.
30. Connectivity Connected Components. Biconnectivity. Union-Find Algorithms.
31. Weighted Graphs Minimum Spanning Tree.
Priority-First Search. Kruskal's Method.
Shortest Path. Minimum Spanning Tree and
Shortest Paths in Dense Graphs. Geometric Problems.
32. Directed Graphs Depth-First Search.
Transitive Closure. All Shortest Paths.
Topological Sorting. Strongly Connected
Components.
33. Network Flow The Network Flow Problem.
Ford-Fulkerson Method. Network Searching.
34. Matching Bipartite Graphs. Stable
Marriage Problem. Advanced Algorithms.
Mathematical Algorithms
35. Random Numbers Applications. Linear
Congruential Method. Additive Congruential
Method. Testing Randomness. Implementation Notes.
36. Arithmetic Polynomial Arithmetic.
Polynomial Evaluation and Interpolation.
Polynomial Multiplication. Arithmetic
Operations with Large Integers. Matrix Arithmetic.
37. Gaussian Elimination A Simple Example.
Outline of the Method. Variations and Extensions.
38. Curve Fitting Polynomial
Interpolation. Spline Interpolation. Method
of Least Squares.
39. Integration Symbolic Integration.
Simple Quadrature Methods. Compound Methods. Adaptive Quadrature.
Advanced Topics
40. Parallel Algorithms General Approaches. Perfect Shuffles. Systolic
Arrays. Perspective.
41. The Fast Fourier Transform Evaluate,
Multiply, Interpolate. Complex Roots of Unity. Evaluation at the Roots of Unity.
Interpolation at the Roots of Unity.
Implementation.
42. Dynamic Programming Knapsack Problem.
Matrix Chain Product. Optimal Binary Search Trees. Time and Space Requirements.
43. Linear Programming Linear Programs.
Geometric Interpretation. The Simplex
Method. Implementation.
44. Exhaustive Search Exhaustive Search in
Graphs. Backtracking. Digression: Permutation Generation. Approximation
Algorithms.
45. NP-Complete Problems Deterministic and Nondeterministic Polynomial-Time Algorithms.
NP-Completeness. Cook's Theorem. Some NP-Complete Problems.
Index