Introduction to the Design and Analysis of Algorithms: A Multi-Paradigm Approach

Preface 
Contents 

I Fundamentals 

1 Introduction 
1.1 Origin of the Algorithm 
1.2 Two Notations for Expressing Algorithms 
1.2.1 Functional Notation 
1.2.2 Imperative Notation 

2 Design Overview 
2.1 Perspectives on Design 
2.2 Structural Recursion 
2.2.1 An Extended Example: Reversal 
2.2.2 An Extended Example: Multiplication 
2.3 Divide and Conquer 
2.3.1 An Extended Example: Raising to a Power 
2.4 Tail Recursion 
2.4.1 An Extended Example: Multiplication Revisited 
2.5 Dynamic Programming 
2.5.1 An Extended Example: Powers of Two 
2.5.2 Issues and Alternatives 
2.6 Greedy Algorithms 
2.6.1 An Extended Example: Minimum Change 
2.7 Exercises 

3 Analysis Overview 
3.1 Perspectives on Analysis 
3.2 Example: Insertion Sort 
3.3 Example: Factorial 
3.4 Exercises 

4 Asymptotics 
4.1 Introduction to Asymptotics 
4.2 Formal Definitions 
4.3 Proofs Using the Definitions 
4.4 Properties of Asymptotic Notation 
4.4.1 Facts about O 
4.4.2 Facts about Ω 
4.4.3 Example Using the Facts 
4.4.4 Some Proofs 
4.5 Additional Properties of Asymptotic Notation 
4.6 Exercises 

5 Sums and Floors 
5.1 Introduction to Sums, Floors, and Ceilings
5.2 Sums 
5.2.1 Fundamental Formulas 
5.2.2 Bounding Sums
5.3 Floors and Ceilings 
5.4 Exercises 

6 Recurrence Relations 
6.1 Introduction to Recurrence Relations 
6.2 Substitution By Example 
6.3 Iteration by Example 
6.4 Induction By Example
6.5 A More Challenging Example Involving Floor 
6.5.1 Substitution 
6.5.2 Iteration 
6.5.3 Induction 
6.6 A Recurrence Relation with Full History
6.6.1 Substitution 
6.6.2 Observations 
6.6.3 Iteration 
6.6.4 Induction 
6.7 A Difference Equation Method Example 
6.8 A Very Brief Introduction to Generating Functions 
6.8.1 A Simple Example 
6.8.2 Another Example 
6.9 Exercises 

II Searching and Sorting 

7 Linear Search 
7.1 Introduction to Linear Search 
7.2 A Structurally Recursive Approach 
7.2.1 Complexity 
7.3 Searching Arrays 
7.4 Dynamic Linear Searching 

8 Binary Search 
8.1 Introduction to Binary Search 
8.2 Binary Search Trees and Binary Search 
8.2.1 Definition 
8.2.2 Operations 
8.2.3 Time Complexity 
8.3 Representing Binary Search Trees as Arrays 
8.3.1 Converting Between Binary Search Trees and Arrays 
8.3.2 Binary Search on Arrays with Slicing 
8.3.3 Binary Search Using Slicing Parameters Instead of Slicing 
8.3.4 Time Complexity 
8.4 Exercises 

9 Naive Sorting 
9.1 Introduction to Naive Sorting 
9.2 Insertion Sort 
9.2.1 Accumulative Insertion Sort 
9.2.2 Imperative Insertion Sort 
9.3 Selection Sort
9.3.1 A Slow Sort 
9.3.2 Accumulative Selection Sort 
9.3.3 Imperative Selection Sort 

10 Heaps 
10.1 Introduction to Heaps
10.2 Binary Search Trees 
10.3 Left-Complete Binary Trees 
10.3.1 Illustrating the Heap Operations for a Left-Complete Binary Min-Heap 
10.3.2 Representing the Tree as an Array 

11 Tree-Based Sorting 
11.1 Introduction to Tree-Based Sorting 
11.2 Fast Insertion Using a Tree 
11.3 Fast Selection Using a Tree 
11.3.1 A Functional Formulation 
11.3.2 An Imperative Formulation 

12 Divide and Conquer Sorting 
12.1 Introduction to Divide and Conquer Sorting 
12.2 Merge Sort 
12.2.1 Time Complexity 
12.2.2 Imperative Formulation 
12.3 Quick Sort 
12.3.1 Quicker Quick Sorts 
12.3.2 Time Complexity 
12.4 Exercises 

13 Selection 
13.1 Introduction to Selection 
13.2 Deriving an Algorithm 
13.3 Time Complexity
13.4 Exercises 

14 Lower Bounds for Sorting 
14.1 Introduction to Lower Bounds for Sorting 
14.2 An Alternative Computational Model 
14.3 Consequences of the Alternative Model 
14.4 Exercises 

III Semi-Numerical Algorithms 

15 Strassen’s Method 
15.1 Introduction to Matrix Multiplication 
15.2 A Divide and Conquer Approach 
15.3 Strassen’s Enhancement 
15.3.1 Seven Products 
15.3.2 Verification 
15.4 Exercises 

IV Graph Algorithms 

16 Introduction to Graphs 
16.1 Graphs — The Very Idea 
16.2 Graph Formal Definitions 
16.3 Graph Representations 
16.3.1 Mathematical Representations 
16.3.2 Computational Representations 

17 Shortest Paths 
17.1 Introduction to Shortest Paths 
17.2 The Bellman–Ford Algorithm 
17.2.1 A Recursive Formulation 
17.2.2 A Dynamic Programming Formulation 
17.2.3 Beyond Dynamic Programming
17.2.4 Throwing Caution to the Wind 

V Complexity Theory 

18 Complexity Theory Overview 
18.1 Introduction to Complexity Theory 
18.2 Formalizing the Class of Tractable Problems 
18.3 Thinking About P 
18.4 The Satisfiability Problem 
18.4.1 Propositional Formula Definition 
18.4.2 Truth Assignment Definitions 
18.4.3 Satisfiability Problem Formal Definition 
18.5 Another Class of Problems 
18.6 Exercises 

19 Additional NP-Complete Problems 
19.1 Introduction to Additional NP-Complete Problems 
19.1.1 Proving a Problem NP-Complete 
19.1.2 Initial Example 
19.2 3SAT 
19.3 Vertex Cover 
19.4 Exercises 

Index