Book:Thomas H. Cormen/Introduction to Algorithms
Jump to navigation
Jump to search
Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms
Published $\text {1990}$, MIT Press
- ISBN 0-262-53091-0
Contents
- Preface
- 1 Introduction
- 1.1 Algorithms
- 1.2 Analyzing algorithms
- 1.3 Designing algorithms
- 1.4 Summary
- 1 Introduction
- I Mathematical Foundations
- Introduction
- 2 Growth of Functions
- 2.1 Asymptotic notation
- 2.2 Standard notations and common functions
- 2 Growth of Functions
- 3 Summations
- 3.1 Summation formulas and properties
- 3.2 Bounding summations
- 3 Summations
- 4 Recurrences
- 4.1 The substitution method
- 4.2 The iteration method
- 4.3 The master method
- * 4.4 Proof of the master theorem
- 4 Recurrences
- 5 Sets, Etc.
- 5.1 Sets
- 5.2 Relations
- 5.3 Functions
- 5.4 Graphs
- 5.5 Trees
- 5 Sets, Etc.
- 6 Counting and Probability
- 6.1 Counting
- 6.2 Probability
- 6.3 Discrete random variables
- 6.4 The geometric and binomial distributions
- * 6.5 The tails of the binomial distribution
- 6.6 Probabilistic analysis
- 6 Counting and Probability
- II Sortlng and Order Statistics
- Introduction
- 7 Heapsort
- 7. 1 Heaps
- 7.2 Maintaining the heap property
- 7.3 Building a heap
- 7.4 The heapsort algorithm
- 7.5 Priority queues
- 7 Heapsort
- 8 Quicksort
- 8.1 Description of quicksort
- 8.2 Performance of quicksort
- 8.3 Randomized versions of quicksort
- 8.4 Analysis of quicksort
- 8 Quicksort
- 9 Sorting in Linear Time
- 9.1 Lower bounds for sorting
- 9.2 Counting sort
- 9.3 Radix sort
- 9.4 Bucket sort
- 9 Sorting in Linear Time
- 10 Medians and Order Statistics
- 10.1 Minimum and maximum
- 10.2 Selection in expected linear time
- 10.3 Selection in worst-case linear time
- 10 Medians and Order Statistics
- III Data Structures
- Introduction
- 11 Elementary Data Structures
- 11.1 Stacks and queues
- 11.2 Linked lists
- 11.3 Implementing pointers and objects
- l1.4 Representing rooted trees
- 11 Elementary Data Structures
- 12 Hash Tables
- 12.1 Direct-address tables
- 12.2 Hash tables
- 12.3 Hash functions
- 12.4 Open addressing
- 12 Hash Tables
- 13 Binary Search Trees
- 13.1 What is a binary search tree?
- 13.2 Querying a binary search tree
- 13.3 Insertion and deletion
- 13.4 Randomly built binary search trees
- 13 Binary Search Trees
- 14 Red-Black Trees
- 14.1 Properties of red-black trees
- 14.2 Rotations
- 14.3 Insertion
- 14.4 Deletion
- 14 Red-Black Trees
- 15 Augmenting Data Structures
- 15.1 Dynamic order statistics
- 15.2 How to augment a data structure
- 15.3 Interval trees
- 15 Augmenting Data Structures
- IV Advanced Design and Analysis Techniques
- Introduction
- 16 Dynamic Programming
- 16.1 Matrix-chain multiplication
- 16.2 Elements of dynamic programming
- 16.3 Longest common subsequence
- 16.4 Optimal polygon triangulation
- 16 Dynamic Programming
- 17 Greedy Algorithms
- 17.1 An activity-selection problem
- 17.2 Elements of the greedy strategy
- 17.3 Huffman codes
- * 17.4 Theoretical foundations for greedy methods
- * 17.5 A task-scheduling problem
- 17 Greedy Algorithms
- 18 Amortized Analysis
- 18.1 The aggregate method
- 18.2 The accounting method
- 18.3 The potential method
- 18.4 Dynamic tables
- 18 Amortized Analysis
- V Advanced Data Structures
- Introduction
- 19 B-Trees
- 19.1 Definition of B-trees
- 19.2 Basic operations on B-trees
- 19.3 Deleting a key from a B-tree
- 19 B-Trees
- 20 Binomial Heaps
- 20.1 Binomial trees and binomial heaps
- 20.2 Operations on binomial heaps
- 20 Binomial Heaps
- 21 Fibonacci Heaps
- 21.1 Structure of Fibonacci heaps
- 21.2 Mergeable-heap operations
- 21.3 Decreasing a key and deleting a node
- 21.4 Bounding the maximum degree
- 21 Fibonacci Heaps
- 22 Data Structures for Disjoint Sets
- 22.1 Disjoint-set operations
- 22.2 Linked-list representation of disjoint sets
- 22.3 Disjoint-set forests
- * 22.4 Analysis of union by rank with path compression
- 22 Data Structures for Disjoint Sets
- VI Graph Algorithms
- Introduction
- 23 Elementary Graph Algorithms
- 23.1 Representations of graphs
- 23.2 Breadth-first search
- 23.3 Depth-first search
- 23.4 Topological sort
- 23.5 Strongly connected components
- 23 Elementary Graph Algorithms
- 24 Minimum Spanning Trees
- 24.1 Growing a minimum spanning tree
- 24.2 The algorithms of Kruskal and Prim
- 24 Minimum Spanning Trees
- 25 Single-source Shortest Paths
- 25.1 Shortest paths and relaxation
- 25.2 Dijkstra's algorithm
- 25.3 The Bellman-Ford algorithm
- 25.4 Single-source shortest paths in directed acyclic graphs
- 25.5 Difference constraints and shortest paths
- 25 Single-source Shortest Paths
- 26 All-pairs Shortest Paths
- 26.1 Shortest paths and matrix multiplication
- 26.2 The Floyd-Warshall algorithm
- 26.3 Johnson's algorithm for sparse graphs
- * 26.4 A general framework for solving path problems in directed graphs
- 26 All-pairs Shortest Paths
- 27 Maximum Flow
- 27.1 Flow networks
- 27.2 The Ford-Fulkerson method
- 27.3 Maximum bipartite matching
- * 27.4 Preflow-push algorithms
- * 27.5 The lift-to-front algorithm
- 27 Maximum Flow
- VII Selected Topics
- Introduction
- 28 Sorting networks
- 28.1 Comparison networks
- 28.2 The zero-one principle
- 28.3 A bitonic sorting network
- 28.4 A merging network
- 28.5 A sorting network
- 28 Sorting networks
- 29 Arithmetic Circuits
- 29.1 Combinational circuits
- 29.2 Addition circuits
- 29.3 Multiplication circuits
- 29.4 Clocked circuits
- 29 Arithmetic Circuits
- 30 Algorithms for Parallel Computers
- 30.1 Pointer jumping
- 30.2 CRCW algorithms versus EREW algorithms
- 30.3 Brent's theorem and work efficiency
- * 30.4 Work-efficient parallel prefix computation
- 30.5 Deterministic symmetry breaking
- 30 Algorithms for Parallel Computers
- 31 Matrix Operations
- 31.1 Properties of matrices
- 31.2 Strassen's algorithm for matrix multiplication
- * 31.3 Algebraic number systems and boolean matrix multiplication
- 31.4 Solving systems of linear equations
- 31.5 Inverting matrices
- 31.6 Symmetric positive-definite matrices and least-squares approximation
- 31 Matrix Operations
- 32 Polynomials and the FFT
- 32.1 Representation of polynomials
- 32.2 The DFT and FFT
- 32.3 Efficient FFT implementations
- 32 Polynomials and the FFT
- 33 Number-Theoretic Algorithms
- 33.1 Elementary number-theoretic notions
- 33.2 Greatest common divisor
- 33.3 Modular arithmetic
- 33.4 Solving modular linear equations
- 33.5 The Chinese remainder theorem
- 33.6 Powers of an element
- 33.7 The RSA public-key cryptosystem
- * 33.8 Primality testing
- * 33.9 Integer factorisation
- 33 Number-Theoretic Algorithms
- 34 String Matching
- 34.1 The naive string-matching algorithm
- 34.2 The Rabin-Karp algorithm
- 34.3 String matching with finite automata
- 34.4 The Knuth-Morris-Pratt algorithm
- * 34.5 The Boyer-Moore algorithm
- 34 String Matching
- 35 Computational Geometry
- 35.1 Line-segment properties
- 35.2 Determining whether any pair of segments intersects
- 35.3 Finding the convex hull
- 35.4 Finding the closest pair of points
- 35 Computational Geometry
- 36 NP-Completeness
- 36.1 Polynomial time
- 36.2 Polynomial-time verification
- 36.3 NP-completeness and reducibility
- 36.4 NP-completeness proofs
- 36.5 NP-complete problems
- 36 NP-Completeness
- 37 Approximation Algorithms
- 37.1 The vertex-cover problem
- 37.2 The traveling-salesman problem
- 37.3 The set-covering problem
- 27.4 The subset-sum problem
- 37 Approximation Algorithms
- Bibliography
- Index