CMSC 28100-1: Introduction to
Complexity Theory
Class: Tue Thu : 09:00 AM-10:20 AM in Ry 276
Tutorial:
Tue : 5 - 6 pm in Ry 255
|
Instructor:
Ketan
Mulmuley
Ryerson 165-B
mulmuley@cs.uch...
Office Hour: Thursday 10:30 - 11:30
|
TA:
Gokalp Demirci
Ryerson 162C
demirci@cs.uch...
Office Hour: Tuesday 12:30 - 1:30 @ Ryerson 162 (note slightly different time than announced in class)
|
|
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: (added by Gokalp)
Introduction to the Theory of Computation
by Michael Sipser.
Publisher: Course Technology; 3 edition, ISBN-10: 113318779X, ISBN-13: 978-1133187790
Computational Complexity: A Modern Approach
by
Sanjeev Arora and Boaz Barak.
Publisher: Cambridge University Press; 1 edition.ISBN-10: 0521424267, ISBN-13: 978-0521424264
Computability: An Introduction to Recursive Function Theory
by
Nigel Cutland.
Publisher: Cambridge University Press; 1 edition; 1 edition.ISBN-10: 0521294657
ISBN-13: 978-0521294652
|
|
Assignments:
|
|
Will be posted here every Thursday, due before class (9am strict) the
following Thursday. You can submit your hw on chalk.uchicago.edu. Hw submission on chalk will close exactly at 9am. If you're not enrolled on class's chalk web page, send me an email.
|
|
Homework 1 due April, 6 (before class) Solutions
|
|
|
Homework 2 due April, 13 (before class) Solutions
|
|
Homework 3 due April, 20 (before class) Solutions
|
|
Homework 4 due April, 27 (before class) Solution guidelines
|
|
Homework 5 due May, 4 (before class) Solution guidelines
|
|
Homework 6 due May, 11 (before class) Solution guidelines
|
|
Homework 7 due May, 18 (before class) Solution guidelines
|
|
Midterm Solution guidelines
|
|
Homework 8 due May, 25 (before class) Solution guidelines
|
|
Homework 9 due June, 1
|
|