2011-2013 Undergraduate and Graduate Catalog (with addenda) 
    
    Nov 03, 2025  
HELP
2011-2013 Undergraduate and Graduate Catalog (with addenda) [ARCHIVED CATALOG]

Facebook this Page (opens a new window)
Tweet this Page (opens a new window)

CS 6753 Theory of Computation

3 Credits
This course introduces the theory of computation. Topics: Formal languages and automata theory. Deterministic and non-deterministic finite automata, regular expressions, regular languages, context-free languages. Pumping theorems for regular and context-free languages. Turing machines, recognizable and decidable languages. Limits of computability: the Halting Problem, undecidable and unrecognizable languages, reductions to prove undecidability. Time complexity, P and NP, Cook-Levin theorem, NP completeness.

Prerequisite(s): Graduate status and CS 6003  or instructor’s permission.
Weekly Lecture Hours: 3 | Weekly Lab Hours: 0 | Weekly Recitation Hours: 0


Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Catalog Navigation
  Bulletin Home
  Institute Profile
  Administration and Board of Trustees
  Admissions, Financial Aid, Tuition and Fees
  Administrative Offices
  Communication Policy
  Institute Compliance and Other Guidelines
  Statistics on Enrollment and the Student Body
  2011-2013 Academic Calendar
  Academic Department, Degree and Program Information
  List of Academic Programs and Curricula
  Course Descriptions
  Undergraduate Academic Requirements and Policies
  Graduate Academic Requirements and Policies
  Academic Success, Advising and Tutoring Services
  Registration
  Special Programs
  Student Services
  Index of HEGIS Codes
  Previous PDF Catalogs
  2011-2013 PDF Catalog