CSC 8510-001: Theory of Computability
Spring 2018


v Homework assignments

v Lecture notes

Meeting on Tuesdays, 6:15-9:00 PM, John Barry Hall 213

Course Home Page:

Instructor: Dr. G. Japaridze

Teaching Assistant: Mr. Sri Harsha Alla

"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 (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)

Grading: There will be quizzes and one examination (final). The examination will contribute 20% to your final grade, and the quizzes 80%. The quizzes will be given every week at the beginning of the class.  A quiz will typically have two questions: one from the latest homework assignment, and one from one of the latest three homework assignments. Occasionally, however, questions may be asked that are not exactly on the list of homework problems yet are similar or closely related to the latter; if you have done homework with understanding (as opposed to memorization), answering such questions should not be a problem. The examination will be in the same style as the quizzes but it will be comprehensive and will ask more questions.    Presumably the following scale will be used for final grades after taking your average quiz score:  (A) 94+;  (A-) 87+;  (B+) 80+;  (B) 73+;  (B-) 64+;  (C+) 55+;  (C) 45+

Office of Disabilities and Learning Support Services: It is the policy of Villanova to make reasonable academic accommodations for qualified individuals with disabilities. You must present verification and register with the Learning Support Office by contacting 610-519-5176 or at or for physical access or temporary  disabling conditions, please contact the Office of Disability Services at 610-519-4095 or email Registration is needed in order to receive accommodations.


Academic Integrity: All students are expected to uphold Villanova’s Academic Integrity Policy and Code. Any incident of academic dishonesty will be reported to the Dean of the College of Liberal Arts and Sciences for disciplinary action. For the College’s statement on Academic Integrity, you should consult the Enchiridion. You may view the university’s Academic Integrity Policy and Code, as well as other useful information related to writing papers, at the Academic Integrity Gateway web site:

External links (video lectures):

Ø  P vs. NP and the Computational Complexity Zoo [10 min]

Ø  The P vs NP Problem [61 min]  by Michael Sipser

Ø  The Church-Turing Thesis: Story and Recent Progress [66 min]  by Yuri Gurevich

Ø  The Mathematics of Alan Turing [51 min] by Angus MacIntyre

Ø  Quantum Computing and the Limits of the Efficiently Computable [70 min] by Scott Aaronson

Ø  A Mathematical Mystery Tour [49 min]

Ø  Quantum Computer [collection]