Department of Computer Science and Information Technology
Institute of Advanced Studies in Basic Sciences

Computational Complexity (Autumn 2015)
Section: Room I003, Monday, 9:30 AM - 11:00 AM
Section: Room I003, Wendesday, 9:30 AM - 11:00 AM

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.


We should learn about these subjects:


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.


Announcement in future


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.


There will be one final examination.


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.


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


No announcement yet