Welcome to Week 1 of "Analysis of Algorithms" (aka part I of "Analytic
Combinatorics"). Each Friday, I’ll send an email like this one
describing lectures and problem sets for the week.
Each lecture for the first half of the course corresponds to a chapter
in An Introduction to the Analysis of Algorithms, 2nd edition, and
everyone is encouraged to study the corresponding chapter in
conjunction with the lectures. The coverage in the book is somewhat
encyclopedic, so I am only expecting that people will turn to the
material associated with what's in the lecture, perhaps scanning
through the rest to see what's there and perhaps find something else
of interest.
We begin our course with an overview of the use of the scientific
method for studying algorithm performance, one of the motivating
applications for analytic combinatorics.
----------
Lecture 1: Analysis of Algorithms. We begin by considering
historical context and motivation for the scientific study of
algorithm performance. Then we consider a classic example that
illustrates the key ingredients of the process: the analysis of
Quicksort. The lecture concludes with a discussion of some resources
that you might find useful during this course.
----------
Slide 45 of the lecture (“Assignments for next lecture”) is a typical
ending of each online lecture. Since we are going through the material
at a rather quick pace, we do not expect that you will complete all of
the suggested activities, and we will abridge and fully specify the
“problem sets” that you must submit for grading.
Your assignment for this week (a short one, to get the ball rolling),
due at 11:59PM on
Thursday, February 7, 2019,
is to write up and submit solutions to
Exercises 1.14 and 1.16
in "Analysis of Algorithms" (second edition). Please note the errata
on the AofA booksite (discovered by students last time we offered this
course). You can find the corrected versions of the exercises on the
booksite.
Email files named “-PS1-Q1.pdf" and “-PS1-Q2.pdf"
directly to me at rs@cs.princeton.edu.
RS