Welcome to Week 4 of Analysis of Algorithms. The lecture for this week
introduces a completely different approach to studying properties of
discrete structures.
----------
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.
----------
Your assignment for this week, due at 11:59PM on
Thursday, March 2, 2017
is to write up and submit solutions to
Exercises 5.1, 5.3, 5.7, and 5.23
in "Analysis of Algorithms" (second edition). As usual, be sure to note
the errata listed on the booksite. Specifically, \rho^n should be
\rho^{-n} in the Corollary on page 250 (and on slide 46 in lecture 5).
Submit files named “A4-Q1.pdf” “A4-Q2.pdf” “A4-Q3.pdf” “A4-Q4.pdf" here:
http://dropbox.cs.princeton.edu/COS488_S2017/Assignment_4
RS