Introduction to Computability and Complexity
CS-611-002 Syllabus

Instructor: Ioannis Koutis
Email: ikoutis+cs611@njit.edu
Office: GITC 4314
Course Time and Location: Tuesday and Thursday 2:30-3:55pm (GITC3710)
Office Hours: Tuesday 4:30-6:00, Thursday: 4:30-6:00 and by appointment

Description

The course will cover fundamental elements of computational complexity. Possible topics include:

- Computability
- NP and NP Completeness
- Parameterized Complexity
- Diagonalization
- Space Complexity
- Polynomial Hierarchy
- Randomized Computation
- Interactive Proofs
- Complexity of Counting
- Cryptography

Resources

Textbook:

Computational Complexity: A modern approach, by Boaz Barak and Sanjeev Arora

1^st edition, Cambridge University Press

ISBN: 0521424267, 9780521424264

Alternative Source:

Computational Complexity, by Christos Papadimitriou

Lecture notes will also be distributed.

Course Schedule

We will cover at least 8 of the topics listed in course description, roughly in the given order. There will be 3 non-cumulative exams, on the given dates, during class time:

Exam 1: February 22
Exam 2: March 22
Exam 3: May 1

Coursework and Evaluation

Assignments [25%]. There will be eight short assignments.
(Each assignment is worth 1/32 of the final score)

Each assignment will be graded with [A/B/F], worth [4/3/0] points.
“A” signifies very good and complete work, demonstrating solid understanding.
“B” signifies a satisfactory amount of work but with some key elements missing.
“F” to all other assignments.

Exams [75%]. The exam is graded in a [A/B/C/F] basis, worth [4/3/2/0] points.
“C” signifies basic understanding.
(Each exam is worth 1/4 of the final score)

Final Grade: The weighted average (say g) of the assignments and the exams will be converted to the final letter grade as follows:
[A: g>3.5, B+: 3<g<3.5 , B: 2.5<g<3, C+: 2<g<2.5, C: 1.5<g<2, D: 1<g<1.5, F: g<1]

Lateness Policy. Each student starts the semester with a total budget of 160 hours of combined delay. After that, the maximum assignment grade is B, and credit is given only when the assignment is delivered before the solutions are posted.

Course Policies

Email
Use of your NJIT email is strongly encouraged to avoid delivery problems.

Moodle Announcements
All course announcements will be posted on Moodle. So, check it regularly, or even better subscribe to the corresponding forums to receive e-mail notifications.

Moodle Discussion Forums
We will use Moodle to have informal and friendly conversations about topics related to the course, including assignments, problems, ideas, etc. You are encouraged to participate. Please be absolutely assured that any question or idea is welcome; even if you are afraid it may be silly, it can lead to interesting and beneficial discussions.

Mobile Devices
Please refrain from using them during the lecture.

Assignment Delivery
Be careful to read and follow any formatting and delivery instructions that come with each assignment.

Grading
Written work will be graded for conciseness and correctness. Use formal arguments. Be brief and to the point and write clearly. Material covered in class and appearing in the relevant notes without proof. Do not use pencils in the exams.

Grade Corrections
Check the marks in course work and report errors promptly. Please try and resolve any issue within one week of the mark notification.

Absenteeism
If you miss a class, it’s up to you to make up for lost time.

Incomplete
A grade of I (incomplete) is given in rare cases where work cannot be completed during the semester due to documented long-term illness or unexpected absence for other serious reasons. A student needs to be in good standing (i.e. passing the course before the absence) and receives a provisional I if there is no time to make up for the documented lost time; a letter (or email) with a timeline of what is needed to be done will be sent to the student. Note that for most cases an I would be resolved within few days, not months and not the following semester! Not showing up in the final will probably get you an F rather than an I.

Collaboration and External Resources for Assignments
Some homework assignment problems will be challenging. You are advised to first try and solve all the problems on your own. For problems that persist, you are welcome to talk to the professor. You are also allowed to collaborate with your classmates and search for solutions online. But you should use such solutions only if you understand them completely (admitting that you don’t understand something is way better than copying things you don’t understand). Also make sure to give the appropriate credit and citation.

The NJIT Academic Integrity (Honor) Code will be upheld; violations will be reported to the Dean of Students (DOS).