Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms

3rd Edition. — MIT Press, 2009. — 1312 p. — ISBN 978-0262033848.Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.The first edition became a widely used text in universities worldwide as well as the standard reference for professionals. The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming. The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, and substantial additions to the chapter on recurrences (now called Divide-and-Conquer). It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many new exercises and problems have been added for this edition.As of the third edition, this textbook is published exclusively by the MIT Press.FoundationsThe 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 Randomized Algorithms
The hiring problem
Indicator random variables
Randomized algorithms
Probabilistic analysis and further uses of indicator random variables
Sorting and Order StatisticsHeapsort
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 StructuresElementary 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 data structure
Interval trees
Advanced Design and Analysis TechniquesDynamic 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 StructuresB-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 representation of disjoint sets
Disjoint-set forests
Analysis of union by rank with path compression
Graph AlgorithmsElementary 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 TopicsMultithreaded 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-cover problem
The traveling-salesman problem
The set-covering problem
Randomization and linear programming
The subset-sum problem
Appendix: Mathematical BackgroundSummations
Summation formulas and properties
Bounding summations
Sets, Etc.
Sets
Relations
Functions
Graphs
Trees
Counting and Probability
Counting
Probability
Discrete random variables
The geometric and binomial distributions
The tails of the binomial distribution
Matrices
Matrices and matrix operations
Basic matrix properties