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

Materials

Click on topic headings to hide their contents. 

Collapse All Topics 

General

04.16.15
  Solutions to the Midterm

Last modified by: Saeed Mehraban

02.12.15
  Lecture 1: Intro

Last modified by: Kevin L Wu

02.12.15
  Lecture 2: Logic

Last modified by: Kevin L Wu

02.12.15
  Lecture 3: Circuits and Finite Automata

Last modified by: Kevin L Wu

03.03.15
  Lecture 4: Turing Machines

Last modified by: Kevin L Wu

03.03.15
  Lecture 5: Reducibility and Gödel

Last modified by: Kevin L Wu

03.05.15
  Lecture 6: Minds and Machines

Last modified by: Kevin L Wu

03.27.15
  Lecture 7: Complexity

Last modified by: Kevin L Wu

03.31.15
  Lecture 8: Polynomial Time

Last modified by: Kevin L Wu

03.31.15
  Lecture 9: P and NP

Last modified by: Kevin L Wu

04.09.15
  Lecture 10: NP-completeness

Last modified by: Kevin L Wu

04.09.15
  Lecture 11: NP-Completeness in Practice

Last modified by: Kevin L Wu

04.16.15
  Lecture 12: Space Complexity and More

Last modified by: Kevin L Wu

04.16.15
  Lecture 13: Randomness

Last modified by: Kevin L Wu

04.16.15
  Lecture 14: Probabilistic Complexity Classes

Last modified by: Kevin L Wu

04.30.15
  Lecture 15: Derandomization / Crypto Double Feature

Last modified by: Kevin L Wu

04.30.15
  Lecture 16: Private-Key Cryptography

Last modified by: Kevin L Wu

04.30.15
  Lecture 17: Public-Key Cryptography

Last modified by: Kevin L Wu

02.02.15
  Lecture 18: Cryptographic Protocols

Last modified by: Scott Aaronson

02.02.15
  Lecture 19: Interactive Proofs / Machine Learning

Last modified by: Scott Aaronson

02.02.15
  Lecture 20: PAC-Learning

Last modified by: Scott Aaronson

02.02.15
  Lecture 21: Learning, Chomsky, RSA, Quantum

Last modified by: Scott Aaronson

02.02.15
  Lecture 22/23: Quantum Computing

Last modified by: Scott Aaronson

02.02.15
  Lecture 24: Quantum Algorithms

Last modified by: Scott Aaronson

02.02.15
  Dating Problem + Zero Knowledge Slides

Slides from the lecture 

Last modified by: Rotem Oshman

02.08.15
  Syllabus

Last modified by: Saeed Mehraban

Lecture notes

02.02.15
  Lecture 3: DFAs and NFAs

Last modified by: Matthew S Peairs

02.02.15
  Lecture 4: NFAs and Regular Expressions

Last modified by: Matthew S Peairs

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

Last modified by: Matthew S Peairs

02.02.15
  Lecture 7: Decidability

Last modified by: Matthew S Peairs

02.02.15
  Lecture 8: Undecidable Problems and PCP

Last modified by: Matthew S Peairs

02.02.15
  Lecture 9: Mapping Reducibility and Rice's Theorem

Last modified by: Matthew S Peairs

02.02.15
  Lecture 10: Self-Reference and the Recursion Theorem

Last modified by: Matthew S Peairs

02.02.15
  Lecture 12: Complexity Theory

Last modified by: Matthew S Peairs

02.02.15
  Lecture 15: More Complexity Theory

Last modified by: Matthew S Peairs

02.02.15
  Lecture 16: More NP-completeness

Last modified by: Matthew S Peairs

02.02.15
  Lecture 17: Probabilistic TMs and Complexity Classes

Last modified by: Matthew S Peairs

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

Last modified by: Leonid Grinberg

02.02.15
  RSA Notes

Last modified by: Leonid Grinberg

Lecture Slides as PDFs

02.12.15
  Lecture 3: DFAs and NFAs

Last modified by: Kevin L Wu

02.12.15
  Lecture 4: NFAs and Regular Expressions

Last modified by: Kevin L Wu

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

Last modified by: Matthew S Peairs

02.02.15
  Lecture 7: Decidability

Last modified by: Matthew S Peairs

02.02.15
  Lecture 8: Undecidable Problems and PCP

Last modified by: Matthew S Peairs

02.02.15
  Lecture 9: Mapping Reducibility and Rice's Theorem

Last modified by: Matthew S Peairs

02.02.15
  Lecture 10: Self-Reference and the Recursion Theorem

Last modified by: Matthew S Peairs

02.02.15
  Lecture 12: Complexity Theory

Last modified by: Matthew S Peairs

02.02.15
  Lecture 15: More Complexity Theory

Last modified by: Matthew S Peairs

02.02.15
  Lecture 16: More NP-completeness

Last modified by: Matthew S Peairs

02.02.15
  Lecture 17: Probabilistic TMs and Complexity Classes

Last modified by: Matthew S Peairs

Other readings

02.02.15
  Turing's paper

Last modified by: Matthew S Peairs

Tangentially relevant humor

02.02.15
  Godel's Incompleteness Theorem (Abstruse Goose)

Last modified by: Matthew S Peairs

02.02.15
  Principle of Explosion (xkcd)

Last modified by: Matthew S Peairs

02.02.15
  Scooping the Loop Scooper (Lucas Dixon)

Last modified by: Matthew S Peairs

02.02.15
  NP-Complete Problems (xkcd)

Last modified by: Matthew S Peairs

Video materials

02.11.15
  6.045 Lecture videos

Flash Player strongly recommended 

Last modified by: Scott Aaronson

Homework

02.07.15
  Pset 1

Due: February 20 2015 5:00 p.m.

02.25.15
  Pset2

Due: March 06 2015 5:00 p.m.

03.09.15
  Pset3

Due: March 20 2015 4:03 p.m.

04.04.15
  Pset4

Due: April 16 2015 5:00 p.m.

04.11.15
  Pset5

Due: April 24 2015 5:00 p.m.

04.26.15
  Pset6

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

Study materials

03.22.15
  Midterm topics

Last modified by: Scott Aaronson

03.22.15
  Additional practice problems

Last modified by: Leonid Grinberg

03.22.15
  More practice problems

Last modified by: Leonid Grinberg

03.22.15
  More midterm review problems — Solutions

Last modified by: Leonid Grinberg

03.22.15
  2011 midterm

Last modified by: Leonid Grinberg

03.22.15
  2011 midterm solutions

Last modified by: Leonid Grinberg

05.09.15
  Final 2010

Last modified by: Leonid Grinberg

05.09.15
  Final 2010 Solutions

Last modified by: Leonid Grinberg

05.09.15
  Final 2011

Last modified by: Leonid Grinberg

05.09.15
  Final 2011 Solutions

Last modified by: Leonid Grinberg

05.09.15
  Additional practice final

Last modified by: Leonid Grinberg

05.09.15
  Final topics

Last modified by: Leonid Grinberg