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.


Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics


Valid HTML 4.01!Valid CSS! Last modified: Thursday, 29-May-2014 15:12:53 EDT


Menu:ShowHide