The "Notes" readings refer to our course reader, available here:

Course Reader

This schedule updates each week. For an overview of the whole quarter, refer to the Syllabus Handout:

Syllabus


The schedule is subject to change by the management at any time.

Week Monday Wednesday Friday
1

Jan 7th

00: Can computers solve all problems? Set theory and the limits of computing

Read: Syllabus, Course Information Sheet, Notes Ch. 1

Slides
Course Information
Syllabus PDF
Guide to Sets, Elements, and Subsets

  • Out: Pset0

  • Jan 9th

    01: How can we prove results with certainty?

    Read: Notes Ch. 2

    Slides
    How to Succeed
    Mathematical Prerequisites
    Guide to Set Theory Proofs

    2

    Jan 14th

    03: How can we formalize our reasoning?

    Read: related handout

    Slides
    Guide to Logic Translations
    Truth Table Tool

    Jan 16th

    04: How can we reason about collections of objects?

    Read: related handout

    Slides
    First-Order Translation Checklist

    Jan 18th

    05: How do we rigorously define key terms?

    Read: (see handouts from Mon and Wed)

    Slides

  • Out: Pset2

  • 3

    Jan 21st

    Martin Luther King Jr Holiday - no class

    Read: Consider watching his 1967 Two Americas speech, given here on Stanford campus

    Jan 23rd

    06: How do we model relationships between objects?

    Read: Notes Ch. 5

    Slides

    Jan 25th

    07: What does it mean to compare two objects?

    Read: Handouts, Notes Ch. 6

    Slides
    Guide to Proofs on Discrete Structures
    Discrete Structures Proofwriting Checklist

  • Out: Pset3

  • 4

    Jan 28th

    08: How do we model transformations and associations?

    Read: Notes Ch. 6

    Slides

    Jan 30th

    09: How do we reason about infinity?

    Read: Handout, Notes Ch. 6

    Slides
    Guide to Cantor's Theorem

    Feb 1st

    10: How do we model network structures?

    Read: Notes Ch. 4

    Slides 1
    Slides 2

  • Out: Pset4

  • 5

    Feb 4th

    11: Graphs II

    Read: Notes Ch. 4

    Midterm tonight!
    Slides

    Feb 6th

    12: Induction

    Read: Notes Ch. 3

    Slides

    Feb 8th

    13: Induction Pt. 2

    Read: Notes Ch. 3, Handout

    Slides
    Guide to Induction Movie clip: Good Will Hunting problem (trees)
    Numberphile on the Good Will Hunting problem (gives a detailed problem statement; you should pause before they go through the solution to try it yourself!)

  • Out: Pset5

  • 6

    Feb 11th

    14: Automata I: DFAs

    Read: Sipser 1.1

    Slides

    Feb 13th

    15: Automata II: NFAs

    Read: Sipser 1.2

    Slides 1
    Slides 2
    Slides 3

    Feb 15th

    16: Automata III: Equivalence, Closure

    Read: Sipser 1.2

    Slides 1
    Slides 2
    Slides 3

  • Out: Pset6

  • 7

    Feb 18th

    No lecture: President's Day holiday

    Feb 20th

    17: Regular Expressions

    Read: Sipser 1.3

    Slides

    Feb 22nd

    18: Non-Regular Languages

    Read: Sipser 2.1

    Slides

  • Out: Pset7

  • 8

    Feb 25th

    19: CFGs

    Read: Sipser 2.1

    Midterm tonight!
    Slides

    Feb 27th

    20: Turing Machines

    Read: Sipser 3.1

    Slides

    Mar 1st

    21: Turing Machines II

    Read: Sipser 3.1

    Slides

  • Out: Pset8

  • 9

    Mar 4th

    22: Turing Machines III

    Read: Sipser 4.1-4.2, 6.1

    Slides

    Mar 6th

    23: Unsolvable Problems

    Read: Sipser 4.1-4.2, 6.1

    Slides

    Mar 1st

    24: Unsolvable Problems II

    Read: Handouts

    Slides
    Lava Guide
    Self-reference Guide

  • Out: Pset9

  • 10

    Mar 11th

    25: Complexity Theory I

    Read: Sipser 7.2, 7.3

    Slides

    Mar 13th

    26: Complexity Theory II

    Read: Sipser 7.4

    Slides

    Mar 15th

    27: Quarter Wrap-Up

    Read:

    Slides