CSE 318 Introduction to the Theory of Computation (3)


Hector Munoz-Avila (Spring 2018)

Current Catalog Description

Formal study of theoretical computational models: finite automata, pushdown automata, and Turing machines. Study of formal languages: regular, context-free, and decidable languages. Prerequisite: CSE 261 or MATH 261.


Micheal Sipser, "Introduction to the Theory of Computation", 3rd Edition, ISBN 978-1133187790


CSE 318 substantially supports the following student enabled characteristics

A. An abiity to apply knowledge of computing and mathematics appropriate to the discipline


Students will:

  1. Understanding theoretical capabilities and limitations of algorithms as a function of the problems they can/cannot solve
  2.  Formal understanding of the notion of nondeterministic computation
  3.  Understanding the classes of machines, as per the Chomsky hierarchy, their capabilities and limitations
  4.  Understanding the principles of formal languages

Major Topics Covered in the Course

  1.  Regular Languages
    • Regular expressions
    • Finite automata
    • Non regular expressions
  2. Context-free languages
    • Context-free grammars
    • Pushdown automata
    • Non context-free languages
  3.  Computational Theory
    • Turing machines
    • Decidable languages
    • Turing-recognizable languages
    • Turing-enumerabililty
    • Definition of algorithm
  4.  Non-decidable languages
    • Halting problem
    • Diagonalization methods

Assessment Plan for the Course

The students are giving weekly homework assignments on each of the topics covered in the course. There are two exams and a final exam.

How Data in the Course are Used to Assess Program Outcomes: (unless adequately covered already in the assessment discussion under Criterion 4

Each semester I include the above data from the assessment plan for the course in my self-assessment of the course. This report is reviewed, in turn, by the Curriculum Committee.

© 2014-2016 Computer Science and Engineering, P.C. Rossin College of Engineering & Applied Science, Lehigh University, Bethlehem PA 18015.