Design and Analysis of Algorithms

Announcements

  • The final exam will be on Monday, December 12 from 9am-12pm in Singer Hall room 222. Here is a final exam review guide.
  • Homeworks 1-9 have been graded and returned.
  • There will be review sessions for the final exam on Thursday December 8 and Saturday December 10, both from 8-10pm in Singer 222. The first review session will be exclusively for recurrence relations and dynamic programming.

Schedule

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

WEEK DAY ANNOUNCEMENTS TOPIC & SUGGESTED READING LABS     
1

Aug 29

  Course Introduction
Stable matching
read: chapter 1
set up github
LearningLaTeX.tex
Lab 1
Homework 1

Aug 31

 

Sep 02

 
2

Sep 05

no classes -- Labor Day

Lab 2
Homework 2

Sep 07

 

Sep 09

Drop/add ends

Analysis
read: chapter 2.1-2.4
3

Sep 12

  Lab 3
Homework 3

Sep 14

 

Sep 16

 
4

Sep 19

  Graph algorithms
read: chapter 3
Lab 4
Homework 4

Sep 21

 

Sep 23

 
5

Sep 26

Test 1 in class

Sep 28

  Graph algorithms
read: chapter 3 (continued)
Lab 5

Sep 30

 
6

Oct 03

  Greedy algorithms
read: chapter 4

Oct 05

no class -- Yom Kippur

Lab 6
Homework 5

Oct 07

 
 

Oct 10

Fall break

Oct 12

Oct 14

7

Oct 17

  Greedy algorithms
read: chapter 4 (continued)

Oct 19

  Divide and conquer
read: chapter 5
Lab 7
Homework 6

Oct 21

Test 2 in class

8

Oct 24

  Divide and conquer
read: chapter 5 (continued)
Lab 8
Homework 7

Oct 26

 

Oct 28

 
9

Oct 31

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

Nov 02

 

Nov 04

 
10

Nov 07

  Lab 10

Nov 09

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

Nov 11

 
11

Nov 14

  Lab 11
Homework 9

Nov 16

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

Nov 18

Test 3 in class

12

Nov 21

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

Nov 23

 

Nov 25

Thanksgiving break

13

Nov 28

 

Nov 30

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

Dec 02

 
14

Dec 05

 

Dec 07

Last day of classes

Lab 13
 

Dec 12

9am-12pm Final Exam, Singer 222