Course»Course 6»Spring 2013»6.045/18.400»Homepage

6.045/18.400  Automata, Comput, & Complexity

Spring 2013

home page image

Instructor: Scott Aaronson

TAs: Arturs Backurs, Shalev Ben David

Lecture:  TR2.30-4  (32-141)        

Information: 

[Syllabus]

[6.045 Piazza site]

[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

3. Optional: The Nature of Computation by Cris Moore and Stephan Mertens

4. 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.

See the 6.045 Curricular Goals Map giving a dynamic graphical display connecting the class outcomes with the outcomes of other subjects in the Course 6 curriculum.

Announcements

Final exam grades

Hi everyone,

As some of you might have seen already, all the grades are now up on Stellar for everyone who took the final today.  Some statistics: the mean was 117.2 (out of an absolute maximum of 200), the high score was 166, the low scores were in the 70s, and the standard deviation was 25.6.  This is better than I was expecting!  After seeing the pained expressions on people's faces this morning, I told Arturs and Shalev that I guessed the mean would be somewhere around 100.  Also, like with the midterm, there were no long-answer questions that no one managed to solve correctly.  We haven't yet done the course grades -- except in unusual circumstances, we plan to submit them by Friday -- but for calibration purposes, you might want to know that the average course grade in past years has consistently been a B.

Important: There are 4 students who have yet to take the final exam.  So please do not post anything about the exam on Piazza (and, obviously, don't discuss the exam with any student who hasn't yet taken it).

Some other loose ends: Arturs and Shalev will prepare a typed answer key to the final, for those who are interested.  You're also welcome to pick up your final from my office next week, later in the summer, or even in the fall if you still care then and I can still find the exams. :-)  For various reasons, we can't give them back this week, but you can come tomorrow or Friday to review your final in my office if you really can't wait.  Just send me an email to make sure I'll be around.

The graders are also hard at work on pset6, and will be finished grading it by tomorrow.  I sincerely apologize that we weren't able to get pset6 back to you before the final -- that was a significant screwup on our part.  Once it's ready, pset6 will also be available for pickup from the pset boxes outside my office.

Anyway, thanks so much to all of you for sticking with this class till the end!  You were awesome, and I hope you enjoyed taking the class at least Ω(1/poly(n)) as much as I enjoyed teaching it.  Have a wonderful summer.

All the best,
Scott

Announced on 22 May 2013  8:27  p.m. by Scott Aaronson

Final exam reminder

Hi everyone,

Just a reminder that the final exam will be tomorrow 9AM-12PM (starting promptly, so I strongly recommend getting there by 8:50), in room 50-340, the Walker Memorial 3rd floor gymnasium:

http://web.mit.edu/registrar/classrooms/exams/rooms/Walker.html

If, for any reason whatsoever, you can't make this exam and/or require special arrangements, then please respond to this email today letting me know -- even if you've already done so.  It would be helpful to me to have a complete list so that we can plan the makeup(s).

It was wonderful having all of you in the course.  Good luck on the final!!

--Scott

Announced on 21 May 2013  10:42  a.m. by Scott Aaronson

Additional Office Hours

Hi Class,

I will hold additional office hours on Monday from 1pm to 2pm in the G6 lounge.

Shalev

Announced on 16 May 2013  7:30  p.m. by Shalev Ben David

Extra office hours

Hi everyone,

I will hold extra office hours this Friday at 3:30-4:30 pm in the G6 open space.

Best,
Arturs

Announced on 16 May 2013  12:24  p.m. by Arturs Backurs

Readings for Lectures 18-23

Lecture 18 - "Lecture 14: Probabilistic Complexity Classes" notes
Lecture 19 - "Lecture 15: Derandomization / Crypto Double Feature" notes
Lecture 20 - "Lecture 16: Private-Key Cryptography" notes
Lecture 21 - "Lecture 17: Public-Key Cryptography" notes
Lecture 22 - "Lecture 18: Cryptographic Protocols" notes
Lecture 23 - "Lecture 22/23: Quantum Computing" notes until section 2.2

Announced on 13 May 2013  10:49  p.m. by Arturs Backurs

View archived announcements