The right way
to teach and learn math -- my new book: Rediscovering
Mathematics

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

**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

Grades:

Academic Honesty:

**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 |

Week | Topics | Reading |

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. |
4.1- 4.2 |

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

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
Problem. |
13, 14 |

12 | Reductions and more Undecidable
problems, Post's Correspondence Problem, CFL equivalence,
CFL ambiguity. |
15 |

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 |