An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expression. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.
This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages. The course stresses the understanding of the basic concepts and constructions.
Please see Prerequisites page.
Equivalent to Math 166. Credit not offered for both Math 166 and CSE 105. Restricted to undergraduates with sophomore, junior, and senior standing. Graduate students will be allowed as space permits.
Three sections per year. Please see Tentative Course Offerings page.