CMSC 28100-1: Introduction to
Complexity Theory
Class: Monday, Wednesday and Friday 1:30-2:20 pm in Ry 276
Tutorial:
Tuesday 6:00-7:00 pm in Ry 255
Midsem: Monday 1:30 in Ry 276
|
Instructor:
Ketan
Mulmuley
Ryerson 165-B, (773)702-1270
mulmuley@cs.uchicago.edu
|
TA:
Pooya
Hatami
Ryerson 278
pooya@cs.uchicago.edu
Office Hour: Thursday
4:00-5:00 pm in Ry 278.
|
|
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 Friday, due in class the
following Friday.
|
|
Homework 1 (due Friday April 8th
– in class) - solution
|
|
Homework 2 (due Friday April 22nd
– in class)
|
|
Homework 3 (due Friday April 29th
– in class)
|
|
Homework 4 (due Friday May 13th
– in class)
|
|
Homework 5 (due Friday May 27th
– in class)
|
|
Homework 6 (due Friday June 3rd
– in class)
|
|