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 Friday, 2–6 p.m., the CSC Help Centre awaits your questions.
Below you'll find a calendar with entries for all significant course events
| Week: | Thursday | Friday | Monday | Tuesday | Wednesday |
| Week #1 introduction, simple induction input: output: assignment #1 due Sep 28 | Sep 6 Lecture 6:10–8:00 SF1101 no tutorial first week | Sep 7 no tutorial first week | Sep 10 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Sep 11 | Sep 12 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #2 complete induction input: output: | Sep 13 Lecture 6:10–8:00 SF1101 Tutorial 8:10–9:00 p.m., handout | Sep 14 Tutorial 11:10–noon, handout Tutorial 12:10–1 p.m., handout | Sep 17 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 annotated slides | Sep 18 | Sep 19 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 annotated slides |
| 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 20 Lecture 6:10–8:00 SF1101 | Sep 21 | Sep 24 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Sep 25 | Sep 26 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #4 recurrences input: output: | Sep 27 Lecture 6:10–8:00 SF1101 | Sep 28 | Oct 1 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Oct 2 | Oct 3 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #5 complexity binary search input: output: | Oct 4 term test #1 6:10--7p.m. surnames A-Downie: BA2195 surnames Du-Li: BA1240 surnames Lin-Z: SF1101 Lecture 7:20--8:20 p.m. | Oct 5 term test #1 during tutorial time 11:10--noon BA3116 -> BA3116 BA1230 -> BA1230 BA1240 -> BA1240 BA2185 -> LM161 [changed!] noon--1:00 AP120 -> BA1180 BA2135 -> BA1180 AB114 -> LM161 [changed!] BA2139 -> BA2139 | Oct 8 Thanksgiving, university closed | Oct 9 | Oct 10 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #6 mergesort, divide and conquer, master theorem input: output: | Oct 11 Lecture 6:10–8:00 SF1101 | Oct 12 | Oct 15 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Oct 16 | Oct 17 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #7 use master theorem / recursive correctness input: output: | Oct 18 Lecture 6:10–8:00 SF1101 | Oct 19 | Oct 22 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Oct 23 | Oct 24 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #8 iterative correctness input: output: | Oct 25 Lecture 6:10–8:00 SF1101 | Oct 26 | Oct 29 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Oct 30 | Oct 31 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #9 introduce Finite State Automata (FSAs) input: output: | Nov 1 Lecture 6:10–8:00 SF1101 | Nov 2 | Nov 5 reading week :) | Nov 6 reading week :) | Nov 7 reading week :) |
| Week #9 introduce Finite State Automata (FSAs) input: output: | Nov 8 reading week :) | Nov 9 reading week :) | Nov 12 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Nov 13 | Nov 14 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #10 FSAs and regular languages input: output: | Nov 15 term test #2, 6:10 to 7:00, EX200 | Nov 16 term test #2, during tutorial time 11:10--noon BA3116 -> BA3116 BA1230 -> BA1230 BA1240 -> BA1240 BA2185 -> LM161 noon--1:00 AP120 -> BA1180 BA2135 -> BA1180 AB114 -> LM161 BA2139 -> BA2139 | Nov 19 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 | Nov 20 | Nov 21 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 |
| Week #11 properties, equivalence: FSAs/regexes input: output: | Nov 22 Lecture 6:10–8:00 SF1101 | Nov 23 | Nov 26 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 annotated slidesCSSU outreach survey | Nov 27 | Nov 28 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 annotated slidesCSSU outreach survey |
| Week #12 regular languages, non-regular languages input: output: | Nov 29 Lecture 6:10–8:00 SF1101 CSSU outreach survey | Nov 30 | Dec 3 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 CSSU outreach survey | Dec 4 | Dec 5 Lecture 11:10–noon LM161 Lecture 12:10–1:00 LM161 CSSU outreach survey |