CPSC 627 Theory of Computability
Spring 08

Instructor: Sing-Hoi Sze
Email: shsze@cs.tamu.edu
Meeting: MWF 10:20-11:10 ZACH 223D
Office Hours: MWF 11:15-12:15 HRBB 328B or by appointment


Sipser M. (2006) Introduction to the Theory of Computation, Second Edition. Thomson Course Technology.


This is an introductory graduate level theory course which will promote better understanding of the techniques used in computer science theory, and prepare students for deeper understanding and research in various fields which employ results from theoretical computer science.

The course is divided roughly into two parts. The first part will explore the limits of computation: "what is computable" versus "what is not computable" without worrying about running time. The second part will explore the issues of complexity: "what is tractable" versus "what is not tractable" in terms of the running time requirement.

In order not to lose contact with active research areas, the last part of the course will consist of selected topics which showcase some of the newest and most fruitful techniques introduced to combat the important finding that most computational problems are likely to be intractable.




Graduate standing or consent of instructor.