COS488 Introduction to Analytic Combinatorics

Spring 2020 Syllabus

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.

Faculty

Robert Sedgewick
Office hours: Mondays 12:30–1:20, CS 319 (except for class meeting days). Feel free to stop by alone or in a group to chat, about the course or about CS in general.

RESOURCES

	Required Reading (1st half) Analysis of Algorithms, 2nd ed. Sedgewick and Flajolet Addison-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 Sedgewick Cambridge 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 to study for exams), two lectures per week. The first lecture will be a live lecture 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 3, 12:30–1:20, CS 302).

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.

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. Please pay attention to the instructions for submitting assignments (one .pdf file per problem, named as specified) to avoid snafus in the grading workflow.

Class Meetings

We meet occasionally, usually on Mondays (12:30–1:20, CS 302) for enrichment, exam preparation, and exams, as follows.

February 3
February 10
March 9
March 23
March 25
April 27
May 4

Introduction to AofA [Cardinality Estimation]

COS488 Roadmap

Exam Review 1

Intro to AC [Random Generation]

INCLASS EXAM 1

Exam Review 2

INCLASS EXAM 2

These are the only meeting dates—you may wish to enter them in your calendar. We do not meet on other Mondays or Wednesdays.

GRADING

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

20% Inclass Exam 1 (Wednesday after March break).
20% Inclass Exam 2 (Monday following end of classes).
50% Problem Sets.
10% Questions and Answers (due with problem sets, after the first week).

Exams are in-class, closed-book, no-electronics. A one-page cheatsheet is allowed, one-sided for Exam 1 and two-sided for Exam 2.

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.

Questions and Answers have proven to a very effective vehicle for learning this material. More details will be covered in the second class meeting.

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.