Course»Course 6»Spring 2016»6.045/18.400»Materials

Materials

Click on topic headings to hide their contents. 

Collapse All Topics 

General

01.30.16
  Lecture 1: Intro

Last modified by: Kevin L Wu

01.30.16
  Lecture 2: Logic

Last modified by: Kevin L Wu

01.30.16
  Lecture 3: Circuits and Finite Automata

Last modified by: Kevin L Wu

01.30.16
  Lecture 4: Turing Machines

Last modified by: Kevin L Wu

01.30.16
  Lecture 5: Reducibility and Gödel

Last modified by: Kevin L Wu

01.30.16
  Lecture 6: Minds and Machines

Last modified by: Kevin L Wu

01.30.16
  Lecture 7: Complexity

Last modified by: Kevin L Wu

01.30.16
  Lecture 8: Polynomial Time

Last modified by: Kevin L Wu

01.30.16
  Lecture 9: P and NP

Last modified by: Kevin L Wu

01.30.16
  Lecture 10: NP-completeness

Last modified by: Kevin L Wu

01.30.16
  Lecture 11: NP-Completeness in Practice

Last modified by: Kevin L Wu

01.30.16
  Lecture 12: Space Complexity and More

Last modified by: Kevin L Wu

01.30.16
  Lecture 13: Randomness

Last modified by: Kevin L Wu

01.30.16
  Lecture 14: Probabilistic Complexity Classes

Last modified by: Kevin L Wu

01.30.16
  Lecture 15: Derandomization / Crypto Double Feature

Last modified by: Kevin L Wu

01.30.16
  Lecture 16: Private-Key Cryptography

Last modified by: Kevin L Wu

01.30.16
  Lecture 17: Public-Key Cryptography

Last modified by: Kevin L Wu

01.30.16
  Lecture 18: Cryptographic Protocols

Last modified by: Scott Aaronson

01.30.16
  Lecture 19: Interactive Proofs / Machine Learning

Last modified by: Scott Aaronson

01.30.16
  Lecture 20: PAC-Learning

Last modified by: Scott Aaronson

01.30.16
  Lecture 21: Learning, Chomsky, RSA, Quantum

Last modified by: Scott Aaronson

01.30.16
  Lecture 22/23: Quantum Computing

Last modified by: Scott Aaronson

01.30.16
  Lecture 24: Quantum Algorithms

Last modified by: Scott Aaronson

01.30.16
  Dating Problem + Zero Knowledge Slides

Slides from the lecture 

Last modified by: Rotem Oshman

02.11.16
  Syllabus

Last modified by: Scott Aaronson

03.31.16
  Midterm solutions

Last modified by: Nirav Bhan

05.22.16
  Final solutions restricted use

Last modified by: Nirav Bhan

02.07.16
  Pset1

Due: February 19 2016 5:00 p.m.

02.22.16
  Pset2

Due: March 04 2016 5:00 p.m.

03.06.16
  Pset3

Due: March 19 2016 11:59 p.m.

03.29.16
  Pset4

Due: April 08 2016 5:00 p.m.

04.11.16
  Pset5

Due: April 23 2016 5:00 p.m.

04.25.16
  Pset6

Due: May 08 2016 5:00 p.m.

Lecture notes

01.30.16
  Lecture 3: DFAs and NFAs

Last modified by: Matthew S Peairs

01.30.16
  Lecture 4: NFAs and Regular Expressions

Last modified by: Matthew S Peairs

01.30.16
  Lecture 5: Non-Regular Languages and the Pumping Lemma

Last modified by: Matthew S Peairs

01.30.16
  Lecture 7: Decidability

Last modified by: Matthew S Peairs

01.30.16
  Lecture 8: Undecidable Problems and PCP

Last modified by: Matthew S Peairs

01.30.16
  Lecture 9: Mapping Reducibility and Rice's Theorem

Last modified by: Matthew S Peairs

01.30.16
  Lecture 10: Self-Reference and the Recursion Theorem

Last modified by: Matthew S Peairs

01.30.16
  Lecture 12: Complexity Theory

Last modified by: Matthew S Peairs

01.30.16
  Lecture 15: More Complexity Theory

Last modified by: Matthew S Peairs

01.30.16
  Lecture 16: More NP-completeness

Last modified by: Matthew S Peairs

01.30.16
  Lecture 17: Probabilistic TMs and Complexity Classes

Last modified by: Matthew S Peairs

01.30.16
  Notes on countability, decidability, recognizability, and oracles/reducability

Last modified by: Leonid Grinberg

01.30.16
  RSA Notes

Last modified by: Leonid Grinberg

Lecture Slides as PDFs

01.30.16
  Lecture 3: DFAs and NFAs

Last modified by: Kevin L Wu

01.30.16
  Lecture 4: NFAs and Regular Expressions

Last modified by: Kevin L Wu

01.30.16
  Lecture 5: Non-Regular Languages and the Pumping Lemma

Last modified by: Matthew S Peairs

01.30.16
  Lecture 7: Decidability

Last modified by: Matthew S Peairs

01.30.16
  Lecture 8: Undecidable Problems and PCP

Last modified by: Matthew S Peairs

01.30.16
  Lecture 9: Mapping Reducibility and Rice's Theorem

Last modified by: Matthew S Peairs

01.30.16
  Lecture 10: Self-Reference and the Recursion Theorem

Last modified by: Matthew S Peairs

01.30.16
  Lecture 12: Complexity Theory

Last modified by: Matthew S Peairs

01.30.16
  Lecture 15: More Complexity Theory

Last modified by: Matthew S Peairs

01.30.16
  Lecture 16: More NP-completeness

Last modified by: Matthew S Peairs

01.30.16
  Lecture 17: Probabilistic TMs and Complexity Classes

Last modified by: Matthew S Peairs

Other readings

01.30.16
  Turing's paper

Last modified by: Matthew S Peairs

Tangentially relevant humor

01.30.16
  Godel's Incompleteness Theorem (Abstruse Goose)

Last modified by: Matthew S Peairs

01.30.16
  Principle of Explosion (xkcd)

Last modified by: Matthew S Peairs

02.03.16
  Scooping the Loop Scooper (Lucas Dixon)

Last modified by: Scott Aaronson

01.30.16
  NP-Complete Problems (xkcd)

Last modified by: Matthew S Peairs

Video materials

01.30.16
  6.045 Lecture videos

Flash Player strongly recommended 

Last modified by: Scott Aaronson

Study materials

03.15.16
  Midterm topics

Last modified by: Scott Aaronson

03.15.16
  Additional practice problems

Last modified by: Leonid Grinberg

03.15.16
  More practice problems

Last modified by: Leonid Grinberg

03.15.16
  More midterm review problems — Solutions

Last modified by: Leonid Grinberg

03.15.16
  2011 midterm

Last modified by: Leonid Grinberg

03.15.16
  2011 midterm solutions

Last modified by: Leonid Grinberg

03.31.16
  Midterm solutions

Last modified by: Nirav Bhan

05.06.16
  Final 2010

Last modified by: Leonid Grinberg

05.06.16
  Final 2010 Solutions

Last modified by: Leonid Grinberg

05.06.16
  Final 2011

Last modified by: Leonid Grinberg

05.06.16
  Final 2011 Solutions

Last modified by: Leonid Grinberg

05.06.16
  Additional practice final

Last modified by: Leonid Grinberg

05.06.16
  Final topics

Last modified by: Leonid Grinberg

05.22.16
  Final solutions restricted use

Last modified by: Nirav Bhan