(Coordinator: Mark Bochert)

Catalog description

Review of sets, relations, and languages. Induction and diagonalization. Finite automata, context-free languages, pushdown automata. Basic complexity theory.

Course Topics and Student Outcomes

Models & Abstractions (1)

• Formally define and reason about discrete mathematical structures and concepts (sets, relations, functions, cardinalities, counting.)
• Synthesize and evaluate elementary mathematical arguments as they apply to formal models of computation
• Determine a language's location in the Chomsky hierarchy (regular languages and context-free languages)
• Prove that a language is in a specified class and that it is not in the next higher class
• Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs

Evaluation

• Weekly homework assignments (20%)
• Weekly quizzes (40%)
• Two exams (40%)

Topics

• Review of basic discrete mathematics including:
  • Logic, sets, relations, functions, induction and counting
• Limitations of computation:
  • Diagonalization method, cardinality, halting problem
• Models of computation:
  • Alphabets and languages
  • Regular languages and regular expressions
  • Deterministic and nondeterministic finite automata
  • Context-free languages and pushdown automata

Textbooks

• James L. Hein, Discrete Structures, Logic, and Computability, 3rd Ed.