Graduate

Courses

Computer Science

B501 Theory of Computing

Credits: 3

Prerequisite(s): CSCI-C 241.

Deterministic and nondeterministic automata, regular expressions, pumping lemmas; context-free languages, parsing, pushdown automata, context-sensitive languages, LBA, LR(k) languages, closure and decidability of language classes. Turing machines, random access machines, grammars, general recursive functions, equivalence of computation models, universal machines, relative computing. Unsolvability, semi-recursive sets, Rice's Theorem. Space and time complexity, NP completeness.

Fall 2017


Instructor: Daniel Leivant
Time: Multiple Times
Location: Multiple Locations

  • Course History

      Fall 2016


      Instructor: Ladislav Novak
      Time: Multiple Times
      Location: Multiple Locations

      Fall 2015


      Instructor: Daniel Leivant
      Time: Multiple Times
      Location: Multiple Locations

      Spring 2015


      Instructor: Daniel Leivant
      Time: Multiple Times
      Location: Multiple Locations

      Fall 2014


      Instructor: Dirk Van Gucht
      Time: Multiple Times
      Location: Informatics East, Room 150

      Spring 2014


      Instructor: Daniel Leivant
      Time: Multiple Times
      Location: Multiple Locations
      Course URL (syllabus link or course homepage)

      Fall 2013


      Instructor: Dirk Van Gucht
      Time: Multiple Times
      Location: Multiple Locations

      Spring 2013


      Instructor: Daniel Leivant
      Time: Multiple Times
      Location: Multiple Locations
      Course URL (syllabus link or course homepage)

      Fall 2012


      Instructor: Dirk Van Gucht
      Time: Multiple Times
      Location: Multiple Locations

      Spring 2012


      Instructor: Dirk Van Gucht
      Time: Multiple Times
      Location: Informatics East, Room 130

      Fall 2011


      Instructor: Daniel Leivant
      Time: Multiple Times
      Location: Lindley Hall, Room 008

      Spring 2011


      Instructor: Steven Myers
      Time: 4:00PM-5:15PM Mon, Wed
      Location: Informatics East, Room 130