6.045/18.400 Automata, Comput, & Complexity
Spring 2010
Instructors: Scott Aaronson, Nancy Ann Lynch
TAs: Aleksandr Arkhipov, Matthew S Peairs
Lecture:
TR2.30-4
(32-124)
Recitation1: F11
(34-301)
Recitation2: F2
(34-303)
Scott's office hours: M1-3
(32-G638)
Matt's office hours: T4-5, W2-3
(32-G500, near the elevators)
Information:
This course provides a challenging introduction to some of the central ideas of theoretical computer science. Beginning in antiquity, the course will progress through circuits and decision trees, finite automata, 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.
Relation to other courses: For Spring 2010 this
course is a combination of the traditional version of 6.045 that
has been taught in the past and the Spring 2008 Special Subject
course 6.080 "Great Ideas in Theoretical Computer
Science". There is significant overlap between 6.045 and
6.840. However, as a graduate course, 6.840 is able to cover topics
in much more mathematical depth.
Please see the syllabus for more information.
Announcements
Final Exam Grades are Posted
Your grades are available on Stellar. The average was 142.55/200 with a standard deviation 40.42.As for course policy, we will not be handing back exams, posting the exam, or posting solutions. We will try to arrange a time and place for you to look at (but not keep) your graded exam.
Announced on 18 May 2010 1:32 a.m. by Aleksandr Arkhipov
HKN course surveys
Today is the last day that the 6.045 evaluation will be open, so send the HKN Guide your feedback before it's too late. The Course VIers of the future will thank you!
Announced on 17 May 2010 6:23 p.m. by Matthew S Peairs
Psets Available for Picking in Stata Basement Lab (32-083)
Newly graded psets are available to pick in the the 32-083 lab cluster. The lab is (I believe) open 24/7. The psets currently there are:4a, 4b, 5a #3 and #4, 5b, 6a #1
You can get the the lab by taking the stairs down from the first floor, across from 32-144 and the pueblo mural, the going left in the basement. If you're course 6, you should know the lab combo - otherwise, ask a friend or knock to be let in. Once you enter the lab, go all the way left - the psets are on a table.
Since searching for your problems takes a while, please kindly amortize the process by splitting off piles of each problem as you search, as a courtesy to students who come later.
Announced on 15 May 2010 5:51 p.m. by Aleksandr Arkhipov
Question Session in Recitation Tomorrow
I will hold a finals question-and-answer session tomorrow (Friday) in recitations times and rooms, at 11:00 in 34-301 and at 2:00 in 34-303 (there's no official recitation since class is over). I will go over problems you're interested in and answer any questions you have. If you'd like me to address a specific topic or problem, please e-mail me in advance.Happy studying,
Alex
Announced on 13 May 2010 4:57 p.m. by Aleksandr Arkhipov
Optional Homework 7 Solution Posted
The solutions are up for the study guide 7, an optional homework that covers quantum computing material from classes 23-25. Even though the assignment isn't graded, there will be questions on quantum computing on the final, so it is recommended that you try the homework or at least look at the solutions as part of your studying. Be sure to gain facility with quantum computing operations, especially those involving multiple qubits. Please feel free to come to office hours or e-mail us with questions.Announced on 13 May 2010 2:16 p.m. by Aleksandr Arkhipov
