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