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 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, due at 11:59PM on
Thursday, February 9, 2017
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.
Submit files named “PS1-Q1.pdf" and “PS1-Q2.pdf" here:
http://dropbox.cs.princeton.edu/COS488_S2017/Assignment_1
RS