CSC 8510 / CSC 4170

Spring 2016

Homework assignments

Lecture notes

Meeting on Thursdays, 6:15-9:00 PM, Mendel 115

Course Home Page:

Instructor: Dr. M.A Papalaskari

Office: MSC 162C
Office hours: Tuesdays: 11:30-1:00pm; Thursdays: 4:30-6:00; Fridays: 9:30-10:30am; or by appointment

Teaching Assistant: Naresh Nelavalli

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

Grading: Your grade will be based on the quizzes. They will be given every Thursday. A quiz will typically have two questions: one from the latest homework assignment, and one from some earlier homework assignment. 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. One quiz with the lowest grade will be automatically dropped.

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

Additional Resources:

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]

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  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 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.