Table of Contents
Preface v
Chapter 1 Introduction 1
1.1 Algorithm 1
1.2 Another definition 1
1.3 Analyzing the performance of algorithms 1
1.4 Growth of the functions 2
1.5 Asymptotic notations 2
1.5.1 The O (big oh) notation 3
1.5.2 The ω notation 4
1.5.3 The θ notation 5
1.6 Recurrence relation 8
1.6.1 Linear recurrence relation 8
1.6.2 Solution of homogeneous recurrence relation 8
1.6.3 Solution to nonhomogeneous linear recurrence relation 10
1.7 Divide and conquer relations 12
1.7.1 Solution to DAC recurrence relation 12
1.7.2 The recursion tree method 13
1.7.3 The substitution method 14
1.7.4 Change of variable method 17
1.8 Master's theorem 17
Problem set 20
Chapter 2 Sorting techniques 23
2.1 Sorting 23
2.2 Insertion sort 23
2.2.1 Analysis of insertion sort 24
2.3 Quick sort 25
2.3.1 DAC approach 26
2.3.2 Analysis of quick sort 28
2.4 Merge sort 29
2.4.1 Analysis of merge sort 31
2.5 Heap sort 32
2.5.1 Analysis of Heapify 35
2.5.2 Heap sort 35
2.5.3 Analysis of heap sort 35
2.6 Sorting in linear time 35
2.7 Counting sort 36
2.7.1 Analysis of counting sort 37
2.8 Radix sort 38
2.8.1 Analysis of radix sort 38
2.9 Bucket sort 38
2.9.1 Analysis of bucket sort 39
2.9.2 Binomial distribution 40
Problem set 41
Chapter 3 Algorithm design techniques 43
3.1 Greedy approach 43
3.1.1 Traveling salesman problem 43
3.1.2 Fractional knapsack problem 44
3.2 Backtracking 46
3.2.1 Hamiltonian cycle 47
3.2.2 8-queen problem 48
3.3 Dynamic programming 51
3.3.1 0/1 knapsack problem 52
3.3.2 The traveling salesman problem 53
3.3.3 Chain matrix multiplication 55
3.3.4 Optimal binary search tree 57
3.4 Branch-and-bound technique 59
3.4.1 Assignment problem 60
3.4.2 Knapsack problem 61
3.5 Amortized analysis 62
3.5.1 Aggregate method 62
3.5.2 The potential method 63
3.6 Order statistics 65
Problem set 67
Chapter 4 Advanced graph algorithm 69
4.1 Introduction 69
4.1.1 Terminology 69
4.2 The graph search techniques 70
4.2.1 Breadth first search 70
4.2.2 Depth first search 72
4.3 Spanning tree 74
4.3.1 Kruskal's algorithm 75
4.3.2 Prim's algorithm 76
4.4 Shortest path algorithm 77
4.4.1 Warhsall's algorithm 77
4.4.2 Floyd Warshall's algorithm 80
4.4.3 Dijkstra algorithm 82
4.4.4 Bellman-Ford algorithm 83
4.5 Maximum flow 89
4.5.1 Maximum flow and minimum cut 90
4.5.2 Ford Fulkerson method 91
Problem set 94
Chapter 5 Number theory, classification of problems, and random algorithms 97
5.1 Division theorem 97
5.1.1 Common divisor and greatest common divisor 97
5.2 Chinese remainder theorem 98
5.3 Matrix operations 100
5.3.1 Strassen's matrix multiplication 100
5.3.2 Divide and conquer for matrix multiplication 101
5.3.3 Strassen's multiplication 102
5.4 Pattern matching 103
5.4.1 The Naive algorithm 103
5.4.2 The Rabin-Karp algorithm 104
5.5 P and NP class problem 107
5.5.1 Reducibility 107
5.5.2 NP complete problem 107
5.6 Approximation algorithms 108
5.6.1 Relative error 108
5.6.2 Approximation algorithm for TSP 108
5.6.3 The vertex cover problem 109
5.7 Deterministic and randomized algorithm 111
5.7.1 The nut and bolt problem 112
5.8 Computational geometry 112
5.9 The convex hull 113
5.9.1 Counterclockwise and clockwise 114
5.9.2 Finding whether two line segments intersect 114
5.10 Class P problems 116
5.10.1 NP (nondeterministic Polynomial Time) Problems 116
5.10.2 Any problem in P is also in NP 116
5.10.3 NP Hard Problems 116
5.10.4 NP Complete 117
5.10.5 Halting Problem for Deterministic Algorithms 117
5.10.6 The satisfiability problem 117
5.11 Clique 118
5.11.1 Clique Decision Problem 118
5.11.2 Non-Deterministic Algorithm for Clique Decision Algorithm 118
Problem set 120
Chapter 6 Tree and heaps 121
6.1 Red-Black Tree 121
6.2 Operations on RBT 122
6.2.1 Rotation 122
6.2.2 Insertion 123
6.2.3 Deletion 126
6.3 B-tree 127
6.3.1 Searching key k in B-tree 128
6.4 Binomial heap 130
6.4.1 Binomial heap 131
6.5 Fibonacci heap 135
6.5.1 Operation on Fibonacci heap 136
Problem set 138
Chapter 7 Lab session 141
Appendices 141
Further reading 165
Index 167
