Copyright ©1998-2010 Glenn Fleishman. Send in your comments. Bibliographic information on isbn.nu licensed from Baker & Taylor. Contact them for corrections and licensing, or read more about our data.
Tables of Contents for Introduction to Algorithms
Chapter/Section Title
Page #
Page Count
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