Design and Analysis of Algorithms

Announcements

  • Thursday (Dec 15) afternoon from 1-3pm there will be O(n!) cookies available for those who are still on-campus and can bring themselves to visit the CS hallway.
  • All homeworks have been returned via github.

Schedule

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

WEEK DAY ANNOUNCEMENTS TOPIC & READING LAB
1

Aug 29

   Course Introduction
Stable Matching
K&T Ch1
Algorithm 3		 Lab 1
Hw 1

Aug 31

  

Sep 02

  
2

Sep 05

   Analysis
K&T Ch 2.1-2.4		 Lab 2

Hw 2

Sep 07

  

Sep 09

Drop/Add ends
3

Sep 12

   Analysis (continued) Lab 3

Hw 3

Sep 14

   Graph Algorithms
K&T Ch 3

Sep 16

  
4

Sep 23

   Graph Algorithms (continued)
Lab 4
Hw 4

Sep 21

  

Sep 19

   Greedy Algorithms
K&T Ch 4
5

Sep 26

   Greedy Algorithms (continued)
Lab 5
Hw 5

Sep 28

  

Sep 30

   Divide and Conquer
K&T Ch 5
6

Oct 03

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
Lab 7
Hw 6

Oct 19

 midterm 7-10pm
review guide

Oct 21

  
8

Oct 24

   Intractability
K&T 8.1-8.4
See also CLRS Ch 34
Lab 8
Hw 7

Oct 26

  

Oct 28

  
9

Oct 31

   Intractability (continued)
Lab 9
Hw 8

Nov 02

  

Nov 04

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

 Network Flow
K&T 7.1-7.3
See also CLRS Ch 26
10

Nov 07

   Network Flow (continued)
K&T 7.5, 7.9, Note on augmenting paths
Lab 10
Hw 9

Nov 09

  

Nov 11

  Linear Programming & the simplex algorithm
11

Nov 14

   Note on LPs and duality
Approximation Algorithms
K&T 11.1-11.4, 11.6, 11.8
See also CLRS Ch 35
Lab 11
Hw 10

Nov 16

  

Nov 18

  
12

Nov 21

   Local Search
K&T 12.1, 12.2, 12.4, 12.5
Randomized Algorithms
K&T 13.1-13.5
Lab 12
Hw 11

Nov 23

  

Nov 25

Thanksgiving Break
13

Nov 28

   Randomized Algorithms (continued)
The Master Theorem (CLRS 4.3-4.4)
Arrow's Impossibility Theorem
(nice but terse and math-dense reference: J. Geanakoplos' Three brief proofs of Arrow's Impossibility Theorem)
This brief Quora discussion is good.
Lab 13

Nov 30

  

Dec 02

  
14

Dec 05

   Class review
15

Dec 14

 final exam
review guide 		9am
Science Center 181: last names A-M
Science Center 183: last names N-Z