##
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

### 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

Graduate standing or consent of instructor.