CSC 236: Introduction to the Theory of Computation (Summer 2023)

This course has now been archived, you can find the lecture notes for this semester here: [lectures]

(Thanks to Obsidian, Cosma, and this script.)

Course Info

Instructor Harry Sha
TAs Matthew Hagan, Lawrence Li, Lily Li, and Logan Murphy
Guides [guide-to-hw], [guide-to-check-ins]
Syllabus [syllabus]
Learning Outcomes [learning-outcomes]
Additional Reading [notes-vassos-hadzilacos], [notes-david-liu]
Prerequisite CSC165 (or equivalent). [notes-david-liu-toniann-pitassi]

Schedule

Week Date Topic Links Reading
1 May 10 Welcome and Functions VH {0.1-0.3, 0.6}
2 May 17 Graphs LP 6
3 May 24 Induction 1 DL 2, VH {1, 4}
4 May 31 Induction 2
5 June 7 Recursive Algorithms 1 DL 3, VH {2.7-2.8, 3}
6 June 14 Recursive Algorithms 2
7 June 21 NO CLASS
8 June 28 Midterm
9 July 5 Algorithm Correctness 1 DL 4, VH 2.1-2.6
10 July 12 Algorithm Correctness 2
11 July 19 Formal Languages 1 DL 5, VH 7
12 July 26 Formal Languages 2
13 August 2 Formal Languages 3
14 August 9 Review