Courses:

Theory of Computation >> Content Detail



Syllabus



Syllabus

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.


Prerequisites




Official


Principles of Applied Mathematics (18.310C) or Mathematics for Computer Science (18.062J / 6.042J).



Real


You need some facility with the mathematical concepts of theorem and proof. Most of the assignments in this course require proving some statement and some creativity in finding the proof will be necessary.



Course Outline


  • Automata and Language Theory (2 weeks)
    • Finite automata, regular expressions, push-down automata, context free grammars, pumping lemmas.
  • Computability Theory (3 weeks)
    • Turing machines, Church-Turing thesis, decidability, halting problem, reducibility, recursion theorem.
  • Complexity Theory (7 weeks)
    • Time and space measures, hierarchy theorems, complexity classes P, NP, L, NL, PSPACE, BPP and IP, complete problems, P versus NP conjecture, quantiers and games, provably hard problems, relativized computation and oracles, probabilistic computation, interactive proof systems. Possible advanced topic as time permits.


Text


Amazon logo Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Thomson Course Technology, 2006. ISBN: 0534950973.

You'll need the 2nd edition because of the new homework problems it contains. Errata for 2nd edition of textbook.



Recitations


Recitations are primarily for going over lecture material in more detail, for answering questions and for reviewing homework and exams. Recitation attendance is optional, and you may attend any recitation you wish. However, if you are having trouble with the course, you will be expected to attend recitations weekly; doing so may keep you from failing. No recitations during the first week.



Grading



ACTIVITIESPERCENTAGES
Homework40%
Midterm Exam20%
Final Exam40%



Homework


40% of grade. There will be 6 biweekly problem sets. Cooperation policy: Permitted (though not encouraged). If you do cooperate on some problems, then solutions must be written up individually (not copied). Using outside or online materials is not permitted. Homework is due on Thursdays by 11:00 am sharp. Late homework will be accepted the following day up to 1:00 pm, but will be charged a 1 point per problem (out of the 10 point maximum) late penalty. Homework submitted after that will not be graded but will be kept for reference.



Exams


One midterm (20% of grade) during a class session and one final exam (40% of grade) during finals week. The exams are both open book and open notes. You may only use the class textbook and notes you took in lectures and in recitation (i.e. no other books or print-outs of other courses' problems).


 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.