Analysis of Algorithms Book

	Preface	v
Chapter 1	Analysis Basics	1
1.1	What is Analysis?	3
1.1.1	Input Classes	7
1.1.2	Space Complexity	9
1.1.3	Exercises	10
1.2	What to Count and Consider	10
1.2.1	Cases to Consider	11
1.2.2	Exercises	13
1.3	Mathematical Background	13
1.3.1	Logarithms	14
1.3.2	Binary Trees	15
1.3.3	Probabilities	15
1.3.4	Summations	16
1.3.5	Exercises	18
1.4	Rates of Growth	20
1.4.1	Classification of Growth	22
1.4.2	Exercises	23
1.5	Divide and Conquer Algorithms	24
1.5.1	Tournament Method	27
1.5.2	Lower Bounds	28
1.5.3	Exercises	31
1.6	Recurrence Relations	32
1.6.1	Exercises	37
1.7	Analyzing Programs	38
Chapter 2	Searching and Selection Algorithms	41
2.1	Sequential Search	43
2.1.1	Worst-Case Analysis	44
2.1.2	Average-Case Analysis	44
2.1.3	Exercises	46
2.2	Binary Search	46
2.2.1	Worst-Case Analysis	48
2.2.2	Average-Case Analysis	49
2.2.3	Exercises	52
2.3	Selection	53
2.3.1	Exercises	55
2.4	Programming Exercise	55
Chapter 3	Sorting Algorithms	57
3.1	Insertion Sort	59
3.1.1	Worst-Case Analysis	60
3.1.2	Average-Case Analysis	60
3.1.3	Exercises	62
3.2	Bubble Sort	63
3.2.1	Best-Case Analysis	64
3.2.2	Worst-Case Analysis	64
3.2.3	Average-Case Analysis	65
3.2.4	Exercises	67
3.3	Shellsort	68
3.3.1	Algorithm Analysis	70
3.3.2	The Effect of the Increment	71
3.3.3	Exercises	72
3.4	Radix Sort	73
3.4.1	Analysis	74
3.4.2	Exercises	76
3.5	Heapsort	77
3.5.1	Worst-Case Analysis	80
3.5.2	Average-Case Analysis	82
3.5.3	Exercises	83
3.6	Merge Sort	83
3.6.1	MergeLists Analysis	85
3.6.2	MergeSort Analysis	86
3.6.3	Exercises	88
3.7	Quicksort	89
3.7.1	Worst-Case Analysis	91
3.7.2	Average-Case Analysis	91
3.7.3	Exercises	94
3.8	External Polyphase Merge Sort	95
3.8.1	Number of Comparisons in Run Construction	99
3.8.2	Number of Comparisons in Run Merge	99
3.8.3	Number of Block Reads	100
3.8.4	Exercises	100
3.9	Additional Exercises	100
3.10	Programming Exercises	102
Chapter 4	Numeric Algorithms	105
4.1	Calculating Polynomials	107
4.1.1	Horner's Method	108
4.1.2	Preprocessed Coefficients	108
4.1.3	Exercises	111
4.2	Matrix Multiplication	112
4.2.1	Winograd's Matrix Multiplication	113
4.2.2	Strassen's Matrix Multiplication	115
4.2.3	Exercises	116
4.3	Linear Equations	116
4.3.1	Gauss-Jordan Method	117
4.3.2	Exercises	119
Chapter 5	Matching Algorithms	121
5.1	String Matching	122
5.1.1	Finite Automata	124
5.1.2	Knuth-Morris-Pratt Algorithm	125
5.1.3	Boyer-Moore Algorithm	128
5.1.4	Exercises	135
5.2	Approximate String Matching	136
5.2.1	Analysis	138
5.2.2	Exercises	139
5.3	Programming Exercises	139
Chapter 6	Graph Algorithms	141
6.1	Graph Background and Terminology	144
6.1.1	Terminology	145
6.1.2	Exercises	146
6.2	Data Structure Methods for Graphs	147
6.2.1	The Adjacency Matrix	148
6.2.2	The Adjacency List	149
6.2.3	Exercises	149
6.3	Depth-First and Breadth-First Traversal Algorithms	150
6.3.1	Depth-First Traversal	150
6.3.2	Breadth-First Traversal	151
6.3.3	Traversal Analysis	153
6.3.4	Exercises	154
6.4	Minimum Spanning Tree Algorithm	155
6.4.1	The Dijkstra-Prim Algorithm	155
6.4.2	The Kruskal Algorithm	159
6.4.3	Exercises	162
6.5	Shortest-Path Algorithm	163
6.5.1	Dijkstra's Algorithm	164
6.5.2	Exercises	167
6.6	Biconnected Component Algorithm	168
6.6.1	Exercises	171
6.7	Partitioning Sets	172
6.8	Programming Exercises	174
Chapter 7	Parallel Algorithms	177
7.1	Parallelism Introduction	178
7.1.1	Computer System Categories	179
7.1.2	Parallel Architectures	180
7.1.3	Principles for Parallelism Analysis	182
7.1.4	Exercises	183
7.2	The PRAM Model	183
7.2.1	Exercises	185
7.3	Simple Parallel Operations	185
7.3.1	Broadcasting Data in a CREW PRAM Model	186
7.3.2	Broadcasting Data in a EREW PRAM Model	186
7.3.3	Finding the Maximum Value in a List	187
7.3.4	Exercises	189
7.4	Parallel Searching	189
7.4.1	Exercises	191
7.5	Parallel Sorting	191
7.5.1	Linear Network Sort	191
7.5.2	Odd-Even Swap Sort	195
7.5.3	Other Parallel Sorts	196
7.5.4	Exercises	197
7.6	Parallel Numerical Algorithms	198
7.6.1	Matrix Multiplication on a Parallel Mesh	198
7.6.2	Matrix Multiplication in a CRCW PRAM Model	204
7.6.3	Solving Systems of Linear Equations with an SIMD Algorithm	205
7.6.4	Exercises	206
7.7	Parallel Graph Algorithms	207
7.7.1	Shortest-Path Parallel Algorithm	207
7.7.2	Minimum Spanning Tree Parallel Algorithm	209
7.7.3	Exercises	211
Chapter 8	Nondeterministic Algorithms	213
8.1	What is NP?	214
8.1.1	Problem Reductions	217
8.1.2	NP-Complete Problems	218
8.2	Typical NP Problems	220
8.2.1	Graph Coloring	220
8.2.2	Bin Packing	221
8.2.3	Backpack Problem	222
8.2.4	Subset Sum Problem	222
8.2.5	CNF-Satisfiability Problem	222
8.2.6	Job Scheduling Problem	223
8.2.7	Exercises	223
8.3	What Makes Something NP?	224
8.3.1	Is P = NP?	225
8.3.2	Exercises	226
8.4	Testing Possible Solutions	226
8.4.1	Job Scheduling	227
8.4.2	Graph Coloring	228
8.4.3	Exercises	229
Chapter 9	Other Algorithmic Techniques	231
9.1	Greedy Approximation Algorithms	232
9.1.1	Traveling Salesperson Approximations	233
9.1.2	Bin Packing Approximations	235
9.1.3	Backpack Approximation	236
9.1.4	Subset Sum Approximation	236
9.1.5	Graph Coloring Approximation	238
9.1.6	Exercises	239
9.2	Probabilistic Algorithms	240
9.2.1	Numerical Probabilistic Algorithms	240
9.2.2	Monte Carlo Algorithms	244
9.2.3	Las Vegas Algorithms	246
9.2.4	Sherwood Algorithms	249
9.2.5	Probabilistic Algorithm Comparison	250
9.2.6	Exercises	251
9.3	Dynamic Programming	252
9.3.1	Array-Based Methods	252
9.3.2	Dynamic Matrix Multiplication	255
9.3.3	Exercises	257
9.4	Programming Exercises	258
Appendix A	Random Number Table	259
Appendix B	Pseudorandom Number Generation	261
Appendix C	Results of Chapter Study Suggestion	265
Appendix D	References	279
	Index	285