TA: Wei Zhou, w_zhou75 at y a h o o . c o m

Final exam and grades

• Answers to final
• Additional answer to final
• Histogram

Syllabus

See last fall's offering for an idea about the course.

Textbook:

• Harry Lewis and Christos Papadimitriou, Elements of the Theory of Computation, 2nd Edition.

Notes:

• Errata for textbook.
• Prof. Milenkovic will teach this course April 19, 21, and 23.

Assignments:

• Chapter 1.3, all odd number problems. Due Feb 4.
• Chapter 1.5, all odd number problems. Due Feb 6.
• Midterm: 2.1, 2.2, 2.3, odd problems. Due March 5, Friday. Midnight.
• Chapter 3.1, and 3.2, all odd number problems. Due after spring break.
• Chapter 4.1, 4.2, and 4.3, all odd number problems. Due April 2.
• Chapter 4.5, 4.5, 5.2, 5.3 and 5.4, all odd number problesm. Due April 16.
• Final: 5.7.1, 5.7.3; 6.1.1; 6.2 all odd number problems; 6.3.1, 6.3.3; 6.4.1; 7.1.1; 7.3 all odd except not 5.3.7. (Total of 13 problems)
  Due 7:30 PM Thursday May 13.

Practicum

• Implement that Nondeterministic Finite Automata algorithm given on page 106. The program takes the NFA descriptionfrom a file named on the command line, and then accepts strings from stdin, echoing the string indicating accept or reject by following the string with the label ACCEPT or REJECT.
• Due at the first class after spring break.
• Implement a Turing Machine simulator. The project description.

Final exam date

May 13, Thursday, 5:00-7:30.