Professor: John
Noga (jnoga@csun.edu) (x6480)
WebCT: http://webteach.csun.edu/
Lectures: EN 3510 - 19:00-21:45
Office Hours: EA 4429 - M 19:00-20:00 & R 17:00-19:00
Text: Computational Complexity - Papadimitriou
Course Objective: To understand some of the fundamental
limitations of computation. Topics include: Turing Machines,
decidability, complexity classes (P, NP, coNP), reductions, cryptographic algorithms, and
approximability.
Class Web Page:
http://www.csun.edu/~jnoga/comp610/
Tentative Schedule
| Wednesday |
| Jan 31 Intro / Preliminaries (Ch 1) |
| Feb 7 Turing Machines (Ch 2) |
| Feb 14 Decidability (Ch 3) |
| Feb 21 SAT and Hierarchy Results
(Ch
4.1-2,7) |
| Feb 28 Reductions (Ch 8) |
| Mar 7 Reductions (Ch 8) |
| Mar 14 NP/NP-completeness (Ch 9) |
| Mar 21 NP/NP-completeness (Ch 9) |
| Mar 28 Catch Up, Review, Midterm
Exam |
| Apr 4 Spring Break |
| Apr 11 coNP (Ch 10) |
| Apr 18 Cryptographic Algorithms/Protocols (Ch 12) |
| Apr 25 Cryptographic Protocols (Ch 12) |
| May 2 Approximation/Online Algorithms (Ch 13) |
| May 9 Approximation/Online Algorithms (Ch 13) |
| May 16 Catch Up / Review |
| May
23 Final 20:00-22:00 |
| A 92% |
A- 90% |
|
| B+ 88% |
B 82% |
B- 80% |
| C+ 78% |
C 72% |
C- 70% |
| D+ 68% |
D 62% |
D- 60% |
| F 0% |