1. Chapter 0 Preface
1.1. 0.1 Books and Algorithms
1.1.3. Etymology of algorithm
1.2. 0.2 starts with the Fibonacci sequence
1.2.2. programming calculations
1.2.3. exponential algorithm
1.2.4. polynomial algorithm
1.3. 0.3 big 0 symbol
1.3.1. Space-time analysis of algorithms
1.3.2. Growth rate comparison: linear vs. polynomial, exponential, logarithmic, factorial, etc. P8
2. Chapter 1 Arithmetic of Numbers
2.1. 1.1 Basic arithmetic
2.1.2. Multiplication and division
2.2. 1.2 Modulo operation
2.2.1. Modular addition and multiplication
2.2.2. Modulo exponential arithmetic
2.2.3. Euclid's greatest common factor algorithm
2.2.4. An extension of Euclid algorithm
2.3. 1.3 Primeness test
2.3.1. Fermat's little theorem
2.3.2. random generation of prime numbers
2.3.2.1. Lagrange's prime number theorem
2.4. 1.4 Cryptography
2.4.1. Key mechanism: one-time pad and AES
2.5. 1.5 Universal hash table
2.5.2. Hash function family
3. Chapter 2 Divide and Conquer Algorithm
3.2. 2.2 Recursive formula
3.4. 2.4 Find the middle term
3.5. 2.5 Matrix multiplication
3.6. 2.6 Details of Fast Fourier Transform
3.6.1. Another way to express polynomials
3.6.2. Divide and Conquer Implementation of Computational Steps
3.6.4. Details of Fast Fourier Transform
3.6.4.1. Deterministic FTT algorithm
3.6.4.2. Internal mechanism of fast Fourier transform
4. Chapter 3 Decomposition of Figures
4.1. 3.1 Why is it a picture?
4.1.1. Representation of graph
4.2. 3.2 Depth-first search of undirected graphs
4.2.2. depth first search
4.2.3. Connectivity of undirected graphs
4.2.4. preorder and postorder
4.3. 3.3 Depth-first search of directed graphs
4.3.2. directed acyclic graph
4.4. 3.4 Strongly connected components
4.4.1. Define the connectivity of a directed graph
4.4.2. an efficient algorithm
5. Chapter 4 The path in the picture
5.2. 4.2 Breadth First Search (BFS)
5.2.1. Correctness and efficiency
5.4. 4.4Dijkstra algorithm
5.4.1. An improvement on breadth-first search
5.4.2. another explanation
5.5. 4.5 Implementation of priority queue
5.6. 4.6 Shortest paths in graphs containing negative edges
5.7. 4.7 Shortest path in directed acyclic graph
6. Chapter 5 Greedy Algorithm
6.1. 5.1 Minimum spanning tree
6.1.1. a greedy algorithm
6.1.4. A data structure for detached sets
6.4. 5.4 Collection coverage
7. Chapter 6 Dynamic Programming
7.1. 6.1 Re-examining the shortest path problem of directed acyclic graph
7.2. 6.2 Longest increasing subsequence
7.3. 6.3 Edit distance
7.3.1. A dynamic programming solution
7.4. 6.4 Knapsack problem
7.4.1. Multiple copies of the backpack problem
7.4.2. Single copy backpack problem
7.5. 6.5 Matrix chain multiplication
7.6. 6.6 Shortest path problem
7.6.1. Shortest reliable road strength
7.6.2. shortest path between all vertices
7.6.3. traveling salesman problem
7.7. 6.7 Independent sets in trees
8. Chapter 7 Linear Programming and Reduction
8.1. 7.1 Introduction to Linear Programming
8.1.1. Example: profit maximization
8.1.2. Example: Production planning
8.1.3. Example: Optimal bandwidth allocation
8.1.4. Variations of Linear Programming
8.2. 7.2 Network flow
8.2.1. Oil transportation
8.2.3. An in-depth look at algorithms
8.2.4. Guarantee of optimality
8.2.4.1. Minimum Partition Maximum Flow Theorem
8.2.5. Algorithm efficiency
8.3. 7.3 Matching of bipartite graphs
8.5. 7.5 Zero-sum game (game)
8.6. 7.6 Simplex Algorithm
8.6.1. Vertices and neighbors in n-dimensional space
8.6.4. Running time of pure algorithm
8.6.4.1. Gaussian elimination method
8.7. 7.7 Postscript: Circuit Values
9. Chapter 8 NP-complete problem
9.1. Search questions
9.1.1. satisfiability problem
9.1.2. traveling salesman problem
9.1.5. integer linear programming
9.1.7. Independent sets, vertex covers and cliques
9.1.8. longest path problem
9.1.9. Knapsack problem and subsets
9.2. NP-complete problem
9.2.1. Hard questions and easy questions
9.2.3. Another discussion on regulations
9.3. All regulations
9.3.1. Rudrata(s,t)-path->Rudrata loop
9.3.2. 3SAT->Independent set
9.3.4. Independent Set->Vertex Cover
9.3.5. Independent set -> clique problem
9.3.6. 3SAT->3D questions
9.3.8. ZOE->Sum of subsets
9.3.10. ZOE->Rudrata loop
9.3.11. Rudrata Loop->TSP
9.3.12. Any NP problem->SAT
10. Chapter 9 Treatment of NP-Complete Problems
10.1. 9.1 Intelligent exhaustive search
10.2. 9.2 Approximation Algorithms
10.2.2. clustering
10.2.2.1. k-clustering (k-CLUSTERING)
10.2.5. level of approximation
10.3. 9.3 Heuristic methods in local search
10.3.1. Revisiting the traveling salesman problem
10.3.2. Graph partitioning
10.3.3. Dealing with local optima
10.3.3.1. Randomize and restart
10.3.3.2. simulated annealing
11. Chapter 10 Quantum Algorithms
11.1. 10.1 Qubits, superposition states and metrics
11.2. 10.2 Algorithm design
11.3. 10.3 Quantum Fourier Transform
11.5. 10.5 Quantum circuits
11.5.1. Basic quantum gate
11.5.2. Two basic types of quantum circuits
11.5.3. Quantum Fourier Transform Circuit
11.6. 10.6 Transform the factorization problem into a periodic solution problem
11.7. 10.7 Quantum Algorithms for Factorization
Wondershare EdrawMind
