CSC 4170: Theory of Computation

Fall 2016

 

Meeting on Tuesdays and Thursdays, 4:00-5:15 PM, White 218

Homework assignments

Lecture Notes

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

Instructor: Dr. M.A. Papalaskari

Teaching Assistant:  Sailaja Chagarlamudi  Office hours Mondays 1-4pm, Mendel 158

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)

Grading: Your grade will be based on the quizzes, midterm, and final exams. 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.

Quizzes 60%

A weekly 10-15 min quiz will be given every Tuesday, unless otherwise noted. 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. 

Midterm Examination (October 4)   15%

Final Examination - Thursday, Dec 15, 8:30 - 11:00am  25%

The midterm and final will be cumulative. If you must miss the midterm or final, please provide appropriate documentation and make arrangements for a make-up, if possible, before or as soon afterward as feasible. A missed midterm or final without adequate documentation will count as zero points toward the final grade.

Final Exam exception: For students who have scored 80% or higher when averaged over midterm and quizzes (weighed 40% midterm, 60% quiz average), there is an option of skipping the final exam.

Grade scale:     A 90    A- 85    B+ 80    B 75    B- 70    C+ 65    C 60    C- 55    D+ 50    D 45    D- 40


Office of Disabilities and Learning Support Services:

Students with disabilities who require reasonable academic accommodations should schedule an appointment to discuss specifics with me. 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 learning.support.services@villanova.edu  or for physical access or temporary disabling conditions, please contact the Office of Disability Services at 610-519-4095 or email Stephen.mcwilliams@villanova.edu 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 result in an “F” for the assignment and will be reported to the appropriate university officials, per regulations in the Graduate Studies (Liberal Arts and Sciences) Catalog.  You can view the Academic Integrity Policy and Code, as well as other useful information related to writing papers, at the Academic Integrity Gateway web site.