Week 1: Review of Algorithm Analysis

Week of 8/27

This week, we’ll review big-O notation, and asymptotic analysis. Most of you are probably already familiar with these ideas, but we will be using them a lot over the course of the semester, so I want to make sure they’re fresh in your minds. We will also practice these concepts in class.

Videos

These are the videos that were recorded for the Fall 2020 version of the class. Watch these if you want a refresher or want to take the class asynchronously.

Monday

Why Study Algorithms? (18:29)

Wednesday

Exact Analysis

Asymptotic Analysis

Proving Asymptotic Bounds on Insertion Sort (7:21)

Complexity Classes

Divide and Conquer

An Example of using Asymptotic Analysis to Build a Better Algorithm

We’ll also go through these practice problems.

Optional extra videos:

Recurrence Relations (16:21)

Lightcycle Example Problem (7:39)

Empirically measuring the time complexity

(using Divide and Conquer algorithm from above)

Live-coding the algorithms used in the previous video

(these are long, so don’t feel obligated to watch them - they’re a resource for you in case they’re helpful)