Engineering Home Contact Us
CSE 30151
Theory of Computing
1/15/06
Spring Semester
CSE 30151Theory of Computing(3-0-3)
 The theory of automata and formal language is developed along with applications. Various classes of automata, formal languages, and the relations between these classes are studied. Restricted models of computation: finite automata and pushdown automata; grammars and their relations to automata; parsing; Turing machines; limits of computation; undecidable problems, the classes of P and NP.
  
Text:
References: H.R. Lewis & C.H. Papadimitriou, Elements of the Theory of Computation, 2nd, Prentice-Hall, , 1998,
  M. Sipser, Introduction to the Theory of Computation, , PWS Publishing Co., , 1997,
  J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd, Addison-Wesley, , 2001,
 
Faculty-in-Charge: Amitabh Chaudhary
 
Course Goals:Develop the fundamental theory of automata, Turing machines and formal languages, and to understand the power and limits of different computational models.
Prerequisites:CSE 20110, CSE 20232 and CSE 30331
Co-requisites:
  
Topics: Number of Lectures
  Introduction2
  Regular Languages & Finite Automata7
  Context-free grammars5
  Pushdown Automata5
  Turing Machines9
  Undecidable problems5
  The Classes P & NP5
  NP Completeness5
  
Course Content:
 Engineering Science 3.0 Credits
 Engineering Design 0.0 Credits
Course Grading:
 Final exam 30 %
 Assignments 35 %
 Participation 5 %
 Midterm exams 30 %
  
  
Computer Usage:Some homework and a project may require a programming in a high-level language.
Laboratory Usage:None
Special Consideration:
© 2009 Department of Computer Science and Engineering College of Engineering University of Notre Dame
384 Fitzpatrick Hall
Notre Dame, IN 46556 Phone: (574) 631-8320
Fax: (574) 631-9260