Mastering Algorithms with C

Preface; Organization; Key Features; About the Code; Conventions; How to Contact Us; Acknowledgments; Part I: Preliminaries; Chapter 1: Introduction; 1.1 An Introduction to Data Structures; 1.2 An Introduction to Algorithms; 1.3 A Bit About Software Engineering; 1.4 How to Use This Book; Chapter 2: Pointer Manipulation; 2.1 Pointer Fundamentals; 2.2 Storage Allocation; 2.3 Aggregates and Pointer Arithmetic; 2.4 Pointers as Parameters to Functions; 2.5 Generic Pointers and Casts; 2.6 Function Pointers; 2.7 Questions and Answers; 2.8 Related Topics; Chapter 3: Recursion; 3.1 Basic Recursion; 3.2 Tail Recursion; 3.3 Questions and Answers; 3.4 Related Topics; Chapter 4: Analysis of Algorithms; 4.1 Worst-Case Analysis; 4.2 O-Notation; 4.3 Computational Complexity; 4.4 Analysis Example: Insertion Sort; 4.5 Questions and Answers; 4.6 Related Topics; Part II: Data Structures; Chapter 5: Linked Lists; 5.1 Description of Linked Lists; 5.2 Interface for Linked Lists; 5.3 Implementation and Analysis of Linked Lists; 5.4 Linked List Example: Frame Management; 5.5 Description of Doubly-Linked Lists; 5.6 Interface for Doubly-Linked Lists; 5.7 Implementation and Analysis of Doubly Linked Lists; 5.8 Description of Circular Lists; 5.9 Interface for Circular Lists; 5.10 Implementation and Analysis of Circular Lists; 5.11 Circular List Example: Second-Chance Page Replacement; 5.12 Questions and Answers; 5.13 Related Topics; Chapter 6: Stacks and Queues; 6.1 Description of Stacks; 6.2 Interface for Stacks; 6.3 Implementation and Analysis of Stacks; 6.4 Description of Queues; 6.5 Interface for Queues; 6.6 Implementation and Analysis of Queues; 6.7 Queue Example: Event Handling; 6.8 Questions and Answers; 6.9 Related Topics; Chapter 7: Sets; 7.1 Description of Sets; 7.2 Interface for Sets; 7.3 Implementation and Analysis of Sets; 7.4 Set Example: Set Covering; 7.5 Questions and Answers; 7.6 Related Topics; Chapter 8: Hash Tables; 8.1 Description of Chained Hash Tables; 8.2 Interface for Chained Hash Tables; 8.3 Implementation and Analysis of Chained Hash Tables; 8.4 Chained Hash Table Example: Symbol Tables; 8.5 Description of Open-Addressed Hash Tables; 8.6 Interface for Open-Addressed Hash Tables; 8.7 Implementation and Analysisof Open Addressed Hash Tables; 8.8 Questions and Answers; 8.9 Related Topics; Chapter 9: Trees; 9.1 Description of Binary Trees; 9.2 Interface for Binary Trees; 9.3 Implementation and Analysis of Binary Trees; 9.4 Binary Tree Example: Expression Processing; 9.5 Description of Binary Search Trees; 9.6 Interface for Binary Search Trees; 9.7 Implementation and Analysis of Binary Search Trees; 9.8 Questions and Answers; 9.9 Related Topics; Chapter 10: Heaps and Priority Queues; 10.1 Description of Heaps; 10.2 Interface for Heaps; 10.3 Implementation and Analysis of Heaps; 10.4 Description of Priority Queues; 10.5 Interface for Priority Queues; 10.6 Implementation and Analysis of Priority Queues; 10.7 Priority Queue Example: Parcel Sorting; 10.8 Questions and Answers; 10.9 Related Topics; Chapter 11: Graphs; 11.1 Description of Graphs; 11.2 Interface for Graphs; 11.3 Implementation and Analysis of Graphs; 11.4 Graph Example: Counting Network Hops; 11.5 Graph Example: Topological Sorting; 11.6 Questions and Answers; 11.7 Related Topics; Part III: Algorithms; Chapter 12: Sorting and Searching; 12.1 Description of Insertion Sort; 12.2 Interface for Insertion Sort; 12.3 Implementation and Analysis of Insertion Sort; 12.4 Description of Quicksort; 12.5 Interface for Quicksort; 12.6 Implementation and Analysis of Quicksort; 12.7 Quicksort Example: Directory Listings; 12.8 Description of Merge Sort; 12.9 Interface for Merge Sort; 12.10 Implementation and Analysis of Merge Sort; 12.11 Description of Counting Sort; 12.12 Interface for Counting Sort; 12.13 Implementation and Analysis of Counting Sort; 12.14 Description of Radix Sort; 12.15 Interface for Radix Sort; 12.16 Implementation and Analysis of Radix Sort; 12.17 Description of Binary Search; 12.18 Interface for Binary Search; 12.19 Implementation and Analysis of Binary Search; 12.20 Binary Search Example: Spell Checking; 12.21 Questions and Answers; 12.22 Related Topics; Chapter 13: Numerical Methods; 13.1 Description of Polynomial Interpolation; 13.2 Interface for Polynomial Interpolation; 13.3 Implementation and Analysis of Polynomial Interpolation; 13.4 Description of Least-Squares Estimation; 13.5 Interface for Least-Squares Estimation; 13.6 Implementation and Analysis of Least-Squuuuuuares Estimation; 13.7 Description of the Solution of Equations; 13.8 Interface for the Solution of Equations; 13.9 Implementation and Analysis of the Solution of Equations; 13.10 Questions and Answers; 13.11 Related Topics; Chapter 14: Data Compression; 14.1 Description of Bit Operations; 14.2 Interface for Bit Operations; 14.3 Implementation and Analysis of Bit Operations; 14.4 Description of Huffman Coding; 14.5 Interface for Huffman Coding; 14.6 Implementation and Analysis of Huffman Coding; 14.7 Huffman Coding Example: Optimized Networking; 14.8 Description of LZ77; 14.9 Interface for LZ77; 14.10 Implementation and Analysis of LZ77; 14.11 Questions and Answers; 14.12 Related Topics; Chapter 15: Data Encryption; 15.1 Description of DES; 15.2 Interface for DES; 15.3 Implementation and Analysis of DES; 15.4 DES Example: Block Cipher Modes; 15.5 Description of RSA; 15.6 Interface for RSA; 15.7 Implementation and Analysis of RSA; 15.8 Questions and Answers; 15.9 Related Topics; Chapter 16: Graph Algorithms; 16.1 Description of Minimum Spanning Trees; 16.2 Interface for Minimum Spanning Trees; 16.3 Implementation and Analysis of Minimum Spanning Trees; 16.4 Description of Shortest Paths; 16.5 Interface for Shortest Paths; 16.6 Implementation and Analysis of Shortest Paths; 16.7 Shortest Paths Example: Routing Tables; 16.8 Description of the Traveling-Salesman Problem; 16.9 Interface for the Traveling-Salesman Problem; 16.10 Implementation and Analysis of the Traveling-Salesman Problem; 16.11 Questions and Answers; 16.12 Related Topics; Chapter 17: Geometric Algorithms; 17.1 Description of Testing Whether Line Segments Intersect; 17.2 Interface for Testing Whether Line Segments Intersect; 17.3 Implementation and Analysis of Testing Whether Line Segments Intersect; 17.4 Description of Convex Hulls; 17.5 Interface for Convex Hulls; 17.6 Implementation and Analysis of Convex Hulls; 17.7 Description of Arc Length on Spherical Surfaces; 17.8 Interface for Arc Length on Spherical Surfaces; 17.9 Implementation and Analysis of Arc Length on Spherical Surfaces; 17.10 Arc Length Example: Approximating Distances on Earth; 17.11 Questions and Answers; 17.12 Related Topics; Colophon;