Description 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. This course combines motivation for the study of the field with an introduction to underlying techniques, by covering as applications the analysis of numerous fundamental algorithms and data structures from computer science. The second half of the course introduces Analytic Combinatorics, starting from basic principles.
Prerequisites COS 226 and COS 340 or equivalent background in computer science and mathematics.
 |
Robert Sedgewick Office hours: TBA |
 |
Jérémie Lumbroso Office hours: TBA |
 |
Required Reading (1st half) Analysis of Algorithms, 2nd ed. Sedgewick and FlajoletAddison-Wesley, 2013 ISBN 0-321-90575-X [ Amazon · Inform IT ]. |
 |
Online Resources (1st half) Analysis of Algorithms booksite https://aofa.cs.princeton.edu |
|---|---|---|---|
 |
Required Reading (2nd half) Analytic Combinatorics, by Flajolet and SedgewickCambridge University Press, 2009 ISBN 978-0-521-89806-5. [ Amazon ]. |
 |
Online Resources (2nd half) Analytic Combinatorics booksite https://ac.cs.princeton.edu |
Philippe Flajolet (posthumously) and Robert Sedgewick won the American Mathematical Society's 2019 Leroy P. Steele Prize for Mathematical Exposition for Analytic Combinatorics.
Lectures are available as studio-produced videos for students to watch at their own pace (and rewatch to clear up any confusion and tostudy for review problems), two lectures per week. The first lecture of each half is intended to place the (mathematical) course content in a CS context by considering a CS application with wide impact.
Online course materials
including lecture videos, lecture slides, assignments, web exercises, and other resources
are accessible through the "Online Course Materials" tabs on the booksites for
Analysis of Algorithms
for the first half of the course
and Analytic Combinatorics
for the second half of the course.
Synchronization will be via e-mail, the Ed
discussion platform, and timely feedback on your written work.
Each Friday, you will get an e-mail with a description of the online
lectures you will watch and the problems assigned for the week.
If you have a question, the best way to get a quick response (and also maybe
help your classmates) is to post it on Ed. Feel free to send an e-mail if you feel
that will not work for you, and we will respond promptly.
Your grade for the course will be based on the following components:
Weekly Problem Sets
are posted each Friday (except the first
one, posted on the first day of class) and due at 11:59PM the
following Thursday. You may work together in groups of two or three
(no larger) and discuss approaches to solving problems, but you must
document such collaboration and each student must prepare all
submitted solutions without assistance from anyone.
Please pay attention to the instructions for submitting assignments
to avoid snafus in our grading work flow.
Review Problem Sets will consist of one question per lecture, to assess understanding of basic concepts. Open-book, open-everything. You must work alone to solve these problems.
Questions and Answers have proven to a very effective vehicle for learning this material. Details and examples will be provided.
To be fair to people who sumbit on time and to minimize disruption to our grading workflow, we need to deduct points at our discretion for late submissions, but it is always better to submit than to not submit. If you need extra time due to particular extenuating circumstances, just ask.
Copyright.
All rights reserved. None of this material may
be reproduced, stored in a retrieval system, or transmitted,
in any form or by any means, electronic, mechanical, photocopying,
recording or otherwise without prior written permission.
Permission is granted to instructors who adopt
the textbooks to use this material in
conjunction with their course.