Welcome to CSC236, Introduction to the Theory of Computation. In this course you will augment your intuition as a programmer with analytical skills and proof. You are responsible for making sure you have the necessary prerequisites for this course.
Extra help: Many students find this course challenging, so you are encouraged to make use of lectures, tutorials, office hours, and the DCS Help Centre to help you master course material. Every Monday through Thursday, 4–6 p.m., the CSC Help Centre awaits your questions.
Below you'll find a calendar with entries for all significant course events
| Week: | Monday | Tuesday | Wednesday | Thursday | Friday |
| Week #1 introduction, simple induction input: output: assignment #1 due Oct 7 | Sep 12 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Sep 13 | Sep 14 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Sep 15 Lecture 6:10–8:00 BA1180 no tutorial first week | Sep 16 no tutorial first week |
| Week #2 complete induction input: output: | Sep 19 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Sep 20 | Sep 21 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Sep 22 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout Week 2 sample solutions | Sep 23 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout Week 2 sample solutions |
| Week #3 well-ordering, structural induction input: course notes sections 4.1, 4.2 Rosen's Discrete Mathematics... lots of induction examples in Chapter 5. output: | Sep 26 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Sep 27 | Sep 28 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Sep 29 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout Week 3 sample solutions | Sep 30 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout Week 3 sample solutions |
| Week #4 recurrences input: output: | Oct 3 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Oct 4 | Oct 5 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Oct 6 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout | Oct 7 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout Assignment #1 due 10 p.m. LaTeX source for Assignment #1 You are welcome to use any editor or word-processor you like, of course. |
| Week #5 complexity binary search input: output: | Oct 10 Thanksgiving: university closed | Oct 11 | Oct 12 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Oct 13 6:10–7 p.m. surnames A--J: BA2165 surnames K--S: BA2175 surnames T--Z: BA2185 Lecture, 7:15–8 p.m. | Oct 14 11:10–noon, regular tutorial rooms 12:10–1 p.m. A--L, BA1180 M--Z, BF323 1:10–2 p.m., regular tutorial rooms |
| Week #6 mergesort, divide and conquer, master theorem input: output: | Oct 17 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Oct 18 | Oct 19 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Oct 20 Tutorial 8:10–9:00 p.m., handout week 6 sample tutorial solutions Lecture 6:10–8:00 BA1180 | Oct 21 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout |
| Week #7 recursive correctness input: output: | Oct 24 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Oct 25 | Oct 26 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Oct 27 Tutorial 8:10–9:00 p.m., handout week 7 sample tutorial solutionsLecture 6:10–8:00 BA1180 | Oct 28 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout week 7 sample tutorial solutions |
| Week #8 iterative correctness input: output: | Oct 31 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Nov 1 | Nov 2 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Nov 3 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout week 8 sample tutorial solutions | Nov 4 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout week 8 sample tutorial solutions |
| Week #9 introduce Finite State Automata (FSAs) input: output: | Nov 7 Fall break: no lecture | Nov 8 | Nov 9 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Nov 10 6:10–7 p.m. surnames A--J: BA2165 surnames K--S: BA2175 surnames T--Z: BA2185 Lecture, 7:15–8 p.m. | Nov 11 11:10–noon, regular tutorial rooms 12:10–1 p.m. A--L, BA1180 M--Z, BF323 1:10–2 p.m., regular tutorial rooms |
| Week #10 FSAs and regular languages input: output: | Nov 14 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Nov 15 | Nov 16 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Nov 17 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout | Nov 18 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout |
| Week #11 properties, equivalence: FSAs/regexes input: output: | Nov 21 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Nov 22 | Nov 23 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Nov 24 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout | Nov 25 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout |
| Week #12 regular languages, non-regular languages input: output: | Nov 28 Lecture 11:10–noon RW110 Lecture 12:10–1:00 BA1130 Lecture 1:10–2:00 BA1170 | Nov 29 | Nov 30 Lecture 11:10–noon RW110 Lecture noon–1:00 BA1180 Lecture 1:10–2:00 BA1170 | Dec 1 Lecture 6:10–8:00 BA1180 Tutorial 8:10–9:00 p.m., handout | Dec 2 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout Tutorial 1:10–2 p.m., handout |