Introduction to Algorithms

1 The Role of Algorithms in Computing
2 Getting Started
3 Growth of Functions
4 Divide-and-Conquer
5 Probabilistic Analysis and Randomized Algorithms

II Sorting and Order Statistics
Introduction

6 Heapsort
7 Quicksort
8 Sorting in Linear Time
9 Medians and Order Statistics

III Data Structures
Introduction

10 Elementary Data Structures
11 Hash Tables
12 Binary Search Trees
13 Red-Black Trees
14 Augmenting Data Structures

IV Advanced Design and Analysis Techniques
Introduction

15 Dynamic Programming
16 Greedy Algorithms
17 Amortized Analysis

V Advanced Data Structures
Introduction
18 B-Trees
19 Fibonacci Heaps
20 Van Emde Boas Trees
21 Data Structures for Disjoint Sets

VI Graph Algorithms
Introduction

22 Elementary Graph Algorithms
23 Minimum Spanning Trees
24 Single-Source Shortest Paths
25 All-Pairs Shortest Paths
26 Maximum Flow

VII Selected Topics
Introduction

27 Multithreaded Algorithms
28 Matrix Operations
29 Linear Programming
30 Polynomials and the FFT
31 Number-Theoretic Algorithms
32 String Matching
33 Computational Geometry
34 NP-Completeness
35 Approximation Algorithms

VIII Appendix: Mathematical Background
Introduction
A Summations
B Sets, Etc.
C Counting and Probability
D Matrices

Bibliography
Index