CSE 105 Course Description

This course introduces the basic, formal ideas underlying the notion of computation:

• regular expressions and finite automata (Chapter 1)
• context-free grammars and pushdown automata (Chapter 2)
• Turing Machines (Chapter 3)
• decidability, undecidability, and the halting problem (Chapter 4, Section 5.1, 5.3, 6.2)
• complexity of problems and NP-completeness (Chapter 7)