CSE 350 Tentative Weekly Schedule Here's a tentative schedule for 13 weeks. Intercalated into this schedule will also be room for a midterm exam and several other topics. week 1. Course overview. What is computation? Introduction to the halting problem. Some uncomputable problems. Why you can solve the halting problem with bounded memory. week 2. Course overview continued. Definition of formal languages and examples. A puzzle. Relations and functions. week 3. Relations and functions. Countability. Regular expressions. week 4. Regular languages. Deterministic and nondeterministic finite automata. DFAs and NDFAs both recognize regular languages. Closure properties of regular languages. week 5. Pumping lemmas. How to prove that a language is not regular. Myhill-Nerode Theorem. week 6. Myhill-Nerode Theorem. Using DFAs for string matching, and other applications of DFAs. week 7. Context tree grammars. Parse trees. Push-down automata. Context-free languages. Closure properties of context-free languages. Pumping theorem for context-free languages. week 8. Turing machines. Recursive languages. Recursively enumerable languages. Deciding/semi-deciding a language. Deterministic and nondeterministic Turing machines. week 9. A TM has the same power as a two-counter machine. Universal Turing machines. Reductions. week 10. Rice's Theorem. Practice with reductions. week 11. Introduction to complexity theory. P and NP. Cook's theorem. week 12. Practice with reductions. week 13. Advanced topics. ---------------- Here's a list of some of the topics that we'll cover in the course. Course logistics and procedures. Motivation question: what is computation and what constitutes a computer. Introduction to halting problem. Languages and other mathematical preliminaries. Set, relations, and functions. Countability. Diagonalization arguments. Pigeonhole principle Regular expressions. Regular languages. Deterministic finite automata (DFA). Nondeterministic finite automata (NFA). Computational equivalence of DFAs and NFAs. Computational equivalence of finite automata and regular expressions. Pumping theorems. Closure properties of regular languages. Minimal DFAs, equivalence classes for DFAs. Myhill-Nerode Theorem. Homing sequences. Context-free grammars (CFG). Pushdown automata (PDA). Computational equivalence of CFGs and PDAs. Closure properties of context-free languages (CFL). Pumping theorem for CFLs. Turing machines (TM). Variants of TMs: Nondeterministic TM (NTM), TM with multiple tapes. Computational equivalence of TMs and variants. Church's thesis. Recursive, recursively enumerable (RE) and co-RE languages. The halting problem. Diagonalization arguments revisited. Rice's theorem and reductions. P vs NP problem. Why the Satisfiability problem is NP-complete. Brief introduction to reductions and NP-completeness arguments. Brief introduction to zero-knowledge proof.