|
|
|
|
15-453 Formal Languages,
Automata and Computation
Spring 2013, TTH 12:00-1:20, GHC 4102
|
|
[Schedule/Assignments
| Project
Handout | What's New]
Instructor:
Lenore Blum (lblum@cs), Gates 7105. Office Hours: Tuesday 2-3pm, Gates 7105 TAs: 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.
Topics
- Automata
and Languages: finite automata,
regular languages, pushdown automata, context-free
languages, pumping lemmas.
- Computability
Theory: Turing
Machines, decidability, reducibility, the arithmetic hierarchy the recursion
theorem, the Post correspondence problem.
- Complexity
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.
Errata
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
is required.
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.
Each
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
Handout.
|
|
|
|