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

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.

• Final: We, 07 Dec 2016

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