**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 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 Faculty Office hours: by appointment anytime Wednesday , CS 319. |
Jérémie Lumbroso Faculty Office hours: Tuesday, 3–4, CS 209. |

Required Reading (1st half)Analysis of Algorithms, 2nd EditionRobert Sedgewick and Philippe Flajolet Addison-Wesley, 2013 ISBN 0-321-90575-X [ Amazon · Inform IT ]. |
Required Reading (2nd half)Analytic Combinatorics,by Philippe Flajolet and Robert Sedgewick Cambridge University Press, 2009 ISBN 978-0-521-89806-5. [ Amazon ]. |

**Lectures** Available as studio-produced videos for students to watch at their own pace (and rewatch to clear up any confusion and to study for exams), two lectures per week. *The first lecture will be a live lecture (no videos available)* that places the course content in a CS context by considering a CS application with wide impact. Anyone with an interest in learning what analytic combinatorics is all about is welcome to attend (Monday, February 6, Louis A. Simpson International Building, Meeting Room A71, 3:00-4:20).

**Class Meetings** Wednesdays 3:00–4:20, Louis A. S. A71. For exams, exam and assignment preparation and postmortem, and enrichment as appropriate. Except for exams and the first meeting, class meetings will normally last less than an hour and are optional. The first lecture is a live lecture on Monday, February 6; otherwise we will not meet on Mondays.

**Online course materials**
Lecture videos,
lecture slides,
assignments, and
other resources
for the first half of the course are accessible through
Analysis of Algorithms
booksite. After the break, these resources for the second half of the course
will be available on the
Analytic Combinatorics website. The
"Online Course Materials" tab on the booksites is another path to these resources. The lecture videos for *Analysis of Algorithms* are accessible only on campus—if you want off-campus access, learn about VPN, or purchase access
here.

Your grade for the course will be based on the following components:

- 20% Midterm Exam (Wednesday, March 29, 3:00–4:20).
- 20% Final Exam ( scheduled by the Registrar).
- 60% Problem Sets (sent to you by e-mail each Friday, due at 11:59PM the following Thursday).

For problem sets, 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.

To be fair to people who sumbit on time and to minize 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.

**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.