Introduction to Algorithms

by Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.

• ISBN13: 9780070131439
• ISBN10: 0070131430
• Format: Hardcover
• Copyright: 1990-07-01
• Publisher: McGraw-Hill College

Table of Contents

Preface	xiii
1 Introduction	1	(20)
1.1 Algorithms	1	(5)
1.2 Analyzing algorithms	6	(5)
1.3 Designing algorithms	11	(5)
1.4 Summary	16	(5)
I Mathematical Foundations	21	(116)
Introduction	21	(2)
2 Growth of Functions	23	(19)
2.1 Asymptotic notation	23	(9)
2.2 Standard notations and common functions	32	(10)
3 Summations	42	(11)
3.1 Summation formulas and properties	42	(4)
3.2 Bounding summations	46	(7)
4 Recurrences	53	(24)
4.1 The substitution method	54	(4)
4.2 The iteration method	58	(3)
4.3 The master method	61	(3)
*4.4 Proof of the master theorem	64	(13)
5 Sets, Etc.	77	(22)
5.1 Sets	77	(4)
5.2 Relations	81	(3)
5.3 Functions	84	(2)
5.4 Graphs	86	(5)
5.5 Trees	91	(8)
6 Counting and Probability	99	(38)
6.1 Counting	99	(5)
6.2 Probability	104	(7)
6.3 Discrete random variables	111	(4)
6.4 The geometric and binomial distributions	115	(6)
*6.5 The tails of the binomial distribution	121	(5)
6.6 Probabilistic analysis	126	(11)
II Sorting and Order Statistics	137	(60)
Introduction	137	(3)
7 Heapsort	140	(13)
7.1 Heaps	140	(2)
7.2 Maintaining the heap property	142	(3)
7.3 Building a heap	145	(2)
7.4 The heapsort algorithm	147	(2)
7.5 Priority queues	149	(4)
8 Quicksort	153	(19)
8.1 Description of quicksort	153	(3)
8.2 Performance of quicksort	156	(5)
8.3 Randomized versions of quicksort	161	(2)
8.4 Analysis of quicksort	163	(9)
9 Sorting in Linear Time	172	(13)
9.1 Lower bounds for sorting	172	(3)
9.2 Counting sort	175	(3)
9.3 Radix sort	178	(2)
9.4 Bucket sort	180	(5)
10 Medians and Order Statistics	185	(12)
10.1 Minimum and maximum	185	(2)
10.2 Selection in expected linear time	187	(2)
10.3 Selection in worst-case linear time	189	(8)
III Data Structures	197	(102)
Introduction	197	(3)
11 Elementary Data Structures	200	(19)
11.1 Stacks and queues	200	(4)
11.2 Linked lists	204	(5)
11.3 Implementing pointers and objects	209	(4)
11.4 Representing rooted trees	213	(6)
12 Hash Tables	219	(25)
12.1 Direct-address tables	219	(2)
12.2 Hash tables	221	(5)
12.3 Hash functions	226	(6)
12.4 Open addressing	232	(12)
13 Binary Search Trees	244	(19)
13.1 What is a binary search tree?	244	(2)
13.2 Querying a binary search tree	246	(4)
13.3 Insertion and deletion	250	(4)
*13.4 Randomly built binary search trees	254	(9)
14 Red-Black Trees	263	(18)
14.1 Properties of red-black trees	263	(2)
14.2 Rotations	265	(3)
14.3 Insertion	268	(4)
14.4 Deletion	272	(9)
15 Augmenting Data Structures	281	(18)
15.1 Dynamic order statistics	281	(6)
15.2 How to augment a data structure	287	(3)
15.3 Interval trees	290	(9)
IV Advanced Design and Analysis Techniques	299	(80)
Introduction	299	(2)
16 Dynamic Programming	301	(28)
16.1 Matrix-chain multiplication	302	(7)
16.2 Elements of dynamic programming	309	(5)
16.3 Longest common subsequence	314	(6)
16.4 Optimal polygon triangulation	320	(9)
17 Greedy Algorithms	329	(27)
17.1 An activity-selection problem	329	(4)
17.2 Elements of the greedy strategy	333	(4)
17.3 Huffman codes	337	(8)
*17.4 Theoretical foundations for greedy methods	345	(5)
*17.5 A task-scheduling problem	350	(6)
18 Amortized Analysis	356	(23)
18.1 The aggregate method	357	(3)
18.2 The accounting method	360	(3)
18.3 The potential method	363	(4)
18.4 Dynamic tables	367	(12)
V Advanced Data Structures	379	(84)
Introduction	379	(2)
19 B-Trees	381	(19)
19.1 Definition of B-trees	384	(3)
19.2 Basic operations on B-trees	387	(8)
19.3 Deleting a key from a B-tree	395	(5)
20 Binomial Heaps	400	(20)
20.1 Binomial trees and binomial heaps	401	(5)
20.2 Operations on binomial heaps	406	(14)
21 Fibonacci Heaps	420	(20)
21.1 Structure of Fibonacci heaps	421	(2)
21.2 Mergeable-heap operations	423	(8)
21.3 Decreasing a key and deleting a node	431	(4)
21.4 Bounding the maximum degree	435	(5)
22 Data Structures for Disjoint Sets	440	(23)
22.1 Disjoint-set operations	440	(3)
22.2 Linked-list representation of disjoint sets	443	(3)
22.3 Disjoint-set forests	446	(4)
*22.4 Analysis of union by rank with path compression	450	(13)
VI Graph Algorithms	463	(168)
Introduction	463	(2)
23 Elementary Graph Algorithms	465	(33)
23.1 Representations of graphs	465	(4)
23.2 Breadth-first search	469	(8)
23.3 Depth-first search	477	(8)
23.4 Topological sort	485	(3)
23.5 Strongly connected components	488	(10)
24 Minimum Spanning Trees	498	(16)
24.1 Growing a minimum spanning tree	499	(5)
24.2 The algorithms of Kruskal and Prim	504	(10)
25 Single-Source Shortest Paths	514	(36)
25.1 Shortest paths and relaxation	518	(9)
25.2 Dijkstra's algorithm	527	(5)
25.3 The Bellman-Ford algorithm	532	(4)
25.4 Single-source shortest paths in directed acyclic graphs	536	(3)
25.5 Difference constraints and shortest paths	539	(11)
26 All-Pairs Shortest Paths	550	(29)
26.1 Shortest paths and matrix multiplication	552	(6)
26.2 The Floyd-Warshall algorithm	558	(7)
26.3 Johnson's algorithm for sparse graphs	565	(5)
*26.4 A general framework for solving path problems in directed graphs	570	(9)
27 Maximum Flow	579	(52)
27.1 Flow networks	580	(7)
27.2 The Ford-Fulkerson method	587	(13)
27.3 Maximum bipartite matching	600	(5)
*27.4 Preflow-push algorithms	605	(10)
*27.5 The lift-to-front algorithm	615	(16)
VII Selected Topics	631	(356)
Introduction	631	(3)
28 Sorting Networks	634	(20)
28.1 Comparison networks	634	(5)
28.2 The zero-one principle	639	(3)
28.3 A bitonic sorting network	642	(4)
28.4 A merging network	646	(2)
28.5 A sorting network	648	(6)
29 Arithmetic Circuits	654	(34)
29.1 Combinational circuits	655	(5)
29.2 Addition circuits	660	(11)
29.3 Multiplication circuits	671	(7)
29.4 Clocked circuits	678	(10)
30 Algorithms for Parallel Computers	688	(42)
30.1 Pointer jumping	692	(9)
30.2 CRCW algorithms versus EREW algorithms	701	(8)
30.3 Brent's theorem and work efficiency	709	(5)
*30.4 Work-efficient parallel prefix computation	714	(6)
30.5 Deterministic symmetry breaking	720	(10)
31 Matrix Operations	730	(46)
31.1 Properties of matrices	730	(9)
31.2 Strassen's algorithm for matrix multiplication	739	(6)
*31.3 Algebraic number systems and boolean matrix multiplication	745	(4)
31.4 Solving systems of linear equations	749	(13)
31.5 Inverting matrices	762	(4)
31.6 Symmetric positive-definite matrices and least-squares approximation	766	(10)
32 Polynomials and the FFT	776	(25)
32.1 Representation of polynomials	778	(5)
32.2 The DFT and FFT	783	(8)
32.3 Efficient FFT implementations	791	(10)
33 Number-Theoretic Algorithms	801	(52)
33.1 Elementary number-theoretic notions	802	(6)
33.2 Greatest common divisor	808	(6)
33.3 Modular arithmetic	814	(6)
33.4 Solving modular linear equations	820	(3)
33.5 The Chinese remainder theorem	823	(4)
33.6 Powers of an element	827	(4)
33.7 The RSA public-key cryptosystem	831	(6)
*33.8 Primality testing	837	(7)
*33.9 Integer factorization	844	(9)
34 String Matching	853	(33)
34.1 The naive string-matching algorithm	855	(2)
34.2 The Rabin-Karp algorithm	857	(5)
34.3 String matching with finite automata	862	(7)
34.4 The Knuth-Morris-Pratt algorithm	869	(7)
*34.5 The Boyer-Moore algorithm	876	(10)
35 Computational Geometry	886	(30)
35.1 Line-segment properties	887	(5)
35.2 Determining whether any pair of segments intersects	892	(6)
35.3 Finding the convex hull	898	(10)
35.4 Finding the closest pair of points	908	(8)
36 NP-Completeness	916	(48)
36.1 Polynomial time	917	(7)
36.2 Polynomial-time verification	924	(5)
36.3 NP-completeness and reducibility	929	(10)
36.4 NP-completeness proofs	939	(7)
36.5 NP-complete problems	946	(18)
37 Approximation Algorithms	964	(23)
37.1 The vertex-cover problem	966	(3)
37.2 The traveling-salesman problem	969	(5)
37.3 The set-covering problem	974	(4)
37.4 The subset-sum problem	978	(9)
Bibliography	987	(10)
Index	997