Welcome to Week 2 of Analysis of Algorithms. The lectures for this
week survey basic mathematical tools that have been used for
scientific studies for centuries and are still effective for the
analysis of algorithms.
----------
Lecture 2: Recurrences. We begin the course with an
overview of recurrence relations, which provide us with a direct
mathematical model for the analysis of algorithms. We finish by
examining the fascinating oscillatory behavior of the
divide-and-conquer recurrence corresponding to the mergesort algorithm
and the general "master theorem" for related recurrences.
Lecture 3: Generating Functions. Since the 17th century, scientists
have been using generating functions to solve recurrences, so we
continue with an overview of generating functions, emphasizing their
utility in solving problems like counting the number of binary trees
with N nodes.
----------
Your assignment for this week, due at 11:59PM on
Thursday, February 14, 2019
is to write up and submit solutions to
Exercises 2.13, 2.17, 3.20, and 3.28
in "Analysis of Algorithms" (second edition). Please note the error
in 2.17 on the AofA booksite (discovered by students last time we offered this
course). You can find the corrected version on the booksite.
Email files named “-PS2-Q1.pdf",
“-PS2-Q2.pdf", “-PS2-Q3.pdf",
“-PS2-Q4.pdf", and “-PS2-QQ.pdf"
directly to me at rs@cs.princeton.edu.
RS