Algorithms. A Top-Down Approach

✍ Scribed by RODNEY R HOWELL

• Publisher: World Scientific Publishing
• Year: 2023
• Tongue: English
• Leaves: 611
• Category: Library

✦ Table of Contents

Contents
Preface
About the Author
List of Symbols
I Fundamentals
1. Introduction
1.1 Specifications
1.2 Algorithms
1.3 Proving Algorithm Correctness
1.4 Algorithm Analysis
1.5 Data Structures
1.6 A Case Study: Maximum Subsequence Sum
1.7 Summary
1.8 Exercises
1.9 Notes
2. Proving Algorithm Correctness
2.1 The Basics
2.2 Handling Recursion
2.3 Handling Iteration
2.4 Combining Recursion and Iteration
2.5 Mutual Recursion
2.6 Finding Errors
2.7 Summary
2.8 Exercises
2.9 Notes
3. Analyzing Algorithms
3.1 Motivation
3.2 Big-O Notation
3.3 Big-Ω and Big-Θ
3.4 Operations on Sets
3.5 Smooth Functions and Summations
3.6 Analyzing While Loops
3.7 Analyzing Recursion
3.8 Analyzing Space Usage
3.9 Multiple Variables
3.10 Little-o and Little-ω
3.11 * Use of Limits in Asymptotic Analysis
3.12 Summary
3.13 Exercises
3.14 Notes
II Data Structures
4. Basic Techniques for Data Structures
4.1 Stacks
4.2 A Simple Stack Implementation
4.3 Expandable Arrays
4.4 The CONSLIST ADT
4.5 Amortized Analysis Using Potential Functions
4.6 Summary
4.7 Exercises
4.8 Notes
5. Priority Queues
5.1 Sorted Arrays
5.2 Heaps
5.3 Leftist Heaps
5.4 Skew Heaps
5.5 Randomized Heaps
5.6 Sorting and Binary Heaps
5.7 Summary
5.8 Exercises
5.9 Notes
6. Storage/Retrieval I: Ordered Keys
6.1 Binary Search Trees
6.2 AVL Trees
6.3 Splay Trees
6.4 Skip Lists
6.5 Summary
6.6 Exercises
6.7 Notes
7. Storage/Retrieval II: Unordered Keys
7.1 Arrays with Virtual Initialization
7.2 Hashing
7.3 Deterministic Hash Functions
7.4 Universal Hashing
7.5 Number Theoretic Universal Hash Families
7.6 Perfect Hashing
7.7 Summary
7.8 Exercises
7.9 Notes
8. Disjoint Sets
8.1 Using DISJOINTSETS in Scheduling
8.2 A Tree-Based Implementation
8.3 A Short Tree Implementation
8.4 * Path Compression
8.5 Summary
8.6 Exercises
8.7 Notes
9. Graphs
9.1 Universal Sink Detection
9.2 Topological Sort
9.3 Adjacency Matrix Implementation
9.4 Adjacency List Implementation
9.5 Multigraphs
9.6 Summary
9.7 Exercises
9.8 Notes
III Algorithm Design Techniques
10. Divide and Conquer
10.1 Polynomial Multiplication
10.2 Merge Sort
10.3 Quick Sort
10.4 Selection
10.5 Integer Division
10.6 * Newton’s Method
10.7 Summary
10.8 Exercises
10.9 Notes
11. Optimization I: Greedy Algorithms
11.1 Job Scheduling
11.2 Minimum-Cost Spanning Trees
11.3 Single-Source Shortest Paths
11.4 Huffman Codes
11.5 Summary
11.6 Exercises
11.7 Notes
12. Optimization II: Dynamic Programming
12.1 Making Change
12.2 Chained Matrix Multiplication
12.3 All-Pairs Shortest Paths
12.4 The Knapsack Problem
12.5 Summary
12.6 Exercises
12.7 Notes
IV Common Reduction Targets
13. Depth-First Search
13.1 Ancestry in Rooted Trees
13.2 Reachability in a Graph
13.3 A Generic Depth-First Search
13.4 Articulation Points
13.5 Topological Sort Revisited
13.6 Strongly Connected Components
13.7 Summary
13.8 Exercises
13.9 Notes
14. Network Flow and Matching
14.1 The Ford–Fulkerson Algorithm
14.2 The Edmonds–Karp Algorithm
14.3 Bipartite Matching
14.4 Summary
14.5 Exercises
14.6 Notes
15. * The Fast Fourier Transform
15.1 Convolutions
15.2 Commutative Rings
15.3 Integer Multiplication
15.4 The Schönhage–Strassen Algorithm
15.5 Summary
15.6 Exercises
15.7 Notes
V Intractable Problems
16. NP-Completeness
16.1 Boolean Satisfiability
16.2 The Set P
16.3 The Set NP
16.4 Restricted Satisfiability Problems
16.5 Vertex Cover and Independent Set
16.6 Three-Dimensional Matching
16.7 Partitioning and Strong NP-Completeness
16.8 Proof of Cook’s Theorem
16.9 Summary
16.10 Exercises
16.11 Notes
17. Approximation Algorithms
17.1 Polynomial Turing Reducibility
17.2 Knapsack
17.3 Bin Packing
17.4 The Traveling Salesperson Problem
17.5 The Maximum Cut and Minimum Cluster Problems
17.6 Summary
17.7 Exercises
17.8 Notes
Bibliography
Index