CSC365H Standard Course Description

CSC365H Standard Course Description

Enriched Computational Complexity and Computability

Owner

Faith Fich

fich@cs.toronto.edu

Course Description

Introduction to the theory of computability: Turing machines, Church's thesis, computable and noncomputable functions, recursive and recursively enumerable sets, many-one reducibility. Introduction to complexity theory: models of computation, P, NP, polynomial time reducibility, NP-completeness, heuristics and approximation algorithms, lower bounds. Emphasis is placed on conceptual understanding, proofs, and problem solving.

Background

This is an enriched version of CSC363H. It will cover the topics in CSC363H, but at a faster pace and in more depth. Certain topics which are only mentioned in CSC363H will be covered in detail in this course. Additional topics will also be covered.

Prerequisistes

CSC265H/(263H with permission of the instructor)/ (148H with permission of the instructor and strong mathematical background, such as with a specialist in Mathematics)
- familiarity with standard algorithms and reasoning about algorithm correctness and complexity, at an "advanced" level. CSC148H is accepted so that mathematics specialists may take the course.
CGPA 3.00
- enriched course

Exclusions

CSC363H
- "regular" version of this course
CSC364H
- "old" version of this course

Follow-On Courses

CSC438H
- familiarity with computational models and methods for proving undecidability
CSC448H
- familiarity with computational models and methods for proving undecidability

Learning Objectives

Understand fundamental restrictions on computability
- understand the Turing machine model and variants
- understand the notions of decidability and semi-decidability
- know various undecidable problems and understand their proofs
- understand and be able to apply techniques for showing undecidability (diagonalization, reductions)
Understand the importance of computational complexity
- understand the definitions of P and NP
- be able to demonstrate membership in P or NP
- understand NP-completeness, including the proof of Cook's theorem
- be able to apply techniques for showing NP-completeness
- know heuristics and approximation algorithms for dealing with NP-complete problems
- know standard lower bounds techniques and be able to apply them to new problems

Topics (not necessarily in this order)

Computability Theory (10 hr.)
- Turing machines
- decidability and semi-decidability
- the Halting problem
- Post Correspondence problem
- diagonalization
- many-one reductions
- recursive and recursively enumerable sets
Computational Complexity (16 hr.)
- self-reducibility and polytime transformations
- P and NP (nondeterministic Turing machines)
- NP-completeness (SAT and 3-SAT)
- Cook's theorem
- various examples of NP-complete problems
- approximation algorithms and heuristics
- lower bounds
  - information-theory lower bound
  - adversary arguments
  - reductions

Suggested Texts

REQUIRED

Introduction to the Theory of Computation
Michael Sipser, PWS Publishing Company, 1997
ISBN 0-534-94728-X

Sample Evaluation

type	weight	description
assignments	40%	4-5 assignments
midterm tests	15-20%	1-2 tests
final exam	40-45%