Analytic Combinatorics, Part II

Product type
Logo Coursera (CC)
Provider rating: starstarstarstar_halfstar_border 7.2 Coursera (CC) has an average rating of 7.2 (out of 6 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. Part II introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.

About the Course

Analytic Combinatorics is based on formal methods for deriving functional relationships on generating functions and asymptotic analysis treating those functions as functions in the complex plane. Part II covers the symbolic method for defining generating functions immediately from combinatorial constructions, then develops methods for direct…

Read the complete description

Frequently asked questions

There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. Part II introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.

About the Course

Analytic Combinatorics is based on formal methods for deriving functional relationships on generating functions and asymptotic analysis treating those functions as functions in the complex plane. Part II covers the symbolic method for defining generating functions immediately from combinatorial constructions, then develops methods for directly deriving asymptotic results from those generating functions, using complex asymptotics, singularity analysis, saddle-point asymptotics, and limit laws. The course teaches the precept "if you can specify it, you can analyze it".

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 Combinatorial Structures and OGFs Lecture 2 Labelled Structures and EGFs Lecture 3 Combinatorial Parameters and MGFs Lecture 4 Complex Analysis, Rational and Meromorphic Asymptotics Lecture 5 Applications of Rational and Meromorphic Asymptotics Lecture 6 Singularity Analysis of Generating Functions Lecture 7 Applications of Singularity Analysis Lecture 8 Saddle-Point Asymptotics Lecture 9 Multivariate Asymptotics and Limit Laws Lecture 10 Mellin Transform Asymptotics

Recommended Background

You need basic familiarity with programming in Java and the algorithms and data structures from Algorithms,Part I, or equivalent experience/preparation in math and CS.

Suggested Readings

This course is based on the textbook Analytic Combinatorics by Flajolet and Sedgewick. The (free) web version of the textbook can be found at http://ac.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.

Provided by:

University: Princeton University

Instructor(s): Robert Sedgewick

There are no reviews yet.

    Share your review

    Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.

    There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.