Class: Tuesdays and Thursdays, 12:30pm–1:50pm in Ryerson 251
Tutorial: Wednesdays, 6:30pm–7:30pm in Ryerson 277
Canvas course page for homework submissions: CMSC 28100 1 Intro Complexity Theory
Piazza course page for discussions: CMSC 28100-1 / MATH 28100-1
|
Instructor: Office Hour: Tuesdays, 2:00pm–3:00pm |
Teaching Assistant: Office Hour: Wednesdays, 2:30pm–3:30pm |
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 and Jeffrey Ullman, 1st edition, published by Addison Wesley, ISBN# 020102988X.
by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, 3rd edition, published by Addison Wesley, ISBN# 0321462253.
(1st edition is better.)
Other useful texts:
Introduction to the Theory of Computation
by Michael Sipser. Publisher: Course Technology; 3rd edition. ISBN-10: 113318779X, ISBN-13: 978-1133187790.
Computational Complexity: A Modern Approach (draft can be found in the official website)
by Sanjeev Arora and Boaz Barak. Publisher: Cambridge University Press; 1st edition. ISBN-10: 0521424267, ISBN-13: 978-0521424264.
Computability: An Introduction to Recursive Function Theory
by Nigel Cutland. Publisher: Cambridge University Press; 1st edition. ISBN-10: 0521294657, ISBN-13: 978-0521294652.
Homeworks:
Will be posted here every Thursday, due next Thursday at noon, electronically on Canvas.
Solutions will be posted after due date.
LaTeX files can be found here.
Homework 1 due October, 5th (at noon) — Solution
Homework 2 due October, 12th (at noon)
—
Solution
A technical mistake was found in the original file. The link above is the correct version as of October 7th.
Homework 3 due October, 19th (at noon) — Solution
Homework 4 due October, 26th (at noon) — Solution
Homework 5 due November, 2nd (at noon) — Solution
Homework 6 due November, 9th (at noon) — Solution
Homework 7 due November, 16th (at noon) — Solution
Homework 8 due November, 28th (Tuesday after Thanksgiving) (at noon) — Solution
Bonus Homework (optional), due November, 28th (Tuesday after Thanksgiving) (at noon) — Solution
Last modified: Nov 28, 2017 13:48, Central Standard Time