CS 360 Introduction to the Theory of Computing
Watch a video introduction to this course on YouTube.
Objectives
To give a basic introduction to the theoretical foundations of computer science.
Intended Audience
Some exposure to the theoretical foundations of Computer Science is considered useful for all CS graduates, especially for anyone intending to continue studies at the graduate level.
Related Courses
Prerequisites: CS 240, 241 and (MATH 239 or 249); Computer Science students only.
Antirequisites: CS 365.
Successors: CS 462.
References
Introduction to Automata Theory Languages & Computation 3rd ed., by Hopcroft, Motwani & Ullman, Published by: Addison Wesley (required)
Schedule
3 hours of lectures per week. Normally available in Fall, Winter and Spring
Outline
Finite Automata (10 hours)
Deterministic and non-deterministic finite automata and their equivalence. Equivalence with regular expressions. Closure properties. The pumping lemma and applications.
Context-free Grammars (10 hours)
Definitions. Parse trees. The pumping lemma for CFLs and applications. Normal forms. General parsing. Sketch of equivalence with pushdown automata.
Turing Machines (9 hours)
Designing simple TMs. Variations in the basic model (multi-tape, multi-head, non-determinism). Church-Turing thesis and evidence to support it through the study of other models.
Undecidability (7 hours)
The undecidability of the halting problem. Reductions to other problems. Reduction in general.
