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 3, 2022 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 that the booksite corrects an error in 2.17 in the book that was discovered by students during an earlier offering of this course. After solving these problems, read the slides in RoadMap.pdf. Starting this week, you must also create and submit a question (with answer) on the week's material, suitable for use as an assessment in this course. RoadMap.pdf gives some examples. These questions will count for 10% of your grade. Finally RoadMap.pdf gives pointers to three movies for your pandemic-viewing enjoyment that relate strongly to the material in this course. Submit files named “AofA2-Q1.pdf" “AofA2-Q2.pdf" "AofA2-Q3.pdf" “AofA2-Q4.pdf" “AofA2-QQ.pdf" via codePost. RS