CMSC 28100-1: Introduction to
Complexity Theory
Class: Tuesday and Thursday 1:30-2:50 pm in Ry 251
Tutorial:
Thursday 6:00 pm
|
Instructor:
Ketan
Mulmuley
Ryerson 165-B
mulmuley@cs.uchicago.edu
Office Hour: Tuesday 3:00-4:00 pm
|
TA:
Aritra Sen
Ryerson 178
aritrasen@cs.uchicago.edu
Office Hour: Wednesday 2:30-3:30 pm.
|
TA:
Yuan Li
Young 208B
yuanli@cs.uchicago.edu
Office Hour: Monday 4:30-5:30 pm.
|
|
Overview:
Computability
topics are discussed, including the s-m-n theorem, the
recursion theorem and resource-bounded computation. This course
introduces complexity theory. Relationships between space and
time, determinism and nondeterminism, NP-completeness, and the
P versus NP question are investigated.
Text:
|
|
Introduction
to Automata Theory, Languages, and Computation
by
John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, 3rd edition,
published by Addison Wesley, ISBN# 0321462253.
Other useful texts:
Introduction to the Theory of Computation
by Michael Sipser.
Publisher: Course Technology; 3 edition, ISBN-10: 113318779X, ISBN-13: 978-1133187790
|
|
Assignments:
|
|
Will be posted here every Thursday, due in class the
following Thursday.
|
|
Homework 1 due April, 14 (before class)
Homework 2 due April, 21 (before class)
Homework 3 due April, 28 (before class)
Homework 4 due May, 12 (before class)
Homework 5 due May, 19 (before class)
Homework 6 due May, 26 (before class)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|