CENG 565 - Introduction to Theory of Computation

 

Spring 2014

 

Instructor: Faruk Polat

Catalog Description: CENG 565 - Introduction to Theory of Computation (3-0) 3 
Elements of computability theory. Turing machines, Church-Turing thesis, decidability, reducibility and recursion theorem. Complexity theory. Classes P and NP, NP-Completeness. Intractability.

  
Prerequisites: Consent of the instructor.

Course Objectives: This course introduces elements of computability theory that had lead to the model of algorithms and of algorithmically solvable problems. The course is designed to cover the theory of computability and that of complexity. The computability theory part includes the Church-Turing thesis, decidability, reducibility and recursion theorem. The complexity theory part includes time complexity, space complexity and intractability. The goal of this course is to expose students to the foundational aspects of theoretical computer science.

Textbooks:

  • M.Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997

·  Reference(s):

  •  M.R.Garey and D.S.Johnson, Computers and Intractability, W.H.Freeman & Company, 1979.
  •  H.R.Lewis and C.H.Papadimitriou, Elements of the Theory of Computation, 2nd edition, Prentice-Hall, 1998.
  •  B.Moret, The Theory of Computation, Addison Wesley, 1998.
  •  J.E.Hopcroft and J.D.Ullman, Introduction to Automata Theory, Languages and Computation, Addision-Wesley, 1979.

Course Conduct: 

Weeks

Topics

1-3

Turing Machines:

  • the definition of a Turing Machine,
  •  extensions of Turing Machines,
  •  Register Machine (RAM)
  •  Hilbert's 10th problem and Church-Turing Thesis.

4-5

Decidability

  • decidable languages
  • primitive and partial recursive functions
  • the halting problem 

6-7

 Reducibility

  • undecidable problems
  • mapping reducibility (many to one) 

8-9

Computability Theory

  • the recursion theorem
  • Rice Theorem

10-12

 Time Complexity

  •  Measuring complexity
  •  Class P
  •  Class NP
  •  NP-completeness: polynomial time reducibility, definition of NP-completeness, Cook-Levin Theorem 

13-14

Space Complexity

  • Savitch's Theorem
  • Class PSPACE
  • PSPACE-Completeness
  • Classes L and NL
  • NL-Completeness

 

 

Grading System 

  • Midterm I  30%
  • Midterm II 30%
  • Final examination 40%


Schedule 
 To be announced