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

Computational Complexity (Autumn 2016)
Section: Room M102, Saturday, 14:00 AM - 15:30 PM
Section: Room M102, Monday, 14:00 AM - 15:30 PM

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

Teacher Assistants
Name E-mail Address Role
Behzad Moradi TA

Required Text: Automata, Computability and Complexity with Applications
Author: Elaine Rich
Publisher: Pearson
Supplementary Material: Introduction to the Theory of Computation
Author: Michael Sipser
Publisher: Thomson (Brooks/Cole), International Student Edition

Scope of the Course

The main goal of this course is to make students more familiar with Computer Science "ABC". It begins with some introduction, finite state machines, regular languages and context-free languages. Then it introduces Turing machines and some applications of it. Finally, it cover some preliminaries of computability by introducing time and space complexity classes.


We may 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.






There will be one final examination.


Your performance in this class will be evaluated using your scores for assignments and test. 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