TABLE OF CONTENTS 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 Binary 70 Numbers 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 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-Three Recurrence 120 with OGFs 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 www.it-ebooks.infoT A B L E O F C O N T E N T S CŔōŜŠőŞ OŚő: AŚōŘťş ŕş śŒ AŘœśŞ ŕŠŔřş 3 1.1 Why Analyze an Algorithm? 3 1.2 Ļeory 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 CŔōŜŠőŞ Tţś: RőŏšŞŞőŚŏő RőŘōŠ ඦş 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 Binary 70 Numbers 2.7 General Divide-and-Conquer Recurrences 80 CŔōŜŠőŞ TŔŞőő: GőŚőŞōŠ ŕŚœ FšŚŏŠ ඦş 91 3.1 Ordinary Generating Functions 92 3.2 Exponential Generating Functions 97 3.3 Generating Function Solution of Recurrences 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-Ļree Recurrence 120 with OGFs 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 xv www.it-ebooks.info