CS103

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

Week	Monday	Wednesday	Friday
1	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 Slides	Jan 24th 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 27th 08: How do we model transformations and associations? Read: Notes Ch. 6 Slides	Jan 29th 09: How do we reason about infinity? Read: Handout, Notes Ch. 6 Slides 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 Slides	Feb 5th 12: Induction Read: Notes Ch. 3 Slides	Feb 7th 13: Induction Pt. 2 Read: Notes Ch. 3, Handout Slides 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 Slides	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 Slides	Feb 21st 18: Non-Regular Languages Read: Sipser 2.1 Slides Out: Pset7
8	Feb 24th 19: CFGs Read: Sipser 2.1 Slides	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 Slides Alan Turing's original 1936 paper Out: Pset8
9	Mar 2nd 22: Turing Machines III Read: Sipser 4.1-4.2, 6.1 Slides Guide to the Lava Diagram	Mar 4th 23: Unsolvable Problems Read: Sipser 4.1-4.2, 6.1 Slides	Mar 6th 24: Unsolvable Problems II Read: n/a Slides Out: Pset9
10	Mar 9th 25: Complexity Theory I Read: Sipser 7.2, 7.3 Slides	Mar 11th 26: Complexity Theory II Read: Sipser 7.4 Slides	Mar 13th No class Read: Study for the final
	Mar 17th FINAL TUES MAR 17th 8:30-11:30AM

Lecture Schedule