Introduction to algorithms

Preface	p. xiii
I Foundations
Introduction	p. 3
1 The Role of Algorithms in Computing	p. 5
2 Getting Started	p. 15
3 Growth of Functions	p. 41
4 Recurrences	p. 62
5 Probabilistic Analysis and Randomized Algorithms	p. 91
II Sorting and Order Statistics
Introduction	p. 123
6 Heapsort	p. 127
7 Quicksort	p. 145
8 Sorting in Linear Time	p. 165
9 Medians and Order Statistics	p. 183
III Data Structures
Introduction	p. 197
10 Elementary Data Structures	p. 200
11 Hash Tables	p. 221
12 Binary Search Trees	p. 253
13 Red-Black Trees	p. 273
14 Augmenting Data Structures	p. 302
IV Advanced Design and Analysis Techniques
Introduction	p. 321
15 Dynamic Programming	p. 323
16 Greedy Algorithms	p. 370
17 Amortized Analysis	p. 405
V Advanced Data Structures
Introduction	p. 431
18 B-Trees	p. 434
19 Binomial Heaps	p. 455
20 Fibonacci Heaps	p. 476
21 Data Structures for Disjoint Sets	p. 498
VI Graph Algorithms
Introduction	p. 525
22 Elementary Graph Algorithms	p. 527
23 Minimum Spanning Trees	p. 561
24 Single-Source Shortest Paths	p. 580
25 All-Pairs Shortest Paths	p. 620
26 Maximum Flow	p. 643
VII Selected Topics
Introduction	p. 701
27 Sorting Networks	p. 704
28 Matrix Operations	p. 725
29 Linear Programming	p. 770
30 Polynomials and the FFT	p. 822
31 Number-Theoretic Algorithms	p. 849
32 String Matching	p. 906
33 Computational Geometry	p. 933
34 NP-Completeness	p. 966
35 Approximation Algorithms	p. 1022
VIII Appendix: Mathematical Background
Introduction	p. 1057
A Summations	p. 1058
B Sets, Etc.	p. 1070
C Counting and Probability	p. 1094
Bibliography	p. 1127
Index	p. 1145