CPSC 627 Theory of Computability
Spring 08

Textbook

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

Goal

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.

Topics

• Finite automata and regular expressions: deterministic finite automata, nondeterministic finite automata, regular expressions, equivalence, closure properties, pumping lemma.
• Context-free grammar and pushdown automata: context-free grammar, pushdown automata, equivalence, Chomsky normal form, pumping lemma, closure properties.
• Turing machines: Turing machines, variants, nondeterministic Turing machines.
• Decidability and undecidability: decidability, halting problem, Rice's theorem, Post correspondence problem.
• NP-completeness: P and NP, Cook's theorem, NP-complete problems.
• Selected Topics: approximation algorithms, randomized algorithms, fixed parameter tractability, parallel algorithms, cryptography, quantum computing, DNA computing.

Grading

• Homework assignments (30%): short written assignments handed out every one or two weeks.
• Two midterms (20% each).
• Presentation (30%): towards the end of the semester, each student will give a 20-minute presentation on a topic of interest.

Prerequisites