Design and Analysis of Algorithms

Announcements

  • The final will be on Friday, May 15 from 9AM-12PM in SCI 105.
  • A study guide for the final is here.
  • There will be a final review session Thursday, May 7 from 3-5PM in SCI 246
  • The second weekly status update is due Friday, April 24.
  • Homework 10 has been released and is due 10AM Thursday April 30.
  • Solutions to Homework 8, problem 3 (Liars and Friars) has been posted outside my door.
  • Final Project information has been released.

Schedule

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

WEEK DAY ANNOUNCEMENTS TOPIC & READING LAB
1

Jan 19

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

Jan 21

 

Jan 23

 
2

Jan 26

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

Jan 28

 

Jan 30

Drop/Add ends

3

Feb 02

  Analysis continued
K&T Ch 2.1-2.4
Homework 3

Feb 04

  classes cancelled

Feb 06

 
4

Feb 09

  Graph Algorithms
K&T Ch 3
Lab 4
Homework 4
partners

Feb 11

 

Feb 13

 
5

Feb 16

  Greedy Algorithms
K&T Ch 4
Lab 5
Homework 5

Feb 18

 

Feb 20

 
6

Feb 23

  Divide and Conquer
K&T Ch 5
Lab 6
Homework 6

Feb 25

 

Feb 27

 
7

Mar 02

Midterm (Mar 03)

Divide and Conquer (continued)
K&T Ch 5

Mar 04

 

Mar 06

  no class
(SIGCSE conference)
 

Mar 09

Spring Break

Mar 11

Mar 13

8

Mar 16

  Dynamic Programming
K&T Ch 6
Lab 8
Homework 7

Mar 18

 

Mar 20

 
9

Mar 23

  Intractability
K&T 8.1-8.4
See also CLRS Ch 34
Lab 9
Homework 8

Mar 25

 

Mar 27

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

10

Mar 30

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

Apr 01

 

Apr 03

 
11

Apr 06

  Randomized Algorithms
K&T 13.1-13.5
Lab 11

Apr 08

 

Apr 10

 
12

Apr 13

  Lower Bounds Lab 12
Homework 10

Apr 15

 

Apr 17

 
13

Apr 20

  Alternate Models of Computation:
Streaming Algorithms
The Space Complexity of Approximating The Frequency Moments, by Alon, Matias, Szegedy STOC 1996.
Lab 13

Apr 22

 

Apr 24

 
14

Apr 27

  Final projects, class review

Apr 29

 

May 01