2013-03-08: Unfortunately, due to unforeseen circumstances, I will not be able to teach CS190 in Spring 2013. Sorry. -Wim
Textbook
As textbook this course will use the wonderful The Nature of Computation by Cristopher Moore and Stephan Mertens.
Description and topics
CS190 (Wim van Dam) is an upper division theory course that looks at the different ways how we can deal (or not) with the hardness of various computational problems. The course will emphasize the more recent developments that followed the discovery of NP-completeness in the 1970s such as approximation algorithms, randomized algorithms, interactive proofs, and quantum computing. Students attending this course will get the most out of it if they are still on top of the mathematics that they learned in CS40.
Topics: complexity theory, P versus NP, complexity of games, PSPACE, approximations of NP-hard optimization problems, linear programming, randomized algorithms, interactive proofs, and quantum computing
Schedule: Week I: refresher on "The Basics" such as big O notation, measuring complexity of algorithms [MM, §2] ¶ Week II and III: The P versus NP Question [MM, §§4--6] ¶ Week IV: Complexity of Games [MM, §8] ¶ Week V: Approximability and Inapproximability [MM, §9.1--3] ¶ Week VI: Linear programming [MM, §9.4--5] ¶ Week VII: Randomized algorithms [MM, §10] ¶ Week VIII: Interactive proofs [MM, §11] ¶ Week IX: Quantum Computation [MM, §15] ¶ Week X: Quantum Computation [MM, §15]
Prerequisites
CS138 and CS40 (of course). Having completed CS130A is helpful, but not necessary.