Design and Analysis of Algorithms

Announcements

  • Homeworks 1-6 have been graded and returned.
  • Homework 8 is released and will be due 11:59pm Sunday November 1.
  • Tests 1-2 have been graded and returned via Gradescope.
  • In addition to lecture videos on Panopto, I'll try to maintain a series of brief lecture notes. I'm putting these in the examples repo. I encourage you to do a git pull on this repo before lecture each day to find these notes.
  • Remote class meeting information: (Zoom and Slack links for our class are posted to the CS41 Piazza page)
    • Lecture: on zoom
    • Labs:start the class on Slack (go to your #lab-X channel). We'll launch Zoom from there.
    • Office hours: on Slack (go to the #office-hours channel)

Schedule

This schedule is subject to modifications. Check back for the latest version!

WEEK DAY ANNOUNCEMENTS TOPIC & SUGGESTED READING LABS     
1

Sep 07

  Course Introduction
Stable matching
read: chapter 1
set up github
Homework 0
Lab 1
Homework 1

Sep 09

 

Sep 11

 
2

Sep 14

Drop/add ends

Analysis
read: chapter 2.1-2.4
Lab 2
Homework 2

Sep 16

 

Sep 18

 
3

Sep 21

  Lab 3
Homework 3

Sep 23

 

Sep 25

Test 1

Graph algorithms
read: chapter 3
4

Sep 28

no class -- Yom Kippur

Homework 4

Sep 30

 

Oct 02

 
5

Oct 05

  Lab 5
Homework 5

Oct 07

  Greedy algorithms
read: chapter 4

Oct 09

Test 2

6

Oct 12

  Lab 6
Homework 6

Oct 14

 

Oct 16

  Divide and conquer
read: chapter 5
7

Oct 19

  Lab 7
Homework 7

Oct 21

 

Oct 23

Test 3

8

Oct 26

  Dynamic programming
read: chapter 6.1, 6.2, 6.5.
optional reading: chapter 6.3, 6.4
Lab 8
Homework 8

Oct 28

 

Oct 30

 
9

Nov 02

 

Nov 04

  Network flow
read: chapter 7.1-7.3, 7.5, 7.9; see also CLRS chapter 26

Nov 06

 
10

Nov 09

 

Nov 11

  Intractability
read: chapter 8.1-8.4; see also CLRS chapter 34

Nov 13

Test 4

11

Nov 16

 

Nov 18

 

Nov 20

 
 

Nov 23

Thanksgiving break

Nov 25

Nov 27

12

Nov 30

  Approximation algorithms
read: chapter 11.1-11.4, 11.6, 11.8; see also CLRS chapter 35
 

Dec 02

 

Dec 04

Last day of classes

Test 5