**Tentative** schedule: (this schedule is a very rough outline, and can and will change)

All lecture notes can be found at introtcs.org. See also preface to the notes.

Note that you will need to read the lecture notes for each lecture **before** it is given.

The midterm exam is as listed below (during lecture time) and the final exam will be on Thursday, December 14th at 2:00 pm.

Lecture # | Date | Lectures | Slides | Pset out |
---|---|---|---|---|

0 (before course) | Math background | |||

1 | Thursday, 8/31/17 | Introduction | lec 1 slides | HW0 |

2 | Tuesday, 9/5/17 | Refreshing some math | lec 2 slides | |

3 | Thursday, 9/7/17 | Representing objects as strings | lec 3 slides | HW1 |

4 | Tuesday, 9/12/17 | Defining computation | lec 4 slides python notebook | |

5 | Thursday, 9/14/17 | Syntactic sugar and computing every function | notebook | HW2 |

6 | Tuesday, 9/19/17 | Code as data | notebook lec 6 slides | |

7 | Thursday, 9/21/17 | Physical implementation | lec 7 slides notebook | HW3 |

8 | Tuesday, 9/26/17 | Loops and infinity | lecture 8 slides notebook | |

9 | Thursday, 9/28/17 | Universality and indirection | slides notebook | HW4 |

Fifth Monday |
Monday, 10/2/17 | |||

10 | Tuesday, 10/3/17 | Equivalence to other models | slides lambda notebook | |

11 | Thursday, 10/5/17 | Uncomputability | slides halting proof powerpoint | no pset (midterm) |

12 | Tuesday, 10/10/17 | Godel’s Incompleteness Theorem | slides | |

13 | Thursday, 10/12/17 | Midterm | HW5 | |

Seventh Monday |
Monday, 10/16/17 | |||

14 | Tuesday, 10/17/17 | Restricted computational models | ||

15 | Thursday, 10/19/17 | Efficient computation | HW6 | |

16 | Tuesday, 10/24/17 | Formally defining running time | ||

17 | Thursday, 10/26/17 | NP | HW7 | |

18 | Tuesday, 10/31/17 | Cook Levin Thm | ||

19 | Thursday, 11/2/17 | More on NP reductions | HW8 | |

20 | Tuesday, 11/7/17 | discussion of P vs NP | ||

21 | Thursday, 11/9/17 | Review of probability | HW9 | |

22 | Tuesday, 11/14/17 | Randomized algorithms | ||

23 | Thursday, 11/16/17 | Modeling randomized computation | HW10 | |

24 | Tuesday, 11/21/17 | Derandomization | ||

– | Thursday, 11/23/17 | Thanksgiving (no lecture) | ||

25 | Tuesday, 11/28/17 | Crypto | Some make up? | |

26 | Thursday, 11/30/17 | Quantum computing |