Introduction To Algorithms (CLRS)

Source

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.