CPSC 627 Theory of Computability
Instructor: Sing-Hoi Sze
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.
- 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
- Turing machines: Turing machines, variants, nondeterministic Turing
- Decidability and undecidability: decidability, halting problem, Rice's
theorem, Post correspondence problem.
- NP-completeness: P and NP, Cook's theorem,
- Selected Topics: approximation algorithms, randomized algorithms, fixed
parameter tractability, parallel algorithms, cryptography, quantum computing,
- 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.
Graduate standing or consent of instructor.