Algorithms

Contents
Introduction . . . . . . . . . . . . . . . . . . . . . .
Algorithms, Outline of Topics
1. Preview. . . . . . . . . . . . . . . . . . . . . . .
Pascal, Euclid’s Algorithm, Recursion, Analysis of Algorithms
Implementing Algorithms
MATHEMATICAL ALGORITHMS
2. Arithmetic . . . . . . . . . . . . . . . . . . . . .
Polynomials, Matrices, Data Structures
3. Random Numbers . . . . . . . . . . . . . . . . . . .
Applications, Linear Congruential Method, Additive
Congruential Method, Testing Randomness, Implementation Notes
4. Polynomials . . . . . . . . . . . . . . . . . . . . . .
Evaluation, Interpolation, Multiplication, Divide-and-conquer
Recurrences, Matriz Multiplication
5. Gaussian Elimination . . . . . . . . . . . . . . . . . .
A Simple Example, Outline of the Method, Variations and Extensions
6. Curve Fitting . . . . . . . . . . . . . . . . . . . . .
Polynomaal Interpolation, Spline Interpolation, Method of Least Squares
7. Integration . . . . . . . . . . . . . . . . . . . . . .
Symbolac Integration, Simple Quadrature Methods, Compound Methods,
Adaptive Quadrature
SORTING
8. Elementary Sorting Methods . . . . . . . . . . . . . .
Rules of the Game, Selection Sort, Insertion Sort, Shellsort,
Bubble Sort, Distribution Counting, Non-Random Files
9. Quicksort . . . . . . . . . . . . . . , , . , . . . . .
The Baszc Algorithm, Removing Recursion, Small Subfiles,
Median-of- Three Partitioning
10. Radix Sorting . . . . . . . . . . . , . . . . . . . . .
Radiz Ezchange Sort, Straight Radix Sort, A Linear Sort
11. Priority Queues . . . . . . . . . . . . . . . . . . . .
Elementary Implementations, Heap Data Structure, Algorithms
on Heaps, Heapsort, Indirect Heaps, Advanced Implementations
12. Selection and Merging . . . . . . . . . . . . . . . . .
Selection, Mergang, Recursion Revisited
13. External Sorting . . . . . . . . . . . . . . . . . . . .
Sort-Merge, Balanced Multiway Merging, Replacement Selectzon,
Practical Considerations, Polyphase Merging, An Easier Way
SEARCHING
14. Elementary Searching Methods . . . . . . . . . . . . . . . . 171
Sequential Searching, Sequential List Searchang, Binary Search,
Binary ‘Pree Search, Indirect Binary Search Trees
15. Balanced Trees . . . . . . . . . . . . . . . . . . . . . . 187
Top-Down 2-9-4 Trees, Red-Black Trees, Other Algorithms
16. Hashing . . . . . . . . . . . . . . . . . , . . . . . . . 201
Hash Functions, Separate Chaining, Open Addresszng, Analytic Results
17. Radix Searching . . . . . . . . . . . . . . . . . . . . . . 213
Digital Search Trees, Radix Search Wes, M&iway Radar Searching,
Patricia
18. External Searching . . . . . . . . ,, . . . . . . . . . . . . . 225
Indexed Sequential Access, B- nees, Extendible Hashing, Virtual Memory
STRING PROCESSING
19. String Searching . . . . . . . . . . . . . . . . . . . . . . 241
A Short History, Brute-Force Algorithm, Knuth-Morris-Pratt Algorzthm,
Bayer-Moore Algorithm, Rabin-Karp Algorithm, Multiple Searches
20. Pattern Matching . . . . . . . . . . . . . . . . . . . . . 257
Describing Patterns, Pattern Matching Machznes, Representzng
the Machine, Simulating the Machine
21. Parsing , . . . . . . . . . . . . . . . . . . . . . . . . . 269
Conteti-Free Grammars, Top-Down Parsing, Bottom-Up Parsing,
Compilers, Compiler-Compilers
22. File Compression . . . . . . . . . . . . . . . . . . . . . . 283
Run-Length Encoding, Variable-Length Encoding
23. Cryptology . . . . . . . . . . . . . . . . . . . . . . . . . 295
Rules of the Game, Simple Methods, Encrypt:!on/Decryption
Machines, Publzc-Key Cryptosystems
GEOMETRIC ALGORITHMS
24. Elementary Geometric Methods . . . . . . . . . . . . . . . . 307
Poznts, Lines, and Polygons, Line Intersection, Simple
Closed Path, Inclusaon in 4 Polygon, Perspective
25. Finding the Convex Hull . . . . . . . . . . . . . . . . . . . 321
Rules of the Game, Package Wrapping, The Graham Scan,
Hull Selection, Performance Issues
26. Range Searching . . . . . . . . . . . . . . . . . . . . . . . 335
Elementary Methods, Grad Method, 2D Trees,
Multidimensaonal Range Searching
27. Geometric Intersection . , . . . . . . . . . . . . . . . . . . 349
Horizontal and Vertical Lines, General Line Intersection
28. Closest Point Problems . . . . . . . . . . . . . . . . . . . 361
Closest Paar, Voronoi Diagrams
GRAPH ALGORITHMS
29. Elementary Graph Algorithms . . . . . . . . . . . . . . .
Glossary, Representation, Depth-First Search, Mazes, Perspectzve
30. Connectivity . . . . . . . . . . . . . . . . . . . . .
Biconnectivity, Graph Traversal Algorzthms, Union-Find Algorithms
31. Weighted Graphs . . . . . . . . . . . . . . . . . . .
Mmimum Spanning Tree, Shortest Path, Dense Graphs, Geometrzc Problems
32. Directed Graphs . . . . . . . . . . . . . . . . . . . .
Depth-Farst Search, Transitwe Closure, Topological Sorting,
Strongly Connected Components
33. Network Flow . . . . . . . . . . . . . . . . . . .
The Network Flow Problem, Ford-Adkerson Method, Network Searching
34. Matching . . . . . . . . . . . . . . . . . . , . . . . .
Bapartite Graphs, Stable Marriage Problem, Advanced Algorathms
ADVANCED TOPICS
35. Algorithm Machines . . . . . . . . . . . . . . . . . . .
General Approaches> Perfect ShujIes, Systolic Arrays
36. The Fast Fourier Transform . . . . . . . . . . . . . . .
Evaluate, Multiply, Interpolate, Complez Roots of Unity, Evaluation
at the Roots of Unity, Interpolatzon at the Roots of Unity, Implementation
37. Dynamic Programming . . . . . . . . . . . . . . . . . .
Knapsack Problem, Matriz Chain Product, Optimal Binary Search Trees,
Shortest Paths, Time and Space Requirements
38. Linear Programming . . . . . . . . . . . . . . . . . .
Lznear Programs, Geometric Interpretation, The Simplex Method,
Implementation
39. Exhaustive Search . . . . . . . . . . . . . . . . . . .
Exhaustive Search in Graphs, Backtrackzng, Permutation Generation,
Approximation Algorithms
40. NP-complete Problems . . . . . . . . . . . http://www.blogger.com/img/blank.gif . . . . .http://www.blogger.com/img/blank.gif
Deterministic and Nondeterministic Polynomial- Time Algorzthms,http://www.blogger.com/img/blank.gif
NP-Completeness, Cook’s Theorem, Some NP-Complete Problems

Another Algorithm Books
Another The Core of CS Books
Download