An Introduction to the Analysis of Algorithms

Table of Contents......Page 16
1.1 Why Analyze an Algorithm?......Page 22
1.2 Theory of Algorithms......Page 25
1.3 Analysis of Algorithms......Page 32
1.4 Average-Case Analysis......Page 35
1.5 Example: Analysis of Quicksort......Page 37
1.6 Asymptotic Approximations......Page 46
1.7 Distributions......Page 49
1.8 Randomized Algorithms......Page 52
CHAPTER TWO: RECURRENCE RELATIONS......Page 60
2.1 Basic Properties......Page 62
2.2 First-Order Recurrences......Page 67
2.3 Nonlinear First-Order Recurrences......Page 71
2.4 Higher-Order Recurrences......Page 74
2.5 Methods for Solving Recurrences......Page 80
2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers......Page 89
2.7 General Divide-and-Conquer Recurrences......Page 99
CHAPTER THREE: GENERATING FUNCTIONS......Page 110
3.1 Ordinary Generating Functions......Page 111
3.2 Exponential Generating Functions......Page 116
3.3 Generating Function Solution of Recurrences......Page 120
3.4 Expanding Generating Functions......Page 130
3.5 Transformations with Generating Functions......Page 133
3.6 Functional Equations on Generating Functions......Page 136
3.7 Solving the Quicksort Median-of-Three Recurrence with OGFs......Page 139
3.8 Counting with Generating Functions......Page 142
3.9 Probability Generating Functions......Page 148
3.10 Bivariate Generating Functions......Page 151
3.11 Special Functions......Page 159
CHAPTER FOUR: ASYMPTOTIC APPROXIMATIONS......Page 170
4.1 Notation for Asymptotic Approximations......Page 172
4.2 Asymptotic Expansions......Page 179
4.3 Manipulating Asymptotic Expansions......Page 188
4.4 Asymptotic Approximations of Finite Sums......Page 195
4.5 Euler-Maclaurin Summation......Page 198
4.6 Bivariate Asymptotics......Page 206
4.7 Laplace Method......Page 222
4.8 “Normal” Examples from the Analysis of Algorithms......Page 226
4.9 “Poisson” Examples from the Analysis of Algorithms......Page 230
CHAPTER FIVE: ANALYTIC COMBINATORICS......Page 238
5.1 Formal Basis......Page 239
5.2 Symbolic Method for Unlabelled Classes......Page 240
5.3 Symbolic Method for Labelled Classes......Page 248
5.4 Symbolic Method for Parameters......Page 260
5.5 Generating Function Coefficient Asymptotics......Page 266
CHAPTER SIX: TREES......Page 276
6.1 Binary Trees......Page 277
6.2 Forests and Trees......Page 280
6.3 Combinatorial Equivalences to Trees and Binary Trees......Page 283
6.4 Properties of Trees......Page 291
6.5 Examples of Tree Algorithms......Page 296
6.6 Binary Search Trees......Page 300
6.7 Average Path Length in Catalan Trees......Page 306
6.8 Path Length in Binary Search Trees......Page 312
6.9 Additive Parameters of Random Trees......Page 316
6.10 Height......Page 321
6.11 Summary of Average-Case Results on Properties of Trees......Page 329
6.12 Lagrange Inversion......Page 331
6.13 Rooted Unordered Trees......Page 334
6.14 Labelled Trees......Page 346
6.15 Other Types of Trees......Page 350
CHAPTER SEVEN: PERMUTATIONS......Page 364
7.1 Basic Properties of Permutations......Page 366
7.2 Algorithms on Permutations......Page 374
7.3 Representations of Permutations......Page 377
7.4 Enumeration Problems......Page 385
7.5 Analyzing Properties of Permutations with CGFs......Page 391
7.6 Inversions and Insertion Sorts......Page 403
7.7 Left-to-Right Minima and Selection Sort......Page 412
7.8 Cycles and In Situ Permutation......Page 420
7.9 Extremal Parameters......Page 425
CHAPTER EIGHT: STRINGS AND TRIES......Page 434
8.1 String Searching......Page 435
8.2 Combinatorial Properties of Bitstrings......Page 439
8.3 Regular Expressions......Page 451
8.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm......Page 456
8.5 Context-Free Grammars......Page 460
8.6 Tries......Page 467
8.7 Trie Algorithms......Page 472
8.8 Combinatorial Properties of Tries......Page 478
8.9 Larger Alphabets......Page 484
CHAPTER NINE: WORDS AND MAPPINGS......Page 492
9.1 Hashing with Separate Chaining......Page 493
9.2 The Balls-and-Urns Model and Properties of Words......Page 495
9.3 Birthday Paradox and Coupon Collector Problem......Page 504
9.4 Occupancy Restrictions and Extremal Parameters......Page 514
9.5 Occupancy Distributions......Page 520
9.6 Open Addressing Hashing......Page 528
9.7 Mappings......Page 538
9.8 Integer Factorization and Mappings......Page 551
List of Theorems......Page 562
List of Tables......Page 564
List of Figures......Page 566
A......Page 570
B......Page 571
C......Page 573
D......Page 575
E......Page 576
F......Page 577
G......Page 578
I......Page 579
L......Page 580
M......Page 581
N......Page 582
P......Page 583
R......Page 585
S......Page 587
T......Page 589
U......Page 590
Z......Page 591