Repository for functions mentioned in this book
- Preface
- I Foundations
- Introduction
- 1 The Role of Algorithms in Computing
- 1.1 Algorithms
- 1.2 Algorithms as a technology
- 2 Getting Started
- 2.1 Insertion sort
- 2.2 Analyzing algorithms
- 2.3 Designing algorithms
- 3 Characterizing Running Times
- 3.1 O-notation, Ω-notation, and Θ-notation
- 3.2 Asymptotic notation: formal definitions
- 3.3 Standard notations and common functions
- 4 Divide-and-Conquer
- 4.1 Multiplying square matrices
- 4.2 Strassen’s algorithm for matrix multiplication
- 4.3 The substitution method for solving recurrences
- 4.4 The recursion-tree method for solving recurrences
- 4.5 The master method for solving recurrences
- 4.6 Proof of the continuous master theorem
- 4.7 Akra-Bazzi recurrences
- 5 Probabilistic Analysis and Randomized Algorithms
- 5.1 The hiring problem
- 5.2 Indicator random variables
- 5.3 Randomized algorithms
- 5.4 Probabilistic analysis and further uses of indicator random variables
- II Sorting and Order Statistics
- Introduction
- 6 Heapsort
- 6.1 Heaps
- 6.2 Maintaining the heap property
- 6.3 Building a heap
- 6.4 The heapsort algorithm
- 6.5 Priority queues
- 7 Quicksort
- 7.1 Description of quicksort
- 7.2 Performance of quicksort
- 7.3 A randomized version of quicksort
- 7.4 Analysis of quicksort
- 8 Sorting in Linear Time
- 8.1 Lower bounds for sorting
- 8.2 Counting sort
- 8.3 Radix sort
- 8.4 Bucket sort
- 9 Medians and Order Statistics
- 9.1 Minimum and maximum
- 9.2 Selection in expected linear time
- 9.3 Selection in worst-case linear time
- III Data Structures
- Introduction
- 10 Elementary Data Structures
- 10.1 Simple array-based data structures: arrays, matrices, stacks, queues
- 10.2 Linked lists
- 10.3 Representing rooted trees
- 11 Hash Tables
- 11.1 Direct-address tables
- 11.2 Hash tables
- 11.3 Hash functions
- 11.4 Open addressing
- 11.5 Practical considerations
- 12 Binary Search Trees
- 12.1 What is a binary search tree?
- 12.2 Querying a binary search tree
- 12.3 Insertion and deletion
- 13 Red-Black Trees
- 13.1 Properties of red-black trees
- 13.2 Rotations
- 13.3 Insertion
- 13.4 Deletion
- IV Advanced Design and Analysis Techniques
- Introduction
- 14 Dynamic Programming
- 14.1 Rod cutting
- 14.2 Matrix-chain multiplication
- 14.3 Elements of dynamic programming
- 14.4 Longest common subsequence
- 14.5 Optimal binary search trees
- 15 Greedy Algorithms
- 15.1 An activity-selection problem
- 15.2 Elements of the greedy strategy
- 15.3 Huffman codes
- 15.4 Offline caching
- 16 Amortized Analysis
- 16.1 Aggregate analysis
- 16.2 The accounting method
- 16.3 The potential method
- 16.4 Dynamic tables
- V Advanced Data Structures
- Introduction
- 17 Augmenting Data Structures
- 17.1 Dynamic order statistics
- 17.2 How to augment a data structure
- 17.3 Interval trees
- 18 B-Trees
- 18.1 Definition of B-trees
- 18.2 Basic operations on B-trees
- 18.3 Deleting a key from a B-tree
- 19 Data Structures for Disjoint Sets
- 19.1 Disjoint-set operations
- 19.2 Linked-list representation of disjoint sets
- 19.3 Disjoint-set forests
- 19.4 Analysis of union by rank with path compression
- VI Graph Algorithms
- Introduction
- 20 Elementary Graph Algorithms
- 20.1 Representations of graphs
- 20.2 Breadth-first search
- 20.3 Depth-first search
- 20.4 Topological sort
- 20.5 Strongly connected components
- 21 Minimum Spanning Trees
- 21.1 Growing a minimum spanning tree
- 21.2 The algorithms of Kruskal and Prim
- 22 Single-Source Shortest Paths
- 22.1 The Bellman-Ford algorithm
- 22.2 Single-source shortest paths in directed acyclic graphs
- 22.3 Dijkstra’s algorithm
- 22.4 Difference constraints and shortest paths
- 22.5 Proofs of shortest-paths properties
- 23 All-Pairs Shortest Paths
- 23.1 Shortest paths and matrix multiplication
- 23.2 The Floyd-Warshall algorithm
- 23.3 Johnson’s algorithm for sparse graphs
- 24 Maximum Flow
- 24.1 Flow networks
- 24.2 The Ford-Fulkerson method
- 24.3 Maximum bipartite matching
- 25 Matchings in Bipartite Graphs
- 25.1 Maximum bipartite matching (revisited)
- 25.2 The stable-marriage problem
- 25.3 The Hungarian algorithm for the assignment problem
- VII Selected Topics
- Introduction
- 26 Parallel Algorithms
- 26.1 The basics of fork-join parallelism
- 26.2 Parallel matrix multiplication
- 26.3 Parallel merge sort
- 27 Online Algorithms
- 27.1 Waiting for an elevator
- 27.2 Maintaining a search list
- 27.3 Online caching
- 28 Matrix Operations
- 28.1 Solving systems of linear equations
- 28.2 Inverting matrices
- 28.3 Symmetric positive-definite matrices and least-squares approximation
- 29 Linear Programming
- 29.1 Linear programming formulations and algorithms
- 29.2 Formulating problems as linear programs
- 29.3 Duality
- 30 Polynomials and the FFT
- 30.1 Representing polynomials
- 30.2 The DFT and FFT
- 30.3 FFT circuits
- 31 Number-Theoretic Algorithms
- 31.1 Elementary number-theoretic notions
- 31.2 Greatest common divisor
- 31.3 Modular arithmetic
- 31.4 Solving modular linear equations
- 31.5 The Chinese remainder theorem
- 31.6 Powers of an element
- 31.7 The RSA public-key cryptosystem
- 31.8 Primality testing
- 32 String Matching
- 32.1 The naive string-matching algorithm
- 32.2 The Rabin-Karp algorithm
- 32.3 String matching with finite automata
- 32.4 The Knuth-Morris-Pratt algorithm
- 32.5 Suffix arrays
- 33 Machine-Learning Algorithms
- 33.1 Clustering
- 33.2 Multiplicative-weights algorithms
- 33.3 Gradient descent
- 34 NP-Completeness
- 34.1 Polynomial time
- 34.2 Polynomial-time verification
- 34.3 NP-completeness and reducibility
- 34.4 NP-completeness proofs
- 34.5 NP-complete problems
- 35 Approximation Algorithms
- 35.1 The vertex-cover problem
- 35.2 The traveling-salesperson problem
- 35.3 The set-covering problem
- 35.4 Randomization and linear programming
- 35.5 The subset-sum problem
- VIII Appendix: Mathematical Background
- Introduction
- A Summations
- A.1 Summation formulas and properties
- A.2 Bounding summations
- B Sets, Etc.
- B.1 Sets
- B.2 Relations
- B.3 Functions
- B.4 Graphs
- B.5 Trees
- Problems
- Appendix notes
- C Counting and Probability
- C.1 Counting
- C.2 Probability
- C.3 Discrete random variables
- C.4 The geometric and binomial distributions
- C.5 The tails of the binomial distribution
- Problems
- Appendix notes
- D Matrices
- D.1 Matrices and matrix operations
- D.2 Basic matrix properties
- Problems
- Appendix notes
- Bibliography
- Index
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent