6.045/18.400 Automata, Computability, & Complexity
Spring 2017
Professor: Ryan Williams
TAs: Nirav Bhan, Mikhail Rudoy, Elena Sergeeva
Lecture:
TR2.30-4
(4-270)
Elena's Recitation: F11-12
(36-144)
Nirav's Recitation: F12-1
(26-328)
Mikhail's Recitation: F1-2
(26-328)
(G6 Lounge)
Office Hours:
Elena's Office Hours: Mon 4 - 5pm in G6 Lounge
Mikhail's Office Hours: Tue 4 - 5pm in G6 Lounge
Nirav's Office Hours: Wed 3.30 - 4.30 in G6 Lounge
Ryan's Office Hours: Wed 10 - noon in 32-G638
Note: The G6 Lounge is the open space outside Ryan's office. It is right behind the G6 elevators.
Course Outline:
What is computation? Given a definition of a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? This course provides a mathematical introduction to these questions. In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in both pure and applied mathematics!
By the end of this course, students will be able to classify computational problems given to them, in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.) They will also gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem.
Prereq: 6.042 or the equivalent mathematics background.
Course
webpage
Sign up for
course announcements on Piazza. Password: lhwkm
Announcements
Pset 2
Dear class,As the clock winds down on Pset 1, the second one has been released! Since we didn't have many lectures recently, this homework is milder than the first.
You can find the relevant files on the Materials page or on Piazza. It's due next Wednesday, March 1st, at 11.59 pm.
As before, submissions will be via Gradescope, and the source code for the assignment (as well as the homework template) are available.
Have fun,
ryan
Announced on 22 February 2017 10:57 p.m. by Ryan Williams
Pset 1
Pset 1 is now released. You can find the Hw files on the Materials page:
It is due next Wednesday, February 22nd, at 11.59 pm. Submissions will be accepted via Gradescope as announced earlier.
In addition to the Pset, we are releasing the source code for the Pset, as well as a template of your homework to get you started. We hope this will help students who are new to LaTeX!
Announced on 16 February 2017 2:59 p.m. by Elena Sergeeva
