**CSC 4170: Theory of Computation**

**Fall
2014**

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

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

**Instructor:** Dr. G. Japaridze

**Office:**M 165A**Email:**giorgi.japaridze@villanova.edu**Office hours:**Thursdays 2:45-3:45 PM and 9:00-10:00 PM (may leave soon after 9:00 if nobody comes)

**Teaching Assistant:** Ms. Sudheshna ThathamChetty

**Office:**Mendel 158**Email:**sthatham@villanova.edu**Office hours:**Wednesdays 3:30-5:30

**Textbook:**

*"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):

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

**Grading:** Your grade will be based on the quizzes. They will
be given every Thursday. Missed
quizzes cannot be made up. One quiz with the lowest grade, however, will be
automatically dropped. A quiz will typically have two questions: one from the
latest two homework assignments, and one from some earlier homework assignment.