# Introduction To Algorithms (CLRS)

## 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
• 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
• Implementing pointers and objects
• Representing rooted trees

#### Hash Tables

• Hash tables
• Hash functions
• 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

#### 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
• 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

• The basics of dynamic multithreading

#### 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
• 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.