CSC 366 -- Spring 2000

Outline of Lecture Topics
-------------------------

*** SUBJECT TO CHANGE ***
(last updated on Thursday 16 December 1999)


Week  1 (Jan  3 - Jan  7):

 * Intro.

 * Greedy Algorithms.

Week  2 (Jan 10 - Jan 14):  (QUIZ #1)

 * Greedy Algorithms.

 * Dynamic Programming.

Week  3 (Jan 17 - Jan 21):  (TEST #1)

 * Dynamic Programming.

 * Flow Algorithms.

Week  4 (Jan 24 - Jan 28):  (QUIZ #2)

 * Flow Algorithms.

 * Self-reducibility.

Week  5 (Jan 31 - Feb  4):  (TEST #2)

 * P and NP.

 * Polytime transformations.

Week  6 (Feb  7 - Feb 11):  (QUIZ #3)

 * NP-completeness.

 * SAT

--------------------------------
 READING WEEK (Feb 14 - Feb 18)
--------------------------------

Week  7 (Feb 21 - Feb 25):  (TEST #3)

 * NP-completeness: examples.

Week  8 (Feb 28 - Mar  3):  (QUIZ #4)

 * NP-completeness: examples.

Week  9 (Mar  6 - Mar 10):  (TEST #4)

 * NP-completeness.

 * Turing machines.

Week 10 (Mar 13 - Mar 17):  (QUIZ #5)

 * Decidability and semi-decidability.

 * Halting problem.

Week 11 (Mar 20 - Mar 24):  (TEST #5)

 * Diagonalization.

 * Many-one reductions.

Week 12 (Mar 27 - Mar 31):  (QUIZ #6)

 * More computability examples.

Week 13 (Apr  3 - Apr  7):  (TEST #6)

 * Review.