CS 575 - Models of Computation

Bulletin Description

The formal study of computation, including computability and computation with limited resources. Church's thesis and models of computation. Formal languages and machines as recognizers of languages. The Chomsky Hierarchy of language types. Topics may include Turing machines or other basic models of computation; decidability and undecidability; basic complexity theory; finite automata and regular languages; pushdown automata and context-free languages. The course will cover primarily theory, including assignments that utilize concepts covered in lectures.

Prerequisites

CS 375 or consent of instructor.

Expected Preparation

Students should be familiar with logic, discrete mathematics, and comfortable using proof techniques such as induction.

Student Learning Outcomes

Successful students will learn:

  1. Basic models of computation, their properties and relationships among them.
  2. Notions of computability; proofs of insolvability and intractability.
  3. Foundations for complexity analysis of algorithms.
  4. Relationships between machine models and languages.
  5. Applications of these topics to program design and analysis.

Measures

Direct Measures:

Indirect Measures:

These five specific outcomes will be evaluated on the basis of student homeworks and exams that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the five outcomes performed at the end of the semester.

Syllabus Information

Possible Textbook:

Introduction to Languages and the Theory of Computation
J. Martin
McGraw Hill, 1991.

Introduction to the Theory of Computation
Michael Sipser
PWS Publishing Company