CSC363H Standard Course Description

CSC363H Standard Course Description

Computational Complexity and Computability

Owner

Francois Pitt

fpitt@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.

Background

The first section of the "old" course (on efficient algorithm design) has been expanded and merged with sections from CSC270H into a new second-year course, CSC263H/265H. The rest of the "old" course has been expanded to move at a somewhat slower pace with more examples and include a discussion of lower bounds (which used to be in CSC378H) and a new section on methods for dealing with NP-complete problems (i.e. heuristics and approximation algorithms).

Prerequisistes

CSC263H/265H/(238H)
- familiarity with standard algorithms and reasoning about algorithm correctness and complexity
CGPA 3.00
- Department requirement for third year courses

Exclusions

CSC364H
- "old" version of this course
CSC365H
- "enriched" 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

Be familiar with fundamental restrictions on computability
- be familiar with Turing machines
- understand the notions of decidability and semi-decidability
- know that the Halting problem is undecidable
- understand and be able to apply techniques for showing undecidability (diagonalization, reductions)
Understand the importance of computational complexity
- be familiar with the definitions of P and NP
- be able to demonstrate membership in P or NP
- be familiar with the definition of NP-completeness
- be able to apply techniques for showing NP-completeness
- know heuristics and approximation algorithms for dealing with NP-complete problems
- know standard lower bounds for common problems

Topics (not necessarily in this order)

Computability Theory (10 hr.)
- Turing machines
- decidability and semi-decidability
- the Halting 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)
- various examples of NP-complete problems
- approximation algorithms and heuristics
- lower bounds
  - information-theory lower bound for sorting
  - adversary argument for searching, finding the maximum

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%