#+BEGIN_COMMENT
.. title: Introduction To Algorithms (CLRS)
.. slug: clrs
.. date: 2021-08-12 12:39:58 UTC-07:00
.. tags: bibliography,book,algorithms
.. category: Algorithms
.. link:
.. description:
.. type: text
#+END_COMMENT
* Chapters
** Foundations
*** The Role of Algorithms in Computing
- Algorithms
- Algorithms as a technology
*** Getting Started
- Insertion Sort
- Analyzing algorithms
- Designing algorithms
*** Growth of Functions
- Asymptotic notation
- Standard notations and common functions
*** Divide-and-Conquer
- The maximum-subarray problem
- Strassen's algorithm for matrix multiplication
- The substitution method for solving recurrences
- The recursion-tree method for solving recurrences
- The master method for solving recurrences
- Proof of the master theorem
*** Probabilistic Analysis and Randomization Algorithms
- The hiring problem
- Indicator Random Variables
- Randomized Algorithms
- Probabilistic analysis and further uses of indicator random variables
** Sorting and Order Statistics
*** Heapsort
- Heaps
- Maintaining the heap property
- Building a heap
- The heapsort algorithm
- Priority queues
*** Quicksort
- Description of quicksort
- Performance of quicksort
- A randomized version of quicksort
- Analysis of quicksort
*** Sorting in Linear Time
- Lower bounds for sorting
- Counting sort
- Radix sort
- Bucket sort
*** Medians and Order Statistics
- Minimum and maximum
- Selection in expected linear time
- Selection in worst-case linear time
** Data Structures
*** Elementary Data Structures
- Stacks and Queues
- Linked Lists
- Implementing pointers and objects
- Representing rooted trees
*** Hash Tables
- Direct-address tables
- Hash tables
- Hash functions
- Open addressing
- Perfect hashing
*** Binary Search Trees
- What is a binary search tree?
- Querying a binary search tree
- Insertion and deletion
- Randomly built binary search trees
*** Red-Black Trees
- Properties of red-black trees
- Rotations
- Insertion
- Deletion
*** Augmenting Data Structures
- Dynamic order statistics
- How to augment a ddata structure
** Advanced Design and Analysis Techniques
*** Dynamic Programming
- Rod cutting
- Matrix-chain multiplication
- Elements of dynamic programming
- Longest common subsequence
- Optimal binary search trees
*** Greedy Algorithms
- An activity-selection problem
- Elements of the greedy strategy
- Huffman codes
- Matroids and greedy methods
- A task-scheduling problem as a matroid
*** Amortized Analysis
- Aggregate analysis
- The accounting method
- The potential method
- Dynamic tables
** Advanced Data Structures
*** B-Trees
- Definition of B-trees
- Basic operations on B-trees
- Deleting a key from a B-tree
*** Fibonacci Heaps
- Structure of Fibonacci heaps
- Mergeable-heap operations
- Decreasing a key and deleting a node
- Bounding the maximum degree
*** van Emde Boas Trees
- Preliminary approaches
- A recursive structure
- The van Emde Boas Tree
*** Data Structures for Disjoint Sets
- Disjoint-set operations
- Linked-list representations of disjoint sets
- Disjoint-set forests
- Analysis of uninon by rank with path compression
** Graph Algorithms
*** Elementary Graph Algorithms
- Representations of graphs
- Breadth-first search
- Depth-first search
- Topological sort
- Strongly connected components
*** Minimum Spanning Trees
- Growing a minimum spanning tree
- The algorithms of Kruskal and Prim
*** Single-Source Shortest Paths
- The Bellman-Ford algorithm
- Single-source shortest paths in directed acyclic graphs
- Dijkstra's algorithm
- Difference constraints and shortest paths
- Proofs of shortest-paths properties
*** All-Pairs Shortest Paths
- Shortest paths and matrix multiplication
- The Floyd-Warshall algorithm
- Johnson's algorithm for sparse graphs
*** Maximum Flow
- Flow networks
- The Ford-Fulkerson method
- Maximum bipartite matching
- Push-relabel algorithms
- The relabel-to-front algorithm
** Selected Topics
*** Multithreaded Algorithms
- The basics of dynamic multithreading
- Multithreaded matrix multiplication
- Multithreaded merge sort
*** Matrix Operations
- Solving systems of linear equations
- Inverting matrices
- Symmetric positive-definite matrices and least-squares approximation
*** Linear Programming
- Standard and slack forms
- Formulating problems as linear programs
- The simplex algorithm
- Duality
- The initial basic feasible solution
*** Polynomials and the FFT
- Representing polynomials
- The DFT and FFT
- Efficient FFT Implementations
*** Number-Theoretic Algorithms
- Elementary number-theoretic notions
- Greatest common divisor
- Modular arithmetic
- Solving modular linear equations
- The Chinese remainder theorem
- Powers of an element
- The RSA public-key cryptosystem
- Primality testing
- Integer factorization
*** String Matching
- The naive string-matching algorithm
- The Rabin-Karp algorithm
- String matching with finite automata
- The Knuth-Morris-Pratt algorithm
*** Computational Geometry
- Line-segment properties
- Determining whether any pair of segments intersects
- Finding the convex hull
- Finding the closest pair of points
*** NP-Completeness
- Polynomial time
- Polynomial-time verification
- NP-completeness and reducibility
- NP-completeness proofs
- NP-complete problems
*** Approximation Algorithms
- The vertex-coverc problem
- The traveling-salesman problem
- The set-covering problem
- Randomization and linear programming
- The subset-sum problem
** Appendix: Mathematical Background
*** Summations
- Summation formulas and properties
- Bounding summations
*** Sets, Etc.
- Sets
- Relations
- Functions
- Graphs
- Trees
*** Counting and Probability
- Counting
- Probability
- Discrcete random variables
- The geometric and binomial distributions
- The tails of the binomial distribution
*** Matrices
- Matrices and matrix operations
- Basic matrix properties
* Citation
- Cormen TH, editor. Introduction to algorithms. 3rd ed. Cambridge, Mass: MIT Press; 2009. 1292 p.