6.045/18.400 Automata, Comput, & Complexity
Spring 2016
Instructor: Scott Aaronson
TAs: Aleksandr Arkhipov, Nirav Bhan, Steven B Fine, Chelsea S Voss
Lecture: TR9.30-11 (34-101)
Information:
[Syllabus]Office Hours:
Tuesday 3-4 pm: Chelsea Voss
Wednesday 4-5 pm: Steven Fine
Thursday 2-3 pm: Nirav Bhan
Thursday 4-5 pm: Alex
All office hours located in open space outside 32G-638.
[Alan Turing's 1936 paper "On Computable Numbers"]
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: Quantum Computing Since Democritus by Scott
Aaronson
Announcements
Final solutions
Final exam solutions are up on Stellar.Announced on 20 May 2016 10:17 p.m. by Nirav Bhan
PS. Picking up your finals / solutions
One other thing that I forgot to mention:If you'd like to pick up your final exam to go over it, you're welcome to come by my office between now and roughly the end of July. You can email me to make sure I'll be around, as I'll be traveling for parts of the summer. Alternatively, you can also ask my administrative assistant, Debbie Lehto (dlehto@mit.edu / 32-G675A), to retrieve your exam from my office for you if I'm not around.
Meanwhile, Nirav will be scanning in my handwritten solutions to the final, and will post them on Stellar shortly.
Best,
Scott
Announced on 20 May 2016 9:09 p.m. by Scott Aaronson
Final exam grades are posted
Hi everyone,Stevie, Nirav, Alex, Chelsea, and I have finally finished grading the final exams; you can find your score on Stellar. 75 students took the final today. The mean score was 65.5 out of 100 (on Stellar, we had to list it as out of 120 because of the extra credit, but "really" it's out of 100). The low score was 25, while the high score was a spectacular 105. The standard deviation was 19.3. 10 students got 90 or above, while 18 got 80 or above. There wasn't a single problem on the exam that nobody aced, with the exception of one of the problem 4 extra credits. On the whole, I'm quite pleased with the class's performance on what the TAs assured me was a very challenging final.
We haven't yet assigned course grades, but we plan to do that by tomorrow. Of course, we'll take into account the midterm, the final, the psets, and (in borderline cases) class participation and the delta in performance over the semester.
On a personal note, I wanted to thank all of you for being part of my final class as an MIT professor, and for your questions, participation, and enthusiasm. I loved teaching 6.045 and will remember it fondly; I can only hope you got something from the course as well.
Have a wonderful summer, and "may the power of Turing be with you!"
All the best,
Scott
Announced on 20 May 2016 8:56 p.m. by Scott Aaronson
Check Gradebook
Now that all the pset grades are in gradebook, please take a look to make sure everything is consistent.Best,
TAs
Announced on 19 May 2016 6:25 p.m. by Steven B Fine
Pset 6 grades posted
Pset-6 grades are now available on Gradebook and Stellar.The maximum points for each question are:
Q1 10; Q2 10; Q3a 5; Q3b 5; Q4 10; Q5 10; Q6 10; Q7a 5; Q7b 5; Q7c 5; Q8a 4; Q8b 5 Q8c 5 Q8d 4 Q8e 4 Q8f 4 Q8g 4
Total: 105
Regards,
TAs
Announced on 19 May 2016 4:34 p.m. by Nirav Bhan
