Introduction to Algorithms, Second Edition

by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

• ISBN13: 9780262032933
• ISBN10: 0262032937
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-09-01
• Publisher: Mit Pr

Summary

There are books on algorithms that are rigorous but incomplete and others that cover masses of material but lack rigor. Introduction to Algorithmscombines 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 the standard reference for professionals and a widely used text in universities worldwide. The second edition features new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming, as well as extensive revisions to virtually every section of the book. In a subtle but important change, loop invariants are introduced early and used throughout the text to prove algorithm correctness. Without changing the mathematical and analytic focus, the authors have moved much of the mathematical foundations material from Part I to an appendix and have included additional motivational material at the beginning.

Table of Contents

Preface	xiii
I Foundations
Introduction	3	(2)
The Role of Algorithms in Computing	5	(10)
Algorithms	5	(5)
Algorithms as a technology	10	(5)
Getting Started	15	(26)
Insertion sort	15	(6)
Analyzing algorithms	21	(6)
Designing algorithms	27	(14)
Growth of Functions	41	(21)
Asymptotic notation	41	(10)
Standard notations and common functions	51	(11)
Recurrences	62	(29)
The substitution method	63	(4)
The recursion-tree method	67	(6)
The master method	73	(3)
Proof of the master theorem	76	(15)
Probabilistic Analysis and Randomized Algorithms	91	(36)
The hiring problem	91	(3)
Indicator random variables	94	(5)
Randomized algorithms	99	(7)
Probabilistic analysis and further uses of indicator random variables	106	(21)
II Sorting and Order Statistics
Introduction	123	(4)
Heapsort	127	(18)
Heaps	127	(3)
Maintaining the heap property	130	(2)
Building a heap	132	(3)
The heapsort algorithm	135	(3)
Priority queues	138	(7)
Quicksort	145	(20)
Description of quicksort	145	(4)
Performance of quicksort	149	(4)
A randomized version of quicksort	153	(2)
Analysis of quicksort	155	(10)
Sorting in Linear Time	165	(18)
Lower bounds for sorting	165	(3)
Counting sort	168	(2)
Radix sort	170	(4)
Bucket sort	174	(9)
Medians and Order Statistics	183	(17)
Minimum and maximum	184	(1)
Selection in expected linear time	185	(4)
Selection in worst-case linear time	189	(11)
III Data Structures
Introduction	197	(3)
Elementary Data Structures	200	(21)
Stacks and queues	200	(4)
Linked lists	204	(5)
Implementing pointers and objects	209	(5)
Representing rooted trees	214	(7)
Hash Tables	221	(32)
Direct-address tables	222	(2)
Hash tables	224	(5)
Hash functions	229	(8)
Open addressing	237	(8)
Perfect hashing	245	(8)
Binary Search Trees	253	(20)
What is a binary search tree?	253	(3)
Querying a binary search tree	256	(5)
Insertion and deletion	261	(4)
Randomly built binary search trees	265	(8)
Red-Black Trees	273	(29)
Properties of red-black trees	273	(4)
Rotations	277	(3)
Insertion	280	(8)
Deletion	288	(14)
Augmenting Data Structures	302	(21)
Dynamic order statistics	302	(6)
How to augment a data structure	308	(3)
Interval trees	311	(12)
IV Advanced Design and Analysis Techniques
Introduction	321	(2)
Dynamic Programming	323	(47)
Assembly-line scheduling	324	(7)
Matrix-chain multiplication	331	(8)
Elements of dynamic programming	339	(11)
Longest common subsequence	350	(6)
Optimal binary search trees	356	(14)
Greedy Algorithms	370	(35)
An activity-selection problem	371	(8)
Elements of the greedy strategy	379	(6)
Huffman codes	385	(8)
Theoretical foundations for greedy methods	393	(6)
A task-scheduling problem	399	(6)
Amortized Analysis	405	(29)
Aggregate analysis	406	(4)
The accounting method	410	(2)
The potential method	412	(4)
Dynamic tables	416	(18)
V Advanced Data Structures
Introduction	431	(3)
B-Trees	434	(21)
Definition of B-trees	438	(3)
Basic operations on B-trees	441	(8)
Deleting a key from a B-tree	449	(6)
Binomial Heaps	455	(21)
Binomial trees and binomial heaps	457	(4)
Operations on binomial heaps	461	(15)
Fibonacci Heaps	476	(22)
Structure of Fibonacci heaps	477	(2)
Mergeable-heap operations	479	(10)
Decreasing a key and deleting a node	489	(4)
Bounding the maximum degree	493	(5)
Data Structures for Disjoint Sets	498	(29)
Disjoint-set operations	498	(3)
Linked-list representation of disjoint sets	501	(4)
Disjoint-set forests	505	(4)
Analysis of union by rank with path compression	509	(18)
VI Graph Algorithms
Introduction	525	(2)
Elementary Graph Algorithms	527	(34)
Representations of graphs	527	(4)
Breadth-first search	531	(9)
Depth-first search	540	(9)
Topological sort	549	(3)
Strongly connected components	552	(9)
Minimum Spanning Trees	561	(19)
Growing a minimum spanning tree	562	(5)
The algorithms of Kruskal and Prim	567	(13)
Single-source Shortest Paths	580	(40)
The Bellman-Ford algorithm	588	(4)
Single-source shortest paths in directed acyclic graphs	592	(3)
Dijkstra's algorithm	595	(6)
Difference constraints and shortest paths	601	(6)
Proofs of shortest-paths properties	607	(13)
All-Pairs Shortest Paths	620	(23)
Shortest paths and matrix multiplication	622	(7)
The Floyd-Warshall algorithm	629	(7)
Johnson's algorithm for sparse graphs	636	(7)
Maximum Flow	643	(61)
Flow networks	644	(7)
The Ford-Fulkerson method	651	(13)
Maximum bipartite matching	664	(5)
Push-relabel algorithms	669	(12)
The relabel-to-front algorithm	681	(23)
VII Selected Topics
Introduction	701	(3)
Sorting Networks	704	(21)
Comparison networks	704	(5)
The zero-one principle	709	(3)
A bitonic sorting network	712	(4)
A merging network	716	(3)
A sorting network	719	(6)
Matrix Operations	725	(45)
Properties of matrices	725	(10)
Strassen's algorithm for matrix multiplication	735	(7)
Solving systems of linear equations	742	(13)
Inverting matrices	755	(5)
Symmetric positive-definite matrices and least-squares approximation	760	(10)
Linear Programming	770	(52)
Standard and slack forms	777	(8)
Formulating problems as linear programs	785	(5)
The simplex algorithm	790	(14)
Duality	804	(7)
The initial basic feasible solution	811	(11)
Polynomials and the FFT	822	(27)
Representation of polynomials	824	(6)
The DFT and FFT	830	(9)
Efficient FFT implementations	839	(10)
Number-Theoretic Algorithms	849	(57)
Elementary number-theoretic notions	850	(6)
Greatest common divisor	856	(6)
Modular arithmetic	862	(7)
Solving modular linear equations	869	(4)
The Chinese remainder theorem	873	(3)
Powers of an element	876	(5)
The RSA public-key cryptosystem	881	(6)
Primality testing	887	(9)
Integer factorization	896	(10)
String Matching	906	(27)
The naive string-matching algorithm	909	(2)
The Rabin-Karp algorithm	911	(5)
String matching with finite automata	916	(7)
The Knuth-Morris-Pratt algorithm	923	(10)
Computational Geometry	933	(33)
Line-segment properties	934	(6)
Determining whether any pair of segments intersects	940	(7)
Finding the convex hull	947	(10)
Finding the closest pair of points	957	(9)
NP-Completeness	966	(56)
Polynomial time	971	(8)
Polynomial-time verfication	979	(5)
NP-completeness and reducibility	984	(11)
NP-completeness proofs	995	(8)
NP-complete problems	1003	(19)
Approximation Algorithms	1022	(105)
The vertex-cover problem	1024	(3)
The traveling-salesman problem	1027	(6)
The set-covering problem	1033	(6)
Randomization and linear programming	1039	(4)
The subset-sum problem	1043	(15)
VIII Appendix: Mathematical Background
Introduction	1057	(1)
A Summations	1058	(4)
A.1 Summation formulas and properties	1058	(4)
A.2 Bounding summations	1062	(8)
B Sets, Etc.	1070	(1)
B.1 Sets	1070	(5)
B.2 Relations	1075	(2)
B.3 Functions	1077	(3)
B.4 Graphs	1080	(5)
B.5 Trees	1085	(9)
C Counting and Probability	1094	(33)
C.1 Counting	1094	(6)
C.2 Probability	1100	(6)
C.3 Discrete random variables	1106	(6)
C.4 The geometric and binomial distributions	1112	(6)
C.5 The tails of the binomial distribution	1118	(9)
Bibliography	1127	(18)
Index	1145