CSC 4170: Theory of Computation

Fall 2013


Meeting on Tuesdays and Thursdays, 4:00-5:15 PM, Mendel G87

Homework assignments

Lecture Notes

Course Home Page:

Instructor: Dr. G. Japaridze

Teaching Assistant: Ms. Sherin AmbrammadomBasheer

"Introduction to the Theory of Computation" (3rd edition) By Michael Sipser. Cengage Learning, 2013. ISBN 978-1-133-18779-0

Description and goals: This course is about what computers can and cannot do. It approaches this question in a strict mathematical fashion. The goal of the course is to expand your mind and give you conceptual tools for solving theoretical and practical problems.

Topics and Schedule (tentative):

  1. Regular Languages (4 weeks)
  2. Context-free Languages (3 weeks)
  3. The Church-Turing Thesis (3 weeks)
  4. Decidability (2 weeks)
  5. Basics of Complexity Theory (2 weeks)

Grading: Your grade will be based on the quizzes. They will be given frequently and without warning.  Missed quizzes usually cannot be made up. One quiz with the lowest grade, however, will be automatically forgiven.