Course Materials


This page provides access to various materials for use in teaching and learning from the book An Introduction to the Analysis of Algorithms, including lecture slides, a sample schedule, assignments, and exams. Along with a MOOC or certificate course (see tabs at bottom left), it is appropriate for use by instructors as the basis for a "flipped" class on the subject, or for self-study by individuals.

Flipped class.

If you are an an instructor teaching the analysis of algorithms, an effective way for you to teach the material in a typical college class is to adhere to a weekly cadence, as follows: Important note: A common mistake in teaching a flipped class is to add too much enrichment material. Our experience is that time in class meetings is much better spent preparing students for success on problem sets and exams. If an instructor makes it clear that the best way to prepare for exams is to watch the lectures and do the reading, most students will do so. Class meetings then can involve interacting with students and with the material in such a way as to reinforce understanding. For example, working with potential exam questions is an excellent activity. You can find some examples at the end of each section on this booksite.

Self-study.

An effective way to learn the material on your own is to play the lectures on some regular schedule, do the associated reading, and attempt to solve some of the assigned exercises on your own. If you get stuck on a particular exercise, find some others in the book or on this website, or try to solve some of the problems given in the lectures without looking at the solutions there. In the future, we plan to add more exercises with solutions to this booksite, but that is work in progress.

While some of the reading material may be difficult for a typical undergraduate to master on such a quick pass through, a substantial fraction of the coverage is elementary, and the lectures provide a firm basis for understanding the key concepts.



WEEKLY ASSIGNMENT LECTURE VIDEOS LECTURE SLIDES
AofAweek0.txt

  0. Cardinality Estimation

    0.1 Introduction

    0.2 Exact cardinality count

    0.3 Probabilistic counting

    0.4 Stochastic averaging

    0.5 Refinements

    0.6 Final frontier

AA00-Cardinality.pdf
AofAweek1.txt

Ex. 1.14

Ex. 1.16

  1. Analysis of Algorithms

    1.1 History

    1.2 Approach

    1.3 Quicksort

    1.4 Resources

AA01-AofA.pdf
AofAweek2.txt

Ex. 2.13

Ex. 2.17

Ex. 3.20

Ex. 3.28

  2. Recurrences

    2.1 Computing

    2.2 Telescoping

    2.3 Types

    2.4 Mergesort

    2.5 Master Theorem

  3. Generating Functions

    3.1 OGFs

    3.2 Solving recurrences

    3.3 Catalan numbers

    3.4 EGFs

    3.5 Counting with GFs

AA02-Recurrences.pdf

AA03-GFs.pdf

Roadmap.pdf

AofAweek3.txt

Ex. 4.9

Ex. 4.23

Ex. 4.38

Ex. 4.71

  4. Asymptotics

    4.1 Standard scale

    4.2 Manipulating expansions

    4.3 Asymptotics of finite sums

    4.4 Bivariate asymptotics

AA04-Asymptotics.pdf
AofAweek4.txt

Ex. 5.1

Ex. 5.3

Ex. 5.7

Ex. 5.23

  5. Analytic Combinatorics

    5.1 The symbolic method

    5.2 Labelled objects

    5.3 Coefficient asymptotics

    5.4 Perspective

AA05-AC.pdf

AofAweek5.txt

Ex. 6.6

Ex. 5.16

Ex. 7.26

Ex. 7.29

  6. Trees

    6.1 Trees and forests

    6.2 BSTs

    6.3 Path length

    6.4 Other types of trees

  7. Permutations

    7.1 Basics

    7.2 Sets of cycles

    7.3 Left-right minima

    7.4 Other parameters

    7.5 BGFs and distributions

AA06-Trees.pdf

AA07-Perms.pdf

AofAweek6.txt

Ex. 8.3

Ex. 8.14

Ex. 8.57

Ex. 9.58

  8. Strings

    8.1 Bitstrings with restrictions

    8.2 Languages

    8.3 Tries

    8.4 Trie parameters

  9. Words and Mappings

    9.1 Words

    9.2 Birthday problem

    9.3 Coupon collector problem

    9.4 Hash tables

    9.5 Mappings

AA08-Strings.pdf

AA09-Words.pdf

AofAreview1.txt

AAReview.pdf

Review Problem Set

Q1.3

Q2.4

Q3.4

Q4.4

Q5.4

Q6.4

Q7.4

Q8.4

Q9.3