CSC 8510: Theory of
Fall 2016 (Tuesday evening section)
NOTE: This page should be viewed with Internet Explorer. Other browsers may fail to display things properly.
Meeting on Thursdays, 6:15-9:00 PM, J.Barry Hall 202B
Course Home Page: http://www.csc.villanova.edu/~japaridz/8510/
Instructor: Dr. G. Japaridze
Teaching Assistant: Ms. NahiniVenkantaKrishnaKumari Palem
"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):
Grading: Your grade will be based on the quizzes. They 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 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.
External links (video lectures):
Ø 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]