text.skipToContent text.skipToNavigation
  1. Home
  2. Computer Science & IT
  3. Introduction to the Analysis of Algorithms, An

Introduction to the Analysis of Algorithms, An, 2nd edition

  • Robert Sedgewick
  • Philippe Flajolet

Published by Addison-Wesley Professional (January 18th 2013) - Copyright © 2013

2nd edition

Chosen format
View all
Introduction to the Analysis of Algorithms, An

ISBN-13: 9780321905758

Includes: Hardcover
Free delivery
$79.99

What's included

  • Hardcover

    You'll get a bound printed text.

Overview

The author makes instructor resources available at http://aofa.cs.princeton.edu/home/.

Table of contents

Chapter 1: 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 2: 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 Numbers 70

2.7 General Divide-and-Conquer Recurrences 80

 

Chapter 3: 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 with OGFs 120

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 4: 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 Algorithms 207

4.9 “Poisson” Examples from the Analysis of Algorithms 211

 

Chapter 5: 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 247

 

Chapter 6: Trees 257

6.1 Binary Trees 258

6.2 Forests and Trees 261

6.3 Combinatorial Equivalences to Trees and Binary Trees 264

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 R

For teachers

All the material you need to teach your courses.

Discover teaching material