CSC 8510: Theory of Computability
Spring 2010


Meeting on Thursdays, 6:15-9:00 PM, JBarry 213

Course Home Page: http://www.csc.villanova.edu/~japaridz/8510/

Instructor: Dr. G. Japaridze

Teaching Assistant: Mr Hao Zhang

Textbook:
"Introduction to the Theory of Computation" (2nd edition) By Michael Sipser. Thomson Course Technology, 2006. ISBN 0-534-95097-3

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 (1 week)
  2. Context-free Languages (1 week)
  3. The Church-Turing Thesis (1 week)
  4. Decidability (1 week)
  5. Reducibility (1 week)
  6. Time Complexity (4 weeks)
  7. Space Complexity (3 weeks)
  8. Advanced topics (2 weeks)

Examination schedule:

  1. Last class before the midterm break
  2. Last class of the semester

Quizzes: Every week. Missed quizzes cannot be made up no matter what the reason was. One quiz of your choice, however, will be automatically forgiven.

Grading: Quizzes --- 20%, Examinations --- 80%.

Presumably, grades will be derived from cumulative scores as follows:

Score Grade
94 or more   A
87 or more   A-
80 or more   B+
72 or more   B
63 or more   B-
54 or more   C+
45 or more   C
less than 45   F