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