Combining Discrete Math and Automata Theory into a Single Course

This tutorial will provide a template for how a CS program can combine its discrete math and automata theory offerings into a single course. Doing this serves two purposes. First, this allows course-limited programs (e.g., liberal arts colleges) to offer both courses in a single-semester 4-credit experience. This might help with creating space for other required offerings or to overcome staffing challenges. Second, the introduction of math concepts just in time to learn automata theory gives more motivation to computer science students to learn the math and to see how it will connect to their later CS coursework. This approach has been used by a small liberal arts college (Denison University) for the past 8 years to great success. Students start with minimal prerequisites (introductory CS and high school algebra). The course covers a wide range of topics from discrete math such as sets, strings, languages, logic, direct proof, proof by induction, proof by contradiction, combinatorics, probability, elementary number theory, asymptotic notation, graphs, loop invariants, and recurrences. Many of these topics are introduced just in time to learn about topics such as finite automata, regular expressions, closure properties, pumping lemma, context-free grammars, Turing machines, and computability. Students are usually excited to learn about Turing machines and the halting problem this early in the curriculum. This tutorial will share the resources used at Denison to teach this course in a single semester (3 days/week, 15 weeks). These will include a freely available online PDF textbook with over 250 worked examples and 550 exercises.