Syllabus Help Center Learn more.

Description.  An introduction to analytic combinatorics in the context of applications in the analysis of algorithms. Basic coverage of recurrences, generating functions, and asymptotics leads to an introduction to labelled and unlabelled combinatorial classes. Then we survey trees, permutations, strings and tries, and words and mappings, with applications drawn from the study of widely-used algorithms.

Prerequisites. First-year calculus, though the more experience in mathematics, the better. First-year programming, though familiarity with Java and a second-year algorithms course is better preparation.

Lectures. There are two lectures (about 75 minutes each) per week (just one the first week). Each lecture is broken up into about 4–6 segments.

Readings. Our textbook is the basic reference for the material we will be covering. Although the lectures are designed to be self-contained, most students will be best served by also studying the associated material in the textbook.

• An Introduction to the Analysis of Algorithms, 2nd Edition by Robert Sedgewick and Philippe Flajolet, Addison-Wesley Professional, 2013, ISBN-13: 978-0-321-90575-8.

Addison-Wesley is offering Coursera students a 35% discount when purchased from informIT. To receive the discount, enter the code COURSERA during checkout. Our booksite is open to everyone and contains a wealth of supplementary information, including synopses of the textbook, answers to some exercises, code, and other resources.

Exercises. Three or four exercises from the book are associated with each lecture. These are for self-assessment and to focus discussion in the forums. Solutions will be posted on the booksite.

Discussion forums. Please be sure to make use of the discussion forums if you need help, and please contribute to the forums if you think that you can provide help. Such forums have proven to be an important and fun part of the online course experience. Staff members will monitor these forums.

Copyright. All rights reserved. All video recordings, lecture slides, assessments and other materials made available in connection with this course are subject to copyright protection and may be used only for private study by persons who are enrolled in this course. Any other use of these materials must be with the express, written permission of Robert Sedgewick and Kevin Wayne.

Certificates. No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

Credits. I am grateful to Daniel Kearns, Lance Herrington, Laura Shaddock, and Jeffrey Himpele for their help in producing this course.