CMPS 3140 Theory of Computation
Catalog Description
CMPS 3140 Theory of Computation (3 units)
An introduction to computability theory to include finite automata, push-down automata, formal grammars, Turing machines, decidability, intractability and NP-completeness. CMPS 3120.
Prerequisites by topic
Algorithm analysis.
Big-oh notation.
Units and Contact Hours
3 semester units. 2 units lecture, 1 unit lab.
Elective for CS.
Required Textbook
Introduction to the Theory of Computation (1st edition) by Michael Sipser
Recommended Textbook and Other Supplemental Materials
Donna Meyers
Student Learning Outcomes
This course covers the following ACM/IEEE Body of Knowledge student learning outcomes:

CC-AL: Algorithms and Complexity
CE-PL: Programming Languages

ABET Outcome Coverage
The course maps to the following program/student outcomes for Computer Science (CAC/ABET) and Computer Engineering (EAC/ABET):

(CAC PIb1): Identify key components and algorithms necessary for a solution.
Assessed by final exam.

Lecture Topics and Rough Schedule

Introduction to automata, computability, and complexity week 01
Automata and languages
week 02
Regular languages
week 03
Finite automata
week 04
Context-free languages
week 05
Push-down automata
week 06
Church-Turing thesis
week 07
Decidability & reducibility
week 08
Time complexity
week 09
week 10
Space complexity
week 11
week 12
Circuit complexity
week 13
Parallel computation
week 14
week 15

Grading Policy
                                    A   93%
                                    A-  90%
    10 HW/Labs...15%                B+  87%
    2 Midterms...60%                B   83%
    Final Exam...25%                B-  80%
                                    C+  77%
                                    C   70%
                                    C-  65%
                                    D+  60%
                                    D   50%
                                    D-  40%
                                    F  below 40% 
Estimated ABET Category Content
Algorithms and Complexity: 3 Credit Hours
Prepared By
Donna Meyers, June 2014.
Approved by CEE/CS Department, June 2014.
Effective Fall 2013