Introduction to the Theory of Computation

Course Description:

In this directed reading course you will learn the fundamentals of the theory of computing. We will rely on material from the textbook, "Introduction to the Theory of Computation" by Michael Sipser.

We will explore topics such as finite automata, regular expressions, context-free grammars, Turing machines, and computational complexity theory. The course will also cover some preliminary discrete mathematics background.

This course is ideal for students who are interested in computer science and/or mathematics. No prior experience is required.

Course Goals:

To introduce students to the fundamental concepts of theoretical computer science

Course Outline:

Week 1: Mathematical background (Proofs) 

Week 2: Finite automata and regular expressions

Week 3: Context-free grammar and pushdown automata

Week 4: Turing machines and computability theory

Week 5: Computational complexity theory and NP-completeness