Schedule Help Center Learn more.

Lectures will be released each Friday at 12:00 p.m. EST 

Overview

The video From Analysis of Algorithms to Analytic Combinatorics: A Journey with Philippe Flajolet is now available on the course website. It is an optional overview that tries to answer the question "What is Analytic Combinatorics" and to give some historical perspective. If you are completely new to the material, you might wish to skip this video or come back to it later on. Most of it is covered, at a much slower pace, later in the course.

Each lecture corresponds to a chapter in An Introduction to the Analysis of Algorithms, 2nd edition, so everyone is encouraged to study the corresponding chapter in conjunction with the lectures.

Week 1

We begin our course with an overview of the use of the scientific method for studying algorithm performance, one of the motivating application for analytic combinatorics.

Lecture 1: Analysis of Algorithms. We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.

Week 2

We survey basic mathematical tools that have been used for scientific studies for centuries and are still effective for the analysis of algorithms.

Lecture 2: Recurrences. We begin the course with an overview of recurrence relations, which provide us with a direct mathematical model for the analysis of algorithms. We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.

Week 3

We introduce classical approximation methods and then our main topic.

Lecture 3: Generating Functions. Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.

Week 4

We address two familiar and fundamental combinatorial structures and the use of analytic combinatorics to study them, including coverage of several applications.

Lecture 4: Asymptotics. Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.

Lecture 5: Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabelled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.

Week 5

We address two familiar and fundamental combinatorial structures and the use of analytic combinatorics to study them, including coverage of several applications.

Lecture 6: Trees. The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.

Lecture 7: Permutations. The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.

Week 6

We complete our survey of important combinatorial classes and applications in the analysis of algorithms.

Lecture 8: Strings and Tries. From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties and then introduce the trie, an essential and fundamental structure not found in classical combinatorics.

Lecture 9: Words and Mappings. We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems and their application to fundamental hashing algorithms. Functions from [1..N] to [1..N] are mappings, which have an interesting and intricate structure that we can study with analytic combinatorics.

Beyond

If you're interested in continuing, please sign up for Analytic Combinatorics, where we examine the methods and models that we have introduced in this course in much more detail with particular focus on classical combinatorics and on complex-analytic asymptotic methods.