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

Apr 6th

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

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

Apr 8th

01: How can we prove results with certainty?

Read: Notes Ch. 2

Apr 10th

02: How do we prove something without directly proving it?

Read: Notes Ch. 2

  • Out: Pset1

  • 2

    Apr 13th

    03: How can we formalize our reasoning?

    Read: related handout

    Apr 15th

    04: How can we reason about collections of objects?

    Read: related handout

    Apr 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

    Slides Parts 1, 2, 3, 4, 5, 6.

    Feb 28th

    21: Turing Machines II

    Read: Sipser 3.1

    Alan Turing's original 1936 paper

  • Out: Pset8
  • 9

    Mar 2nd

    22: Turing Machines III

    Read: Sipser 4.1-4.2, 6.1

    Guide to the Lava Diagram

    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