CSE 318/CSE 409 (Introduction to the Theory of Computation)

Spring 2018

When and where 

Tue. & Thursday 10:45 am - noon, Room TBD 


Héctor Muñoz-Avila, munoz@cse.lehigh.edu 

Instructor's office hours 




Michael Sipser Introduction to the Theory of Computation (Second Edition)


The course studies formal properties of computation. The course addresses the following questions: Here is a cool video that presents Turing machines, one of the central topics of the course.

Students will gain a deep understanding of the capabilities and limitations of computation. As a result, they will have a unique insight to questions grappling society today related to the AI Question and technological singularity, which will be addressed in the course.

topics covered

  • The notion of computation including nondeterministic computation
  • Finite State Machines: finite automata and stack-based automata
  • Turing machines
  • Decidable Languages
  • The Church-Turing Thesis and the notion of algorithm

    Course work

    There will be homeworks and two tests.

    Students choose between taking a final exam or working on a programming project aimed at improving their understanding of topics covered by the course.


    Tests 50% (Test # 1: 25%, Test # 2: 25%)
    Final Exam or Final Project 30%
    Homework:   20%

    Last update: Oct. 10 00:17:57 EDT 2017