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.
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

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