Instructor: Dr. Ebrahim Ansari
Office Hours: See my weekly Schedule
Location: Computer Science and Information Technology Dept., Room 219

Required Text: Computational Complexity: A Modern Approach
Author: Sanjeev Arora and Boaz Barak
Publisher: Cambridge University Press
you can download the draft version of the book here

Supplementary Material: Introduction to the Theory of Computation
Author: Michael Sipser
Publisher: Thomson (Brooks/Cole), International Student Edition

Scope of the Course

To study complexity classes and their interrelations.

Syllabus

We should learn about these subjects:

• Introduction
• Turing machines
• Universal Turing machines and Undecidability
• Halting problem
• P, NP, NP-completeness
• Diagonalization
• Reductions
• Decision vs Search Problems
• Oracle Turing Machines
• Polynomial Hierarchy
• cryptography
• Approximability

Assignments

Each assignment will have a clearly stated due date and time. Assignments start out being easy but get harder over the semester.

You should prepare and give up your assignments before deadline directly to me.

Project

Announcement in future

Presentation

Each student should prepare a 25-minute (excluding Q/A) presentation plus an abstract report for his/her subject. The schedule of our presentation will be announced in future.

Tests

There will be one final examination.

• Final: Mon, 07 Dec 2015

Grades

Your performance in this class will be evaluated using your scores for quizzes, programming assignments, and two tests. The weights of each of these components are listed below. There are no extra credit projects or assignments to improve your grade.

• Programming Assignments: 30%
• Project: 20%
• Presentation: 20%
• Report: 10%
• Final Test: 20%

Policies

Acts that exceed the bounds defined by the approved collaboration practices will be considered cheating. Such acts include:

• Copying solutions, code, or programs from someone else or giving someone else your solutions, code, or programs
• Participation in a discussion group that develops a solution that everyone copies
• Employing someone to write the solutions for you on homework assignment problems.

Announcements

No announcement yet