Time and Location: Mondays and Wednesdays, 3:35-4:50PM, Room Memorial 107.

Instructor: Mitsunori Ogihara(email: ogihara "at" cs "dot" miami "dot" edu).

TA: Alejandro Fernandez (email: a "dot" fernandez43 "at" umiami "dot" edu).

Syllabus for Spring 2012: This course studies fundamental abstract computational models and their computational power, exploring constructive proofs to show that a model is capable of solving certain problems as well as proofs by diagonalization/contradiction to show that a model is incapable of solving certain problems. The topics covered include:

• sets, relations, and languages;
• deterministic and nondeterministic finite automata;
• regular expression;
• context-free grammar and pushdown automata;
• pumping lemma;
• basic computability theory;
• deterministic and nondeterministic Turing machines;
• undecidable problems;
• computational complexity classes;
• P and NP;
• NP-complete problems.

Textbook: Michael Sipser. Introduction to the Theory of Computation. Second Edition, Thomson Course Technology, 2006. ISBN-13 978-0534950972, list price $179.96.

Grading: The coursework consists of homework assignments (50%), quizzes (10%), and multiple (in-class) exams (40%). Below are the details.

• Homework: Homework problem sets consist of problems taken from the text book but may be selected from other sources. Percentage of correct will be used as the grade of an assignment. For the final course grade, the lowest homework grade will be removed from consideration. For example, if there are nine assignments and a student receives 80% on three, 0% on two, and 50% on four, then one of the two 0% will be removed from consideration and the average percentage of the remaining eight, (80*3 + 0 + 50*4)/8 = 55%, will be the homework grade.
• Quizzes: A quiz will be given on daily, except on the days an exam is given. The "drop-the-lowest-grade" rule will be applied here as well.
• Exams: There will be four in-class exams and there will be no finals. The grades from the exams will make equal contributions to the the final grade.
• Policy Regarding Collaboration: Collaborations on homework assignments are permitted as long as they are limited to figuring out the nature of the problems at hand and discussing how to solve them. However, collaborations beyond this limit, such as writing down a solution collaboratively and copying someone else's solution with slight modifications, are prohibited. Violations will result in grade reduction.
• Collection of Homework Papers, Tardiness : Homeword papers are due at the beginning of the class (i.e., 3:35PM) on their due date. Late submissions are accepted, but the grade will be reduced by 25% times the number of days they are late.
• Resubmission of Homework Papers after Correction: Homework papers may be resubmitted after making corrections. Corrected papers have to be turned in within two days from the day they are returned for the first time. The actual points given will be the average between the score before correction and the score after correction. If the original paper was turned in late, then the reduction due to tardiness will be applied to the average.
• Make-ups: Because quizzes and homeworks are subject to the "drop-the-lowest" rule, there will be absolutely no make-ups for them. Extenuating circumstances (illness and accidents) will be considered if students provide official letters proving their inability to attend class.

Lecture Notes: Click this link to go to the lecture note page.

Homework Problem Sets: Click this link for the homework sets.