CSC 4170: Theory of Computation

Fall 2012

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

Homework assignments

Lecture Notes

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

Instructor: Dr. G. Japaridze

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

Teaching Assistant: Mr. SivaKumar Nalanagula

• Office: SE lab
• Email: snalanag@villanova.edu
• Office hours: Wednesdays 2:00-4:00 PM

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

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)

Examination schedule:

1. Last class before the Fall break 
2. T.B.A.

Quizzes: Every Tuesday. Missed quizzes cannot be made up no matter what the reason was. One quiz with the lowest grade, however, will be automatically forgiven.

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