App 下载
注册
登录
|
搜索
正在搜索中...
首页
我的书架
我的主页
我的收藏
我的书评
《算法分析导论（第2版）（英文版）》全面介绍了算法的数学分析中所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课
……
[ 展开全部 ]
题（包括算法和数据结构）。《算法分析导论（第2版）（英文版）》的重点是“平均情况”或“概率性”分析，书中也论述了“最差情况”或“复杂性”分析所需的基本数学工具。 《算法分析导论（第2版）（英文版）》第 1 版为行业内的经典著作，本版不仅对书中图片和代码进行了更新，还补充了新章节。全书共 9 章，第 1 章是导论 ；第 2~5 章介绍数学方法 ；第 6~9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，《算法分析导论（第2版）（英文版）》特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习。 《算法分析导论（第2版）（英文版）》适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员和爱好者学习参考。
[ 收起 ]
作者：[美]Robert Sedgewick（罗伯特•塞奇威克） [美]Philippe Flajolet（菲利普•弗拉若莱）
出版社：电子工业出版社
定价：128.00元
ISBN：7121260700
给个评价
做个书摘
书摘 (21 )
评价 (1 )
查看所有书摘
按目录显示书摘
只显示目录
T A B L E O F C O N T E N T S
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter One: Analysis of Algorithms 3
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.1 Why Analyze an Algorithm? 3
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.2 Theory of Algorithms 6
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.3 Analysis of Algorithms 13
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.4 Average-Case Analysis 16
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.5 Example: Analysis of Quicksort 18
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.6 Asymptotic Approximations 27
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.7 Distributions 30
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
1.8 Randomized Algorithms 33
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Two: Recurrence Relations 41
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.1 Basic Properties 43
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.2 First-Order Recurrences 48
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.3 Nonlinear First-Order Recurrences 52
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.4 Higher-Order Recurrences 55
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.5 Methods for Solving Recurrences 61
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.6 Binary Divide-and-Conquer Recurrences and Bina
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
2.7 General Divide-and-Conquer Recurrences 80
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Three: Generating Functions 91
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.1 Ordinary Generating Functions 92
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.2 Exponential Generating Functions 97
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.3 Generating Function Solution of Recurrences 10
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.4 Expanding Generating Functions 111
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.5 Transformations with Generating Functions 114
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.6 Functional Equations on Generating Functions 1
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.7 Solving the Quicksort Median-of-Three Recurren
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.8 Counting with Generating Functions 123
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.9 Probability Generating Functions 129
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.10 Bivariate Generating Functions 132
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
3.11 Special Functions 140
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Four: Asymptotic Approximations 151
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.1 Notation for Asymptotic Approximations 153
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.2 Asymptotic Expansions 160
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.3 Manipulating Asymptotic Expansions 169
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.4 Asymptotic Approximations of Finite Sums 176
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.5 Euler-Maclaurin Summation 179
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.6 Bivariate Asymptotics 187
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.7 Laplace Method 203
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.8 “Normal” Examples from the Analysis of Algorit
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
4.9 “Poisson” Examples from the Analysis of Algori
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Five: Analytic Combinatorics 219
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
5.1 Formal Basis 220
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
5.2 Symbolic Method for Unlabelled Classes 221
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
5.3 Symbolic Method for Labelled Classes 229
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
5.4 Symbolic Method for Parameters 241
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
5.5 Generating Function Coefficient Asymptotics 24
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Six: Trees 257
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.1 Binary Trees 258
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.2 Forests and Trees 261
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.3 Combinatorial Equivalences to Trees and Binary
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.4 Properties of Trees 272
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.5 Examples of Tree Algorithms 277
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.6 Binary Search Trees 281
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.7 Average Path Length in Catalan Trees 287
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.8 Path Length in Binary Search Trees 293
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.9 Additive Parameters of Random Trees 297
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.10 Height 302
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.11 Summary of Average-Case Results on Properties
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.12 Lagrange Inversion 312
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.13 Rooted Unordered Trees 315
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.14 Labelled Trees 327
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
6.15 Other Types of Trees 331
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Seven: Permutations 345
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.1 Basic Properties of Permutations 347
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.2 Algorithms on Permutations 355
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.3 Representations of Permutations 358
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.4 Enumeration Problems 366
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.5 Analyzing Properties of Permutations with CGFs
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.6 Inversions and Insertion Sorts 384
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.7 Left-to-Right Minima and Selection Sort 393
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.8 Cycles and In Situ Permutation 401
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
7.9 Extremal Parameters 406
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Eight: Strings and Tries 415
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.1 String Searching 416
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.2 Combinatorial Properties of Bitstrings 420
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.3 Regular Expressions 432
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.4 Finite-State Automata and the Knuth-Morris-Pra
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.5 Context-Free Grammars 441
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.6 Tries 448
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.7 Trie Algorithms 453
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.8 Combinatorial Properties of Tries 459
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
8.9 Larger Alphabets 465
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Chapter Nine: Words and Mappings 473
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.1 Hashing with Separate Chaining 474
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.2 The Balls-and-Urns Model and Properties of Wor
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.3 Birthday Paradox and Coupon Collector Problem
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.4 Occupancy Restrictions and Extremal Parameters
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.5 Occupancy Distributions 501
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.6 Open Addressing Hashing 509
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.7 Mappings 519
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
9.8 Integer Factorization and Mappings 532
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
List of Theorems 543
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
List of Tables 545
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
List of Figures 547
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
Index 551
还没有人在此章节添加过书摘，赶紧来抢第一吧！
在此章节添加书摘
导购链接
×
做书摘
文字书摘
读图识字
至少还需要输入
10
字
保存原图片为书摘
上传图片
识别
最多输入
500
个字
上传图片
重新上传
写点笔记吧
至少还需要输入
10
字
章节（选填）
T A B L E O F C O N T E N T S
Chapter One: Analysis of Algorithms 3
1.1 Why Analyze an Algorithm? 3
1.2 Theory of Algorithms 6
1.3 Analysis of Algorithms 13
1.4 Average-Case Analysis 16
1.5 Example: Analysis of Quicksort 18
1.6 Asymptotic Approximations 27
1.7 Distributions 30
1.8 Randomized Algorithms 33
Chapter Two: Recurrence Relations 41
2.1 Basic Properties 43
2.2 First-Order Recurrences 48
2.3 Nonlinear First-Order Recurrences 52
2.4 Higher-Order Recurrences 55
2.5 Methods for Solving Recurrences 61
2.6 Binary Divide-and-Conquer Recurrences and Bina
2.7 General Divide-and-Conquer Recurrences 80
Chapter Three: Generating Functions 91
3.1 Ordinary Generating Functions 92
3.2 Exponential Generating Functions 97
3.3 Generating Function Solution of Recurrences 10
3.4 Expanding Generating Functions 111
3.5 Transformations with Generating Functions 114
3.6 Functional Equations on Generating Functions 1
3.7 Solving the Quicksort Median-of-Three Recurren
3.8 Counting with Generating Functions 123
3.9 Probability Generating Functions 129
3.10 Bivariate Generating Functions 132
3.11 Special Functions 140
Chapter Four: Asymptotic Approximations 151
4.1 Notation for Asymptotic Approximations 153
4.2 Asymptotic Expansions 160
4.3 Manipulating Asymptotic Expansions 169
4.4 Asymptotic Approximations of Finite Sums 176
4.5 Euler-Maclaurin Summation 179
4.6 Bivariate Asymptotics 187
4.7 Laplace Method 203
4.8 “Normal” Examples from the Analysis of Algorit
4.9 “Poisson” Examples from the Analysis of Algori
Chapter Five: Analytic Combinatorics 219
5.1 Formal Basis 220
5.2 Symbolic Method for Unlabelled Classes 221
5.3 Symbolic Method for Labelled Classes 229
5.4 Symbolic Method for Parameters 241
5.5 Generating Function Coefficient Asymptotics 24
Chapter Six: Trees 257
6.1 Binary Trees 258
6.2 Forests and Trees 261
6.3 Combinatorial Equivalences to Trees and Binary
6.4 Properties of Trees 272
6.5 Examples of Tree Algorithms 277
6.6 Binary Search Trees 281
6.7 Average Path Length in Catalan Trees 287
6.8 Path Length in Binary Search Trees 293
6.9 Additive Parameters of Random Trees 297
6.10 Height 302
6.11 Summary of Average-Case Results on Properties
6.12 Lagrange Inversion 312
6.13 Rooted Unordered Trees 315
6.14 Labelled Trees 327
6.15 Other Types of Trees 331
Chapter Seven: Permutations 345
7.1 Basic Properties of Permutations 347
7.2 Algorithms on Permutations 355
7.3 Representations of Permutations 358
7.4 Enumeration Problems 366
7.5 Analyzing Properties of Permutations with CGFs
7.6 Inversions and Insertion Sorts 384
7.7 Left-to-Right Minima and Selection Sort 393
7.8 Cycles and In Situ Permutation 401
7.9 Extremal Parameters 406
Chapter Eight: Strings and Tries 415
8.1 String Searching 416
8.2 Combinatorial Properties of Bitstrings 420
8.3 Regular Expressions 432
8.4 Finite-State Automata and the Knuth-Morris-Pra
8.5 Context-Free Grammars 441
8.6 Tries 448
8.7 Trie Algorithms 453
8.8 Combinatorial Properties of Tries 459
8.9 Larger Alphabets 465
Chapter Nine: Words and Mappings 473
9.1 Hashing with Separate Chaining 474
9.2 The Balls-and-Urns Model and Properties of Wor
9.3 Birthday Paradox and Coupon Collector Problem
9.4 Occupancy Restrictions and Extremal Parameters
9.5 Occupancy Distributions 501
9.6 Open Addressing Hashing 509
9.7 Mappings 519
9.8 Integer Factorization and Mappings 532
List of Theorems 543
List of Tables 545
List of Figures 547
Index 551
页码（选填）
这本书已经添加了这些章节，请勾选或者新建你的书摘所属的章节
add
up
down
remove
T A B L E O F C O N T E N T S
Chapter One: Analysis of Algorithms 3
1.1 Why Analyze an Algorithm? 3
1.2 Theory of Algorithms 6
1.3 Analysis of Algorithms 13
1.4 Average-Case Analysis 16
1.5 Example: Analysis of Quicksort 18
1.6 Asymptotic Approximations 27
1.7 Distributions 30
1.8 Randomized Algorithms 33
Chapter Two: Recurrence Relations 41
2.1 Basic Properties 43
2.2 First-Order Recurrences 48
2.3 Nonlinear First-Order Recurrences 52
2.4 Higher-Order Recurrences 55
2.5 Methods for Solving Recurrences 61
2.6 Binary Divide-and-Conquer Recurrences and Bina
2.7 General Divide-and-Conquer Recurrences 80
Chapter Three: Generating Functions 91
3.1 Ordinary Generating Functions 92
3.2 Exponential Generating Functions 97
3.3 Generating Function Solution of Recurrences 10
3.4 Expanding Generating Functions 111
3.5 Transformations with Generating Functions 114
3.6 Functional Equations on Generating Functions 1
3.7 Solving the Quicksort Median-of-Three Recurren
3.8 Counting with Generating Functions 123
3.9 Probability Generating Functions 129
3.10 Bivariate Generating Functions 132
3.11 Special Functions 140
Chapter Four: Asymptotic Approximations 151
4.1 Notation for Asymptotic Approximations 153
4.2 Asymptotic Expansions 160
4.3 Manipulating Asymptotic Expansions 169
4.4 Asymptotic Approximations of Finite Sums 176
4.5 Euler-Maclaurin Summation 179
4.6 Bivariate Asymptotics 187
4.7 Laplace Method 203
4.8 “Normal” Examples from the Analysis of Algorit
4.9 “Poisson” Examples from the Analysis of Algori
Chapter Five: Analytic Combinatorics 219
5.1 Formal Basis 220
5.2 Symbolic Method for Unlabelled Classes 221
5.3 Symbolic Method for Labelled Classes 229
5.4 Symbolic Method for Parameters 241
5.5 Generating Function Coefficient Asymptotics 24
Chapter Six: Trees 257
6.1 Binary Trees 258
6.2 Forests and Trees 261
6.3 Combinatorial Equivalences to Trees and Binary
6.4 Properties of Trees 272
6.5 Examples of Tree Algorithms 277
6.6 Binary Search Trees 281
6.7 Average Path Length in Catalan Trees 287
6.8 Path Length in Binary Search Trees 293
6.9 Additive Parameters of Random Trees 297
6.10 Height 302
6.11 Summary of Average-Case Results on Properties
6.12 Lagrange Inversion 312
6.13 Rooted Unordered Trees 315
6.14 Labelled Trees 327
6.15 Other Types of Trees 331
Chapter Seven: Permutations 345
7.1 Basic Properties of Permutations 347
7.2 Algorithms on Permutations 355
7.3 Representations of Permutations 358
7.4 Enumeration Problems 366
7.5 Analyzing Properties of Permutations with CGFs
7.6 Inversions and Insertion Sorts 384
7.7 Left-to-Right Minima and Selection Sort 393
7.8 Cycles and In Situ Permutation 401
7.9 Extremal Parameters 406
Chapter Eight: Strings and Tries 415
8.1 String Searching 416
8.2 Combinatorial Properties of Bitstrings 420
8.3 Regular Expressions 432
8.4 Finite-State Automata and the Knuth-Morris-Pra
8.5 Context-Free Grammars 441
8.6 Tries 448
8.7 Trie Algorithms 453
8.8 Combinatorial Properties of Tries 459
8.9 Larger Alphabets 465
Chapter Nine: Words and Mappings 473
9.1 Hashing with Separate Chaining 474
9.2 The Balls-and-Urns Model and Properties of Wor
9.3 Birthday Paradox and Coupon Collector Problem
9.4 Occupancy Restrictions and Extremal Parameters
9.5 Occupancy Distributions 501
9.6 Open Addressing Hashing 509
9.7 Mappings 519
9.8 Integer Factorization and Mappings 532
List of Theorems 543
List of Tables 545
List of Figures 547
Index 551
×
添加一个书摘本
搜索创建书摘本
搜索
正在搜索...
不对，换一下
书名
作者
出版社
备注
ISBN
*
*
T A B L E O F C O N T E N T S
Chapter One: Analysis of Algorithms 3
1.1 Why Analyze an Algorithm? 3
1.2 Theory of Algorithms 6
1.3 Analysis of Algorithms 13
1.4 Average-Case Analysis 16
1.5 Example: Analysis of Quicksort 18
1.6 Asymptotic Approximations 27
1.7 Distributions 30
1.8 Randomized Algorithms 33
Chapter Two: Recurrence Relations 41
2.1 Basic Properties 43
2.2 First-Order Recurrences 48
2.3 Nonlinear First-Order Recurrences 52
2.4 Higher-Order Recurrences 55
2.5 Methods for Solving Recurrences 61
2.6 Binary Divide-and-Conquer Recurrences and Bina
2.7 General Divide-and-Conquer Recurrences 80
Chapter Three: Generating Functions 91
3.1 Ordinary Generating Functions 92
3.2 Exponential Generating Functions 97
3.3 Generating Function Solution of Recurrences 10
3.4 Expanding Generating Functions 111
3.5 Transformations with Generating Functions 114
3.6 Functional Equations on Generating Functions 1
3.7 Solving the Quicksort Median-of-Three Recurren
3.8 Counting with Generating Functions 123
3.9 Probability Generating Functions 129
3.10 Bivariate Generating Functions 132
3.11 Special Functions 140
Chapter Four: Asymptotic Approximations 151
4.1 Notation for Asymptotic Approximations 153
4.2 Asymptotic Expansions 160
4.3 Manipulating Asymptotic Expansions 169
4.4 Asymptotic Approximations of Finite Sums 176
4.5 Euler-Maclaurin Summation 179
4.6 Bivariate Asymptotics 187
4.7 Laplace Method 203
4.8 “Normal” Examples from the Analysis of Algorit
4.9 “Poisson” Examples from the Analysis of Algori
Chapter Five: Analytic Combinatorics 219
5.1 Formal Basis 220
5.2 Symbolic Method for Unlabelled Classes 221
5.3 Symbolic Method for Labelled Classes 229
5.4 Symbolic Method for Parameters 241
5.5 Generating Function Coefficient Asymptotics 24
Chapter Six: Trees 257
6.1 Binary Trees 258
6.2 Forests and Trees 261
6.3 Combinatorial Equivalences to Trees and Binary
6.4 Properties of Trees 272
6.5 Examples of Tree Algorithms 277
6.6 Binary Search Trees 281
6.7 Average Path Length in Catalan Trees 287
6.8 Path Length in Binary Search Trees 293
6.9 Additive Parameters of Random Trees 297
6.10 Height 302
6.11 Summary of Average-Case Results on Properties
6.12 Lagrange Inversion 312
6.13 Rooted Unordered Trees 315
6.14 Labelled Trees 327
6.15 Other Types of Trees 331
Chapter Seven: Permutations 345
7.1 Basic Properties of Permutations 347
7.2 Algorithms on Permutations 355
7.3 Representations of Permutations 358
7.4 Enumeration Problems 366
7.5 Analyzing Properties of Permutations with CGFs
7.6 Inversions and Insertion Sorts 384
7.7 Left-to-Right Minima and Selection Sort 393
7.8 Cycles and In Situ Permutation 401
7.9 Extremal Parameters 406
Chapter Eight: Strings and Tries 415
8.1 String Searching 416
8.2 Combinatorial Properties of Bitstrings 420
8.3 Regular Expressions 432
8.4 Finite-State Automata and the Knuth-Morris-Pra
8.5 Context-Free Grammars 441
8.6 Tries 448
8.7 Trie Algorithms 453
8.8 Combinatorial Properties of Tries 459
8.9 Larger Alphabets 465
Chapter Nine: Words and Mappings 473
9.1 Hashing with Separate Chaining 474
9.2 The Balls-and-Urns Model and Properties of Wor
9.3 Birthday Paradox and Coupon Collector Problem
9.4 Occupancy Restrictions and Extremal Parameters
9.5 Occupancy Distributions 501
9.6 Open Addressing Hashing 509
9.7 Mappings 519
9.8 Integer Factorization and Mappings 532
List of Theorems 543
List of Tables 545
List of Figures 547
Index 551