Table of Contents

    Foreword

1  The Role of Algorithms in Computing

1.1
Algorithms
1.1-1 1.1-2 1.1-3 1.1-4 1.1-5
1.2
Algorithms as a Technology
1.2-1 1.2-2 1.2-3
Problems
1-1

2  Getting Started

2.1
Insertion Sort
2.1-1 2.1-2 2.1-3 2.1-4
2.2
Analyzing Algorithms
2.2-1 2.2-2 2.2-3 2.2-4
2.3
Designing Algorithms
2.3-1 2.3-2 2.3-3 2.3-4 2.3-5 2.3-6 2.3-7
Problems
2-1 2-2 2-3 2-4

3  Growth of Functions

3.1
Asymptotic Notation
3.1-1 3.1-2 3.1-3 3.1-4 3.1-5 3.1-6 3.1-7 3.1-8
3.2
Standard Notations and Common Functions
3.2-1 3.2-2 3.2-3 3.2-4 3.2-5 3.2-6 3.2-7 3.2-8
Problems
3-1 3-2 3-3 3-4 3-5 3-6

4  Divide-and-Conquer

4.1
The Maximum Subarray Problem
4.1-1 4.1-2 4.1-3 4.1-4 4.1-5
4.2
Strassen's Algorithm for Matrix Multiplication
4.2-1 4.2-2 4.2-3 4.2-4 4.2-5 4.2-6 4.2-7
4.3
The Substitution Method for Solving Recurrences
4.3-1 4.3-2 4.3-3 4.3-4 4.3-5 4.3-6 4.3-7 4.3-8 4.3-9
4.4
The Recursion-tree Method for Solving Recurrences
4.4-1 4.4-2 4.4-3 4.4-4 4.4-5 4.4-6 4.4-7 4.4-8 4.4-9
4.5
The Master Method for Solving Recurrences
4.5-1 4.5-2 4.5-3 4.5-4 4.5-5
4.6
Proof of the Master Theorem
Problems
4-1

A  Summations

A.1
Summation Formulas and Properties
A.1-1 A.1-2 A.1-3 A.1-4 A.1-5 A.1-6 A.1-7 A.1-8
A.2
Bounding Summations
A.2-1 A.2-2 A.2-3 A.2-4 A.2-5
Problems
A-1