|
|
|
|
15-453 Formal Languages, Automata, and
Computation
Spring 2008
TTH 1:30-2:50, WeH 5302
|
|
[Schedule/Assignments
| Project Handout | What's New]
NOTE : THE FINAL EXAM WILL BE IN
DOHERTY HALL RM 1112
Instructors:
Lenore Blum (lblum@cs), Wean 4105. Office
Hours: Tues 3-4pm.
Ryan Williams (ryanw@cs), Wean 4112. Office Hours: Thurs 3-4pm.
TAs: Yong Lu (lyongu@cs), Wean 4104. Office Hours: Mon 5-6pm Shobha Venkataraman (shobha@cs), Wean 3711. Office Hours: Wed 3-4pm Problem Solving Sessions: TBA |
|
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
and space complexity, classes P, NP, and PSPACE, NP-completeness,
PSPACE-completeness, the polynomial hierarchy, randomized time
complexity, classes RP and BPP.
|
|
Textbook: Introduction to the Theory of
Computation (2nd Ed.) by Michael Sipser, 2005.
Prerequisites: 15-212 and 15-251 (or 21-228).
Grading: Homework, 25%; Final, 25%; Midterm I,
15%; Midterm II, 15%; Project 15%; Class Participation, 5%. Attendance is
required.
Homework: Homework is due one week after it is
assigned. Late homework will be accepted only under exceptional
circumstances. Each student must do their own work and hand in their own
homework individually. Collaboration is allowed, but any references
used (including books, articles, websites, people, including yourself)
must be listed!
|
|
|
|