CS 611 ---- Introduction to Computability and Complexity


Instructor: Prof. Joseph Leung

Office: 4202 GITC

Office Hrs: T Th 10:00-11:00am, 1:30-2:30pm

Phone: (973) 596-3387

Email: leung@njit.edu

URL: web.njit.edu/~leung


Textbook: M.R. Garey and D.S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman, 1979.


Syllabus: Half of the course is about proving NP-Completeness and the other half is about approximation algorithms with provable worst-case performance. More details can be found in the "Weekly Listing of Course Topics" handout.


Grading: (1) Two midterm exams, the first one at about the 7th week and the second one at about the 12th week. Each midterm counts 1/3 of the grade.

(2) Final exam which will be held in the final exam week. It counts 1/3 of the grade.

(3) Homework will be given throughout the semester. The homework is used to prepare for the exam.


NJIT Honor Code will be upheld. Any violations will be brought to the immediate attention of the Dean of Students.


Students will be consulted about any deviations or modifications from the syllabus throughout the course of the semester.