Design and Analysis of Algorithms

Announcements

  • All homeworks except for hw11 have now been returned. Let me know if you have questions.
  • Here is a review guide for the final exam.
  • Homework 11 has been posted and is due Tuesday, December 6 at 11PM.

Schedule

The schedule for after the fall break remains tentative and subject to change.

WEEK   DATE   ANNOUNCEMENTS TOPIC & READING LAB
1

Aug 29

  Course Introduction
Stable Matching
K&T Ch1
Lab 1
Homework 1

Aug 31

 

Sep 02

 
2

Sep 05

  Analysis
K&T Ch 2.1-2.2
Lab 2
Homework 2

Sep 07

  Analysis (continued)
K&T Ch 2.3

Sep 09

Drop/Add ends

Analysis (continued)
K&T Ch 2.4
3

Sep 12

  Graph Algorithms
K&T Ch 3.1-3.2
Lab 3
Homework 3

Sep 14

  Graph Algorithms (continued)
K&T Ch 3.4

Sep 16

  Graph Algorithms (continued)
K&T Ch 3.5-3.6
4

Sep 19

  Graph Algorithms (continued) Lab 4
Homework 4

Sep 21

  Greedy Algorithms
K&T Ch 4.1-4.2, 4.4-4.5

Sep 23

 
5

Sep 26

  Greedy Algorithms (continued)
K&T Ch 4.2, 4.4-4.5
Lab 5
Homework 5

Sep 28

  Divide and Conquer
K&T Ch 5

Sep 30

 
6

Oct 03

no class -- Rosh Hashanah

Divide and Conquer (continued)
K&T Ch 5
Lab 6

Oct 05

 

Oct 07

 
 

Oct 10

Fall Break

Oct 12

Oct 14

7

Oct 17

  Dynamic Programming
K&T Ch 6.1, 6.4
Homework 6

Oct 19

Midterm

Oct 21

  Dynamic Programming (continued)
K&T Ch 6.5
8

Oct 24

  Dynamic Programming (continued)
K&T Ch 6.2
Lab 8
Homework 7

Oct 26

  Intractability
K&T 8.1-8.4
See also CLRS Ch 34

Oct 28

 
9

Oct 31

  Intractability (continued) Lab 9
Homework 8

Nov 02

  A Brief History of Theoretical Computer Science

Nov 04

Last day to declare CR/NC or
withdraw with a "W"

Approximation Algorithms
10

Nov 07

  Approximation Algorithms
K&T 11.1-11.4, 11.6, 11.8
See also CLRS Ch 35
Lab 10
Homework 9

Nov 09

 

Nov 11

 
11

Nov 14

  Randomized Algorithms
K&T 13.1-13.5
Lab 11
Homework 10

Nov 16

 

Nov 18

 
12

Nov 21

  Lower Bounds

Nov 23

 

Nov 25

Thanksgiving Break

13

Nov 28

  Alternate Models of Computation: Quantum Computing Lab 13
Homework 11

Nov 30

 

Dec 02

 
14

Dec 05

  Class review