# Book:Thomas H. Cormen/Introduction to Algorithms

Jump to navigation
Jump to search
## Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest:

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

**I Mathematical Foundations**

**Introduction**

**2 Growth of Functions**- 2.1 Asymptotic notation
- 2.2 Standard notations and common functions

**3 Summations**- 3.1 Summation formulas and properties
- 3.2 Bounding 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

**5 Sets, Etc.**- 5.1 Sets
- 5.2 Relations
- 5.3 Functions
- 5.4 Graphs
- 5.5 Trees

**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

**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

**8 Quicksort**- 8.1 Description of quicksort
- 8.2 Performance of quicksort
- 8.3 Randomized versions of quicksort
- 8.4 Analysis of quicksort

**9 Sorting in Linear Time**- 9.1 Lower bounds for sorting
- 9.2 Counting sort
- 9.3 Radix sort
- 9.4 Bucket sort

**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

**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

**12 Hash Tables**- 12.1 Direct-address tables
- 12.2 Hash tables
- 12.3 Hash functions
- 12.4 Open addressing

**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

**14 Red-Black Trees**- 14.1 Properties of red-black trees
- 14.2 Rotations
- 14.3 Insertion
- 14.4 Deletion

**15 Augmenting Data Structures**- 15.1 Dynamic order statistics
- 15.2 How to augment a data structure
- 15.3 Interval trees

**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

**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

**18 Amortized Analysis**- 18.1 The aggregate method
- 18.2 The accounting method
- 18.3 The potential method
- 18.4 Dynamic tables

**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

**20 Binomial Heaps**- 20.1 Binomial trees and binomial heaps
- 20.2 Operations on 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

**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

**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

**24 Minimum Spanning Trees**- 24.1 Growing a minimum spanning tree
- 24.2 The algorithms of Kruskal and Prim

**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

**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

**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

**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

**29 Arithmetic Circuits**- 29.1 Combinational circuits
- 29.2 Addition circuits
- 29.3 Multiplication circuits
- 29.4 Clocked 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

**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

**32 Polynomials and the FFT**- 32.1 Representation of polynomials
- 32.2 The DFT and FFT
- 32.3 Efficient FFT implementations

**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

**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

**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

**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

**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

**Bibliography**

**Index**