15-453 Formal Languages,
Automata and Computation
Spring 2014, TTH 12:00-1:20, GHC 4215
Info | What's New?]
Lenore Blum (lblum@cs), Gates 7105.
Office Hours: Tuesday 2-3pm, Gates 7105
Asa Frank (firstname.lastname@example.org)
Office Hours: Friday, 5:30-7:30pm, GHC 6002
Aashish Jindia (ajindia@andrew)
Office Hours: Sunday, 6-8pm, Wean 5316
Andrew Smith (adsmith@andrew)
Office Hours: Monday 5:45-7:45pm, Room GHC 7101
This course provides an introduction to formal
languages, automata, computability, and complexity. The course consists
of a traditional lecture component supported by weekly homework
assignments and a course project. There are two midterms and a final
and Languages: finite automata,
regular languages, pushdown automata, context-free
languages, pumping lemmas.
Machines, decidability, reducibility, the arithmetic hierarchy the
recursion theorem, the Post correspondence problem.
Theory: time complexity, classes P and NP,
NP-completeness, space complexity PPACE, PSPACE-completeness, the
polynomial hierarchy, randomized complexity, classes RP and BPP.
Textbook: Introduction to the Theory of
Computation (3rd Ed.) by Michael Sipser, 2012.
for 3rd Edition: http://math.mit.edu/~sipser/itoc-derrs3.1.html
Prerequisites: 15-251 (or 21-228).
Grading: Homework, 25%; Class Participation,
5%; Midterm I, 15%; Midterm II, 15%; Final, 25%; Project 15%. Attendance
Homework: Homework is due one week after it is assigned
and should be handed in at the beginning of class. Late homework will be
accepted only under exceptional circumstances. All assignments must be
typeset (exceptions allowed for diagrams). Each problem should be done on
a separate page.
is to do their own work and hand in their own homework individually.
Collaboration is allowed, but References used (including books, articles, websites, people, including
yourself) must be listed!
Project: See Project