An Introduction to the
THE BASIS for course content is our textbook, a thorough overview of the primary techniques used in the mathematical analysis of algorithms. Drawing from classical mathematical topics (discrete mathematics, elementary real analysis, and combinatorics) and classical computer science topics (algorithms and data structures), it covers recurrence relations, generating functions, asymptotics, and analytic combinatorics, with applications to algorithms and combinatorial structures such as trees, permutations, strings and tries, words, and mappings.
A major goal of the course is to prepare students to learn from D. E. Knuth’s classic The Art of Computer Programming.
First Edition
French translation
Lectures in this course are based on hundreds of carefully prepared slides, which you can browse below. Clicking on a lecture title allows you to scroll through the slides for that lecture. These slides give full information about the content of the course.
All the lectures for this course are available as online videos. These are carefully prepared, integrated with course content, and produced in a studio. As with traditional in-person lectures, their purpose is to introduce topics to learners and to inspire further study.
To get an idea of what a modern online lecture video is like, try this one, the lecture on trees from this course. Important note: The best way to experience a lecture video is to speed it up when not interested (or bored) and slow it down when interested (or confused). You can quickly scan this video in twenty minutes or so.
All of the videos are available for viewing on the CUvids platform. This platform is recommended because it applies modern machine-learning models to build searchable transcripts, indices, and other features that enhance the experience of learning from the videos.
Our Analysis of Algorithms booksite is freely available on the web. It contains tens of thousands of files, is fully coordinated with our lectures and textbook and also is useful as a standalone resource. It consists of the following elements:
Excerpts. A condensed version of the text narrative.
Exercises. Selected exercises from the book and “web exercises” developed since its publication, along with some solutions.
Online course. A schedule for learning the material in the book over a seven-week period, for use either by individuals or by instructors leading a class. For example, suggested weekly e-mails to the class are included and the lecture videos and slides are integrated into the site.
This is a living resource that is constantly being improved and updated.
You can find details on how we conduct our course at Princeton on our Princeton COS 488 course website. This course is the first half of COS 488. The course website is a detailed “contract” between faculty and students, including the schedule and a full description of course components. This course has been fully online even before the pandemic. Students watch online lectures each week whenever and wherever they want and then complete and submit problem sets that challenge their understanding of the course material. Synchronization is established via weekly e-mails from the instructor delineating the assignments for the week, timely individualized feedback on assignments, and an exam on course content.
