Automata2_Spring14

Course Title: CS-534 - Theory of Automata-II

Semester: Spring 2014

Credit Hours: 3

Course Outline:

Pre-Requisites: Theory of Automata, Discrete Mathematics

Objectives:

This is the first course in theoretical computer science. As opposed to other courses in computer science, the purpose of this course is to ask very fundamental questions about computations. The main questions addressed in this course are:

  • What is a computation?
  • Is there a universal model of computation?
  • Can every problem be computed?
  • Can we identify problems that are not computable?
  • How much resources are needed to solve a problem?
  • Can we classify problems that can be solved in principle (given a lot of resources) but cannot be solved in practice?

The theme of the course is to pose these problems in a mathematically precise way. Furthermore, we will answer these questions in a rigorous fashion.

Text Book:

  • Michael Sipser, Introduction to the Theory of Computation (2nd Edition, Thomson Publishing, 2006)

Note: Part I of the book (chapters 0, 1 and 2) are covered in previous courses. We may briefly visit them if there is a need for it. However, major part of this course would be from Part II and III of this book.

  • John Martin, Introduction to Languages and the Theory of Computation (3rd Edition, McGraw-Hill, 2002)

Reference Book:

  • Christos H. Papadimitriou, Computational Complexity (Addison Wesley, 1994)

  • John E. Hopcroft, Introduction to Automata Theory, Languages, and Computation, ( Addison-Wesley, 1979, ISBN 0-201-02988)

Syllabus and Schedule:

Grading, Ranking

Announcements:

  • [21-04-14] Paper submission deadline is Monday 05-05-14 through Slate. Submit three files (.tex, .bib, .pdf). Late submission: -10% per hour.
  • [31-03-14] Assignment-2 (see below) deadline Monday 07-04-2014 at the start of class. Late submission: -10% per hour.
  • [31-03-14] Submit your term paper proposal in latex format by Friday 11-04-2014 before class through Slate. Submit three files (.tex, .bib, .pdf). Late submission: -10% per hour.
  • -5 to l13-5007 for talking during mid.
  • [10-03-14] Midterm will be held on Monday 24-03-14 during class time.
  • [27-01-14] Assignment-1 due at the start of class next Monday (03-02-14).

Evaluation Criteria (Tentative):

Assignments 10 %

Quizzes 15 %

Term Paper 10 %

Midterm 25 %

Final 40 %

Policy:

Cheating in Assignments etc. will lead to zero weightage in all assignments/quizzes/both or more.