PART 1 Basic Concepts and Introduction to Algorithms
Chapter 1 Basic Concepts in Algorithmic Analysis
1.1 Introduction
1.2 Historical Background
1.3 Binary Search
1.3.1 Analysis of the binary search algorithm
1.4 Merging Two Sorted Lists
1.5 Selection Sort
1.6 Insertion Sort
1.7 Bottom-Up Merge Sorting
1.7.1 Analysis of bottom-up merge sorting
1.8 Time Complexity
1.8.1 Order of growth
1.8.2 The O-notation
1.8.3 The Ω-notation
1.8.4 The θ-notation
1.8.5 Examples
1.8.6 Complexity classes and the o-notation
1.9 Space Complexity
1.10 Optimal Algorithms
1.11 How to Estimate the Running Time of an Algorithm
1.11.1 Counting the number of iterations
1.11.2 Counting the frequency of basic operations
1.11.3 Using recurrence relations
1.12 Worst case and average case analysis
1.12.1 Worst case analysis
1.12.2 Average case analysis
1.13 Amortized Analysis
1.14 Input Size and Problem Instance
1.15 Exercises
1.16 Bibliographic Notes
Chapter 2 Mathematical Preliminaries
2.1 Sets, Relations and Functions
2.1.1 Sets
2.1.2 Relations
2.1.2.1 Equivalence relations
2.1.3 Functions
2.2 Proof Methods
2.2.1 Direct proof
2.2.2 Indirect proof
2.2.3 Proof by contradiction
2.2.4 Proof by counterexample
2.2.5 Mathematical induction
2.3 Logarithms
2.4 Floor and Ceiling Functions
2.5 Factorial and Binomial Coefficients
2.5.1 Factorials
2.5.2 Binomial coefficients
2.6 The Pigeonhole Principle
2.7 Summations
2.7.1 Approximation of summations by integration
2.8 Recurrence Relations
2.8.1 Solution of linear homogeneous recurrences
2.8.2 Solution of inhomogeneous recurrences
2.8.3 Solution of divide-and-conquer recurrences
2.8.3.1 Expanding the recurrence
2.8.3.2 Substitution
2.8.3.3 Change of variables
2.9 Exercises
Chapter 3 Data Structures
3.1 Introduction
3.2 Linked Lists
3.2.1 Stacks and queues
3.3 Graphs
3.3.1 Representation of graphs
3.3.2 Planar graphs
3.4 Trees
3.5 Rooted Trees
3.5.1 Tree traversals
3.6 Binary Trees
3.6.1 Some quantitative aspects of binary trees
3.6.2 Binary search trees
3.7 Exercises
3.8 Bibliographic Notes
Chapter 4 Heaps and the Disjoint Sets Data Structures
4.1 Introduction
4.2 Heaps
4.2.1 Operations on heaps
4.2.2 Creating a heap
4.2.3 Heapsort
4.2.4 Min and max heaps
4.3 Disjoint Sets Data Structures
4.3.1 The union by rank heuristic
4.3.2 Path compression
4.3.3 The union-find algorithms
4.3.4 Analysis of the union-find algorithms
4.4 Exercises
4.5 Bibliographic Notes
PART 2 Techniques Based on Recursion
Chapter 5 Induction
5.1 Introduction
5.2 Two Simple Examples
5.2.1 Selection sort
5.2.2 Insertion sort
5.3 Radix Sort
5.4 Integer Exponentiation
5.5 Evaluating Polynomials (Hornet's Rule)
5.6 Generating Permutations
5.6.1 The first algorithm
5.6.2 The second algorithm
5.7 Finding the Majority Element
5.8 Exercises
5.9 Bibliographic Notes
Chapter 6 Divide and Conquer
6.1 Introduction
6.2 Binary Search
6.3 Mergesort
6.3.1 How the algorithm works
6.3.2 Analysis cf the mergesort algorithm
6.4 The Divide and Conquer Paradigm
6.5 Selection: Finding the Median and the kth Smallest Element
6.5.1 Analysis cf the selection algorithm
6.6 Quicksort
6.6.1 A partitioning algorithm
6.6.2 The sorting algorithm
6.6.3 Analysis of the quicksort algorithm
6.6.3.1 The worst case behavior
6.6.3.2 The average case behavior
6.6.4 Compariscn of sorting algorithms
6.7 Multiplication of Large Integers
6.8 Matrix Multiplication
6.8.1 The traditional algorithm
6.8.2 Recursive version
6.8.3 Strassen's algorithm
6.8.4 Comparisons cf the three algorithms
6.9 The Closest Pair Problem
6.9.1 Time complexity
……
PART 3 First-Cut Techniques
PART 4 Complexity of Problems
PART 5 Coping with Hardness
PART 6 Iterative Improvement for Domain-Specific Problems
PART 7 Techniques in Computational Geometry
