FLAC.WS 15-453 Formal Languages, Automata and Computation

15-453 Formal Languages, Automata and Computation
Spring 2012, TTH 12:00-1:20, GHC 4102

[Schedule/Assignments | Project Handout | What's New]

Instructor:

Lenore Blum (lblum@cs), Gates 7105.

Office Hours: Tues 2-3pm, Gates 7105

TAs:

Jeremiah Blocki (jblocki@cs), Gates-Hillman 7505, (724) 612-1476.

Office Hours: Thurs 3-4pm, Gates 7101

Greg Hanneman, (ghannema@cs) Gates-Hillman 5709

Office Hours: Fri 1:30-2:30pm, Gates 2109

Problem Solving Session (Super Office Hours):

Mon 3:30-5:30+pm, Gates 2109

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 (2nd Ed.) by Michael Sipser, 2005.

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 homeworks individually. Collaboration is allowed, but References used (including books, articles, websites, people, including yourself) must be listed!

Project: See Project Handout.