The right way
to teach and learn math -- my new book: Rediscovering
Lectures: MWF 1:00 - 1:50, Room SES-238
Office Hours: I will be in my office (1216 SEO)
every Monday and Wednesday from 9:30 - 11:30. You are
welcome to see me anytime I am in, and if you cannot make those
hours, feel free to email me about another time.
Description: A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.
Text: Introducing the Theory of Computation by Wayne Goddard, Jones and Bartlett Publishers, 2009.
Exams: There will be 6 quizzes (40% total) and one final examination (35%). Each quiz will be worth 20 points and the lowest quiz grade will be dropped. Quizzes will be taken in discussion sections and administered and graded by the TAs.
Discussion Sections: The TAs will alternate between
giving quizzes, and reviewing HW and quizzes. You are
expected to attend the discussion section for which you are signed
up. The TAs will take attendance and it will be counted in
your HW grade. Lab times: 11 AM meets at 208 Burnham,
and 12 PM meets at 117 Taft.
The teaching assistant this semester is: Iman Mirrezaei Office Hours: 1212 SEO Tuesday 3:30-5:30
Assignments: Homework assignments will be worth 25% of your grade (6.25% each assignment). The HWs are meant to force you to study and practice. If you work hard and meet with the TAs and myself, you can always be sure to work through every problem and get full credit. You may work with a partner on the homework and submit one assignment for both of you. If you choose to do this, then stick together all semester. It is easier to work with a partner but you will get less practice.
Special Dates: April 16 and 21 are
Jewish holidays and I will not lecture on those dates. There
will be a substitute lecturer, or a quiz.
|assignment 1||assignment 2||assignment_3||assignment 4|
|1||Introduction: Languages, Grammars, and Automata (Machines). Fundamental connection to computer science. Applications.||5|
|2||Regular Sets: Finite State Machines, Regular Expressions, and Regular Grammars||1, 2, 8.1
|3||Nondeterminism and equivalence of NFSM's to DFSM's. Other variants of FSM's||3|
|4||Closure Properties of Regular
Sets - a constructive review. Encoding FSMs,
diagonalization, and a non-regular set.
|5||The Pumping Lemma - How to show that a set is not Regular.||4.3|
|6||Decision Algorithms for FSM's. (Problems whose inputs are FSM's.) Decidability.||4.2|
|7||Context Free Languages:
Context Free Grammars and Applications, Syntax Diagrams.
|8||Pushdown Machines - Deterministic versus nondeterministic.||7|
|9||Chomsky Normal Form - Three applications. Equivalence of NPDM and CFL's.||8, 9.1
|10||Closure Properties of CFL's and DCFL's. Decision Algorithms for CFL's. Applications to compilers.||10.1, 10.2
|11||The CFL Pumping Lemma - Showing that a set is not context free.||9.2
|12||Turing Machines and Variants: Multitape, nondeterminism, multidimensional, 2-stack machines.||11, 12|
|11||Decidability: The Halting
|12||Reductions and more Undecidable
problems, Post's Correspondence Problem, CFL equivalence,
|13||Computational Complexity - Measuring the time and space requirements of decidable problems.||17, 18
|14||The computational classes P and NP. The concept of an NP-Complete Problems. Reductions revisited.||17.6, 19|