Professor: John Noga (jnoga@csun.edu) (x6480)
Lectures:
EN3508 - R 19:00-21:45
Office Hours: JD 4429 - TR 12:30-13:15 & 18:00-18:45, W 12:00-13:00
Text: Computational
Complexity - Papadimitriou
LMS: moodle.csun.edu
Course Objectives: Understanding the fundamental limitations of computation. Topics include: Turing Machines, decidability, complexity classes (P, NP, coNP, L, NL), reductions, and approximability.
Tentative Schedule:
| T (class
meets once per week) |
| Jan 20: Intro / Preliminaries (start
TM?) (Ch 1, 2.1) |
| Jan 27: Turing Machines (Ch 2) |
| Feb 3: Decidability (Ch 3) |
| Feb 10:SAT and Hierarchy Results
(Ch
4.1-2,7) |
| Feb 17: Reductions (Ch 8) |
| Feb 24: Reductions (Ch 8) |
| Mar 3: NP/NP-completeness (Ch 9) |
| Mar 10: NP/NP-completeness (Ch 9)
& Catch Up and Review |
| Mar 17: Midterm
Exam & coNP (Ch 10) |
| Mar 24: Randomized Algorithms |
| Mar 31: Chavez Holiday |
| Apr 7: Spring Break |
| Apr 14: Approximation Algorithms
(Ch 13) |
| Apr 21: Online Algorithms |
| Apr 28:Parallel Algorithms (Ch 15) |
| May 5: L / NL (Ch 16) & Catch Up
and Review |
| May
12: 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% |
Academic Dishonesty: The typical penalty for any
form
of academic dishonesty is an F for the course and being reported to
the Vice President for Student Affairs. Note that facilitating the
academic dishonesty of others is a form of academic dishonesty. Note
all homework assignments and exams are assigned to individuals.
Students may discuss homework problems. Students may explain what needs
to done and suggest methods to accomplish the tasks. However,
submitting work which is identical or nearly identical is cheating.
Submitting work done by others or a solution you do not understand is
cheating. What you submit should reflect your understanding of the
material. Further details can be found in the CSUN Catalog.
If there
is any doubt as to what constitutes academic dishonesty ask the
professor.