Week 1: Review of Algorithm Analysis

Week of 1/10

This week, we’ll review big-O notation, asymptotic analysis, and reccurence relations. 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.

In class videos

For Tuesday

Please either come to class (via Zoom) or watch the recording of class (via Mediaspace). We will go over the syllabus and plans for the semester.

The following video goes over the same content that we discussed in class”

Why Study Algorithms? (18:29)

For Thursday

We’ll watch these videos in class:

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)

Proving Asymptotic Bounds on Mergesort (18:09)

Code:

Code for this week is available here.

Out:

Syllabus, Lecture review assignment #1 (due Friday), Homework #1 (due 1/25)

Due:

Lecture review assignment #1 (due Friday)