CSC 445 Introduction to Theory of Computation

Course Goals

The primary objective of this course is to introduce students the areas of computability and complexity, fundamental topics in computer science. The course also facilitates life-long learning in computer science by providing the student with foundational material that continues to be applicable even as the discipline rapidly evolves.

Course Outcomes

A student who successfully completes this course should, at a minimum, be able to:

  1. use cardinality arguments
  2. prove a language is not regular
  3. prove a language is not context-free
  4. develop Turing machines to solve problems
  5. argue that there are non TALs
  6. define carefully P and NP and NP-complete
  7. discuss Cook's Theorem and its proof
  Computer Science Student Outcomes
Course Outcomes #1 #2 #3 #4 #5 #6 #7
1       X X    
2       X X    
3       X X    
4         X    
5         X    
6         X    
7         X