CMSC 28100-1: Introduction to
Complexity Theory
Class: Monday
and Wednesday 2:30-3:50 pm in Ry 276
Tutorial:
Friday 2:30-3:20 pm in Ry 276
|
Instructor:
Ketan
Mulmuley
Ryerson 165-B, (773)702-1270
mulmuley@cs.uchicago.edu
Office Hour: Monday
4-5 pm in Ry 165-B
|
TA:
Maia
Fraser
Ryerson 178, (773)702-6614
maia@cs.uchicago.edu
Office Hour: Tuesday
12-1 pm in Ry 178.
|
|
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.
|
|
Assignments:
|
|
Will be posted here every Wednesday, due in class the
following Wednesday.
|
|
Homework 1 (due Wednesday April 14th
– in class) - solution
|
|
Homework 2 (due Wednesday April 21st
– in class) - solution
|
|
Homework 3 (due Wednesday April 28th
– in class) - solution
|
|
Homework 4 (due Wednesday May 12th
– in class) - solution
|
|
Homework 5 (due Wednesday May 19th
– in class) - solution
|
|
Homework
6 (due Wednesday May 26th
– in class) - solution
|
|
EXAM – Monday June 7th,
1:30pm to 3:30pm in Ry 276 – GOOD LUCK!!
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|