###
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 | behzadmoradi@iasbs.ac.ir | 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.

### Syllabus

We may learn about these subjects:

- Introduction here
- Finite State Machines and Regular Languages here. You may see supplementary slides here
- Context-Free Languages here and Pushdown Automata here
- Turing Machines, Universal Turing machines and Undecidability here
, here
, here
and here
- Halting problem here
- Introduction to Complexity here
, here
and here
- Introduction to Logic here
and here

### 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

NA

### Presentation

NA

### Tests

There will be one final examination.

### Grades

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.*

- Assignments: 30%
- Final Test: 70%

### 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