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

Course Reader

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

Week Monday Wednesday Friday

Jan 6th

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

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

Course Information
Syllabus PDF

Jan 8th

01: How can we prove results with certainty?

Read: Notes Ch. 2

How to Succeed
Mathematical Prerequisites
Guide to Set Theory Proofs


Jan 13th

03: How can we formalize our reasoning?

Read: related handout

First-Order Translation Checklist
Truth Table Tool

Jan 15th

04: How can we reason about collections of objects?

Read: related handout

First-Order Translation Checklist

Jan 17th

05: How do we rigorously define key terms?

Read: (see handouts from Mon and Wed)


  • Out: Pset2

  • 3

    Jan 20th

    MLK Jr. Holiday

    No class Monday

    Watch MLK's "Two Americas" (1967, Stanford campus)

    Jan 22nd

    06: How do we model relationships between objects?

    Read: Notes Ch. 5


    Jan 24th

    07: What does it mean to compare two objects?

    Read: Handouts, Notes Ch. 6

    Guide to Proofs on Discrete Structures
    Discrete Structures Proofwriting Checklist

  • Out: Pset3

  • 4

    Jan 27th

    08: How do we model transformations and associations?

    Read: Notes Ch. 6


    Jan 29th

    09: How do we reason about infinity?

    Read: Handout, Notes Ch. 6

    Guide to Cantor's Theorem

    Jan 31st

    10: How do we model network structures?

    Read: Notes Ch. 4

    Slides Parts 1, 2.

  • Out: Pset4

  • 5

    Feb 3rd

    11: Graphs II

    Read: Notes Ch. 4


    Feb 5th

    12: Induction

    Read: Notes Ch. 3


    Feb 7th

    13: Induction Pt. 2

    Read: Notes Ch. 3, Handout

    Guide to Induction
    Induction Proofwriting Checklist
    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 10th

    14: Automata I: DFAs

    Read: Sipser 1.2


    Feb 12th

    15: Automata II: NFAs

    Read: Sipser 1.2

    Slides Parts 1, 2, 3.

    Feb 14th

    16: Automata III: Equivalence, Closure

    Read: Sipser 1.2

    Slides Parts 1, 2, 3. Review Session Slides.

  • Out: Pset6
  • 7

    Feb 17th

    President's Day Holiday

    No class Monday
    MIDTERM TUES FEB 18th 7-10PM

    Feb 19th

    17: Regular Expressions

    Read: Sipser 1.3


    Feb 21st

    18: Non-Regular Languages

    Read: Sipser 2.1


  • Out: Pset7
  • 8

    Feb 24th

    19: CFGs

    Read: Sipser 2.1

    Feb 26th

    20: Turing Machines

    Read: Sipser 3.1

    Feb 28th

    21: Turing Machines II

    Read: Sipser 3.1

  • Out: Pset8
  • 9

    Mar 2nd

    22: Turing Machines III

    Read: Sipser 4.1-4.2, 6.1

    Mar 4th

    23: Unsolvable Problems

    Read: Sipser 4.1-4.2, 6.1

    Mar 6th

    24: Unsolvable Problems II

    Read: n/a

  • Out: Pset9
  • 10

    Mar 9th

    25: Complexity Theory I

    Read: Sipser 7.2, 7.3

    Mar 11th

    26: Complexity Theory II

    Read: Sipser 7.4

    Mar 13th

    No class

    Read: Study for the final