15-453 Formal Languages,
Automata and Computation
Spring 2013, TTH 12:00-1:20, GHC 4102
Handout | What's New]
Lenore Blum (lblum@cs), Gates 7105.
Office Hours: Tuesday 2-3pm, Gates 7105
Max Illfelder (millfeld@andrew)
Office Hours: Monday 4:30-6:30pm, NSH 4113
Max Tucker da Silva (mltucker@andrew)
Office Hours: Thursday 4:30-6:30, NSH 4113
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 examination.
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:
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.
student 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