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.
Type
Elective for CS.
Required Textbook
Introduction to the Theory of Computation (1st edition) by Michael Sipser
Recommended Textbook and Other Supplemental Materials
None.
Coordinator
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
NP-completeness
 week 10
Space complexity
 week 11
Intractability
week 12
Circuit complexity
week 13
Parallel computation
 week 14
Cryptography
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.
Approval
Approved by CEE/CS Department, June 2014.
Effective Fall 2013