6.045/18.400 Automata, Comput, & Complexity
Spring 2012
Instructor: Scott Aaronson
TAs: Leonid Grinberg, Rotem Oshman
Lecture: TR2.30-4 (32-124)
Information:
[Piazza discussion site]
This course provides a challenging introduction to some of the
central ideas of theoretical computer science. Beginning in
antiquity, the course will progress through finite automata,
circuits and decision trees, Turing machines and computability,
efficient algorithms and reducibility, the P versus NP problem,
NP-completeness, the power of randomness, cryptography and one-way
functions, computational learning theory, and quantum
computing. It examines the classes of problems that can and
cannot be solved by various kinds of machines. It tries to
explain the key differences between computational models that
affect their power.
Prerequisites: We assume that you have taken 6.042 Mathematics for Computer Science, or have equivalent mathematical preparation. In particular, we will assume you have basic "mathematical maturity": i.e., that you're comfortable both reading and writing rigorous mathematical proofs.
Textbooks:
1. Introduction to the Theory of Computation by Michael Sipser -- covers most material from the first half of the course
2. Optional: The Nature of Computation by Cris Moore and Stephan Mertens -- draft available for free on the web (access info provided in class)
3. Optional: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak -- covers most material from the second half (as well as more advanced material that we won't get to in class). Draft available for free on the web.
Announcements
Final exam solutions posted
Hi everyone,Final exam solutions are now posted on Stellar (https://stellar.mit.edu/S/course/6/sp12/6.045/courseMaterial/topics/topic1/exam/final2012sol/final2012sol.pdf). Scott will be around tomorrow (Friday) 1-2:30 PM if you'd like to pick up your graded exam. Please let us know if you have any questions!
Lastly, just to repeat what Scott said, it was a pleasure having all of you in the class. Have a great summer and good luck with all your future endeavors.
Best,
Leonid
For the 6.045 Team
Announced on 24 May 2012 5:21 p.m. by Leonid Grinberg
Final review and old finals posted
Hey everyone!1. There will be a review session for the final this Wednesday 5/16 in 56-114 (note: not the same location as last time!) at 7PM.
2. We posted a bunch of practice final exams. The full 2010 and 2011 exams are posted both in their original form and with solutions. There is also an additional practice final for you to try. Solutions to it are not posted, as we will be going over them at the review session.
As always, please let us know if you have any questions.
Best,
The 6.045 Team
Announced on 14 May 2012 9:03 p.m. by Leonid Grinberg
Pset5 solutions and grades posted
Hi everyone!The solutions to pset5 have been posted at https://stellar.mit.edu/S/course/6/sp12/6.045/courseMaterial/homework/assignments/assignment5/solution/1/ps5sol.pdf. Grades have also been entered and we'll hand back graded problem sets in lecture today.
Please take a moment to look over the gradebook now, and let us know if there are any discrepancies. If there is a grade missing for an assignment you actually submitted, etc., it's going to be a lot easier to resolve earlier rather than later!
Best,
The 6.045 Team
Announced on 10 May 2012 1:23 p.m. by Leonid Grinberg
Problems 6-7 on the pset are now extra credit
Hi everyone,Friday is the last day we're allowed to have homework due, and since we didn't get to some of the material necessary for problems 6-7 on the pset, those problems are now extra credit. The problem set is still due Friday 5/11.
Good luck and please let us know if you have any questions or
concerns!
—The 6.045 Staff
Announced on 08 May 2012 4:14 p.m. by Leonid Grinberg
A few announcements (pset4, remaining pset3's, last Friday's recitation)
Hi everyone,A few things:
(1) The solutions to problem set 4 have been posted. Please take a look and let us know if something doesn't make sense.
(2) The remaining pset3's that were submitted after the deadline have now all finally been graded. We'll have them for you at Tuesday's lecture, but you can look at the grade now on Stellar. As of right now, all grades (except pset4) have been posted, so Stellar reflects your up-to-date grade in 6.045. If you believe there's a mistake (particularly with a problem marked "X"), please let us know ASAP.
(3) I'd like to apologize to students in the Friday 11AM recitation. I forgot that I was supposed to cover for Rotem this week, so I'm sorry you guys just had to sit there. Most of what you missed was a probability review, so if you followed lecture from last week (Markov Inequality, Chernoff bound, and the motivations and definitions of the various probabilistic complexity classes), you should be good. As always, please feel free to ask on Piazza or come to office hours if something doesn't make sense.
Best,
Leonid
Announced on 22 April 2012 5:22 p.m. by Leonid Grinberg
