Analytic Combinatorics, Part I

apply

Next Session:

Feb 8th 2013 (5 weeks long)

Workload: 6-8 hours/week 

About the Course

Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the scientific analysis of algorithms in computer science and for the study of scientific models in many other disciplines, including probability theory, statistical physics, computational biology and information theory. Part I of this course covers recurrence relations, generating functions, asymptotics, and fundamental structures such as trees, permutations, strings, tries, words, and mappings, in the context of applications to the analysis of algorithms.

About the Instructor(s)

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton, where he was the founding chair of the Department of Computer Science. He received the Ph.D. degree from Stanford University, in 1975. Prof. Sedgewick also served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Palo Alto, CA, Institute for Defense Analyses, Princeton, NJ, and INRIA, Rocquencourt, France. He is a member of the board of directors of Adobe Systems. Prof. Sedgewick's interests are in analytic combinatorics, algorithm design, the scientific analysis of algorithms, curriculum development, and innovations in the dissemination of knowledge. He has published widely in these areas and is the author of several books.

Course Syllabus

 Lecture  1  Analysis of Algorithms

 Lecture  2  Recurrences

 Lecture  3  Solving recurrences with GFs

 Lecture  4  Asymptotics

 Lecture  5  The symbolic method

 Lecture  6  Trees

 Lecture  7  Permutations

 Lecture  8  Strings and Tries

 Lecture  9  Words and Mappings

Recommended Background

Math through calculus, CS through algorithms recommended.

Suggested Readings

This course is based on the textbook An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet. You can find (free) web materials associated with the textbook at http://aofa.cs.princeton.edu/home.

Course Format

There will be two lectures (80 minutes each) and a problem set each week. There will also be a final exam.

FAQ

• Does Princeton award credentials or reports regarding my work in this course?
  No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.