• For more updates and announcements, see the Assignments page.
• Final Exam: Tuesday, May 5, 5:30-8:30 PM, in Baker Hall 136A.

• Project has been posted. See Assignments page.
• The due date for the Bonus Problem of Homework 7 has been extended.
• Midterm exam grade distribution. Note that there was a mistake in what was posted on the blackboard in class.

      100-102: 3
        95-99: 4
        90-94: 3
        85-89: 4
        80-84: 7
        75-79: 4
        70-74: 1
        65-69: 1
         0-60: 1 

• Solutions to problems 4 and 6 of Homework 6 have been posted.
• Solutions to Homeworks 4, 5, and parts of 6 have been posted. Some possible topics to be covered on the exam have been posted on the Assignments page.
• Midterm Exam is on Tuesday, March 3, 2009. It is closed-book and closed-notes.
• Homeworks 1, 2, 3, and 4 have been returned.
• The book Introduction to Automata Theory, Languages, and Computation is on reserve in the Engineering library in Wean Hall.
• Lecture notes on BDDs have now been posted.
• If Denny is not in his office, you may slide your Homework 4 under his door.
• HW 2 Grading Notes (Problem 4(c) was counted as an extra credit problem worth up to extra 8 points.)
• The handout entitled "Lecture 15 Myhill-Nerode Relations" and "Lecture 16 The Myhill Nerode Theorem" contains all that you need to know to solve the Nerode homework problems.
• Yi Wu has cancelled his office hours for Friday Feb 13.
• Due date for Homework 4 has been changed.
• For Problem 1 of Homework 3, you don't need to explicitly give a DFA; it would suffice to give an NFA and say something like "This NFA can be converted to a DFA using the standard construction".
• A solution to the Extra Credit problem of Asgn 1, based on the method discussed in class, is now posted.
• Mon Jan 12, 2009: Welcome to FLAC!

Topics (tentative):

• 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.

Tue and Thu, 1:30 -- 2:50 PM,  Wean Hall 5302

Professor: Edmund M. Clarke Email: e​mc A​T c​s DOT cmu DOT e​du Office: Wean Hall Rm 7117 Phone: (412) 268-2628    Office hours: Immediately after class

Teaching Assistant: Will Klieber Email: w​klieber A​T c​s DOT cmu DOT e​du Office: Wean Hall Rm 3713 Phone: 412-268-5944 Office hours: Wed 12:30 pm -- 1:15 pm, and immediately after class

Teaching Assistant: Yi Wu Email: y​iwu A​T c​s DOT cmu DOT e​du Office: Wean Hall Rm 3713 Phone: 412-268-5944 Office hours: Friday 4:30 -- 5:30 pm (2/13 cancelled)

Course Secretary: Denny Marous d​cm AT c​s DOT cmu DOT e​du Office: Wean Hall Rm 7116 Phone: (412) 268-7660 Fax: (412) 268-5576

(Yes, both TAs are located in the same office.)