Week 0: Pre-course review

Week of 1/11

We will use this review week to go over big-O notation, asymptotic analysis, and reccurence relations. Most of you should already be 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 next week.

Primary videos

Make sure you are comfortable with all of the content in these videos.

Why Study Algorithms? (18:29)

Exact Analysis

Asymptotic Analysis

Complexity Classes

Divide and Conquer

An Example of using Asymptotic Analysis to Build a Better Algorithm

Proving Asymptotic Bounds on Insertion Sort (7:21)

Recurrence Relations (16:21)

Optional extra videos:

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)