CSC236H1 — Introduction to the Theory of Computation, Summer 2026
Last updated:
Course Staff and Contact
Instructor: Amir Reza Peimani
Teaching Assistants: Ziyang Jin; Somnath Bhattacharjee; Ziqi Yu; Logan Murphy; Devansh Shringi
Course email: csc236-2026-05@cs.toronto.edu
Piazza: https://piazza.com/utoronto.ca/summer2026/csc236h1y20265lec5101
Important Notice
Important schedule correction: A previous approved version of the syllabus incorrectly listed July 18–24 as Reading Week. The correct schedule is that there are no lectures or tutorials from June 15 to June 30, and there is also no lecture/tutorial on Wednesday July 1 because of Canada Day. Regular lectures and tutorials resume after that. July 18–24 is a regular course week with lecture/tutorial activities. Office hours may still be held during the June break; see the office-hours schedule below.
Also note that the term-test weighting has been updated: across TT1–TT4, the two lowest TT marks count for 10% each, the second-highest TT mark counts for 15%, and the highest TT mark counts for 20%.
- This website serves as a supplementary source of course information.
- Official course announcements will be posted on both Piazza and Quercus.
- Course schedules, resources, and other updates will be maintained on this website throughout the term.
- Some course-material links may require UofT login through OneDrive/SharePoint.
Quick Links
Logistics
- Lecture: Wednesdays 6:10–8:00 PM, MP 103
- Tutorials: Wednesdays 8:00–9:00 PM
- TUT5101: BA 2159
- TUT5102: BA 2175
- TUT5103: BA 2139
- TUT5104: BA 2195
- Term tests are held during tutorial time.
Marking Scheme
| Component | Weight |
|---|---|
| Practice problems | 0% |
| Term tests | 55% |
| Final exam | 45% |
TT weighting: TT1–TT4 are worth 55% total. The two lowest TT marks count for 10% each, the second-highest TT mark counts for 15%, and the highest TT mark counts for 20%.
Final exam policy: Students must earn at least 25% on the final exam to pass the course. If the final exam mark is below 25%, the final course mark will be reduced, if necessary, to no more than 45.
Week-by-week Overview
Each week’s lecture slides, readings, and exercises are collected in the linked weekly materials folder. These links may require UofT login.
| Week | Dates | Materials / Activities | Assessments |
|---|---|---|---|
| Week 1 | May 4–May 10 |
Weekly Materials: Week 01 Materials Topic: Introduction to recursive correctness. Review of recursive structure, tracing, and how to reason about recursive algorithms. First lecture: Wed May 6. Lecture: w01_CSC236_Amir-01.pdf Readings: recursive-correctness-I.pdf Exercises: ex00-questions.pdf / ex00-solutions.pdf; ex01-questions.pdf / ex01-solutions.pdf; ex02-questions.pdf / ex02-solutions.pdf |
none |
| Week 2 | May 11–May 17 |
Weekly Materials: Week 02 Materials Topic: Recursive correctness continued. Valid recursive structure, non-recursive calls, return values, and proof structure for recursive algorithms. Lecture: TBA Readings: recursive-correctness-II.pdf; recursive-correctness-III.pdf Exercises: ex03-questions.pdf / ex03-solutions.pdf; ex04-questions.pdf / ex04-solutions.pdf |
none |
| Week 3 | May 18–May 24 |
Weekly Materials: Week 03 Materials Topic: Complete induction. Lecture: TBA Readings: complete-induction-I.pdf Exercises: ex05-questions.pdf / ex05-solutions.pdf |
TT1 — Wed May 20, 8:00–9:00 PM; TT1 Solution |
| Week 4 | May 25–May 31 |
Weekly Materials: Week 04 Materials Topic: Complete induction continued and introduction to structural induction. Lecture: TBA Readings: complete-induction-II.pdf; structural-I.pdf; structural-II.pdf; structural-III.pdf Exercises: ex06-questions.pdf / ex06-solutions.pdf |
none |
| Week 5 | Jun 1–Jun 7 |
Weekly Materials: Week 05 Materials Topic: Structural induction continued. Well-Ordering Principle. Lecture: TBA Readings: WOP-I.pdf; WOP-II.pdf Exercises: ex07-questions.pdf / ex07-solutions.pdf |
none |
| Week 6 | Jun 8–Jun 14 |
Weekly Materials: Week 06 Materials Topic: Iterative correctness: loop invariants and proof structure. Lecture: TBA Readings: iterative-correctness-I.pdf; iterative-correctness-II.pdf; iterative-correctness-III.pdf Exercises: ex08-questions.pdf / ex08-solutions.pdf |
TT2 — Wed Jun 10, 8:00–9:00 PM TT2 Solution |
| Reading Week | Jun 15–Jun 21 |
Weekly Materials: None No lectures or tutorials. Office hours, if any, will be announced separately. |
|
| Reading Week | Jun 22–Jun 28 |
Weekly Materials: None No lectures or tutorials. Office hours, if any, will be announced separately. |
|
| Canada Day Week | Jun 29–Jul 5 |
Weekly Materials: None No class/tutorial on Wed Jul 1 due to Canada Day. Review and independent practice. |
|
| Week 10 | Jul 6–Jul 12 |
Weekly Materials: Week 10 Materials Topic: Iterative correctness continued. More practice with loop invariants and correctness proofs. Lecture: TBA Readings: iterative-correctness-III.pdf continued Exercises: N/A |
none |
| Week 11 | Jul 13–Jul 17 |
Weekly Materials: Week 11 Materials Topic: Iterative correctness continued and consolidation of proof techniques. Lecture: TBA Readings: iterative-correctness-IV.pdf Exercises: N/A |
|
| Week 12 | Jul 18–Jul 24 |
Weekly Materials: Week 12 Materials Topic: Recursive runtime analysis. Recurrences and runtime reasoning. Lecture: TBA Readings: recursive-runtime-I.pdf Exercises: ex09-questions.pdf / ex09-solutions.pdf |
none |
| Week 13 | Jul 25–Aug 2 |
Weekly Materials: Week 13 Materials Topic: Recursive runtime continued. Introduction to regular expressions and deterministic finite automata. Lecture: TBA Readings: recursive-runtime-II.pdf; regular-intro.pdf Exercises: ex09.5-questions.pdf / ex09.5-solutions.pdf; ex10-questions.pdf / ex10-solutions.pdf |
rescheduled TT3 — Wed Jul 29, 8:00–9:00 PM TT3 Solution |
| Week 14 | Aug 3–Aug 9 |
Weekly Materials: Week 14 Materials Topic: DFA distinguishability and formal-language reasoning. Lecture: TBA Readings: dfa-distinguishability.pdf Exercises: ex11-questions.pdf / ex11-solutions.pdf |
TT4 — Wed Aug 5, 8:00–9:00 PM TT4 Solution |
| Week 15 | Aug 10–Aug 12 |
Weekly Materials: Week 15 Materials Topic: NFAs and additional selected practice/review problems. Last day of classes: Wed Aug 12. Lecture: TBA Readings: nfas.pdf Exercises: additional practice / selected review problems |
none | Week 16 FE | Aug 13–Aug 22 |
Final Exam Materials: Exam Questions 2024 (no solution) + FE Ref Sheet + FE Cover Page |
Final Exam |
Term Test Coverage
| Test | Date / Time | Location | Coverage |
|---|---|---|---|
| TT1 | Wed May 20, 8:00–9:00 PM | EX100 | Recursive correctness. Validity of recursive structure, validity of non-recursive calls, correct return values, and proof structure for recursive algorithms. Covers the main material from Weeks 1–2. TT1 Solution |
| TT2 | Wed Jun 10, 8:00–9:00 PM | EX100 | Complete induction and structural induction. Covers the main material from Weeks 3–4. TT2 Solution |
| rescheduled TT3 | Wed |
EX200 | Well-Ordering Principle and iterative correctness. Covers WOP, loop invariants, and correctness proofs for iterative algorithms. TT3 Solution |
| TT4 | Wed Aug 5, 8:00–9:00 PM | EX100 | Recursive runtime and introduction to regular languages. Covers recursive runtime analysis, recurrences, regular expressions, deterministic finite automata, and related introductory formal-language material. TT4 Solution |
| Final Exam | Check ACORN | Check ACORN | Comprehensive: you are expected to be familiar with all the material covered in the course. Past Exams Repository (requires login with your UTORid) |
Office Hours
Zoom: Link [Passcode: 23620265]
Amir's Office Hours: Amir will be holding weekly office hours on Wednesdays 12–1pm starting on Wednesday May 20, 2026.
| Week | Dates | Office Hours |
|---|---|---|
| Week 1 | May 4–May 10 | No office hours scheduled |
| Week 2 | May 11–May 17 | Mon May 11, 10–11 AM on Zoom; Mon May 11, 1–2 PM in BA2270 |
| Week 3 — TT1 | May 18–May 24 | Mon May 18, 10–11 AM on Zoom; Tue May 19, 10–11 AM in BA2270; Tue May 19, 1–2 PM in BA2270 |
| Week 4 | May 25–May 31 | Mon May 25, 10–11 AM on Zoom |
| Week 5 | Jun 1–Jun 7 | Mon Jun 1, 10–11 AM on Zoom; Tue Jun 2, 10–11 AM in BA2270 |
| Week 6 — TT2 | Jun 8–Jun 14 | Tue Jun 9, 2-3 PM on Zoom; Mon Jun 8, 1–2 PM in BA2270; Tue Jun 9, 10–11 AM in BA2270; Tue Jun 9, 11 AM–12 PM in BA2270 |
| Reading Week | Jun 15–Jun 21 | No office hours scheduled unless announced |
| Reading Week | Jun 22–Jun 28 | No office hours scheduled unless announced |
| Canada Day Week | Jun 29–Jul 5 | Mon Jun 29, 10–11 AM on Zoom |
| Week 10 | Jul 6–Jul 12 | Mon Jul 6, 10–11 AM in BA2270; Tue Jul 7, 1–2 PM in BA2270 |
| Week 11 — |
Jul 13–Jul 17 | Mon Jul 13, 10–11 AM in BA2270; Tue Jul 14, 10–11 AM in BA2270; Tue Jul 14, 1–2 PM in BA2270 |
| Week 12 | Jul 18–Jul 24 | Mon Jul 20, 10–11 AM in BA2270 |
| Week 13 - rescheduled TT3 | Jul 25–Aug 2 | Mon Jul 27, 10–11 AM in BA2270; Fri Jul 31, 10–11 AM in BA2270; Mon Jul 27, 1–2 PM on Zoom |
| Week 14 — TT4 | Aug 3–Aug 9 | Mon Aug 3, 10–11 AM in BA2270; Mon Aug 3, 1–2 PM in BA2270; Tue Aug 4, 9–10 AM in BA2270; Tue Aug 4, 10–11 AM in BA2270; Tue Aug 4, 4–5 PM in BA2270; Wed Aug 5, 9–10 AM on Zoom; Wed Aug 5, 10–11 AM in BA2270; Wed Aug 5, 11 AM–12 PM in BA2270 |
| Week 15 | Aug 10–Aug 16 | Mon Aug 10, 10–11 AM in BA2270 |
| Week 16 — Final Exam Period | Aug 17–Aug 22 |
Mon Aug 17, 10–11 AM at BA 2270 (Weekly OH) Mon Aug 17, 4 PM on Zoom Tue Aug 18, 10 AM on Zoom Tue Aug 18, 3 PM at BA 2270 Tue Aug 18, 4 PM on Zoom Wed Aug 19, 12–1 PM (Amir's OH) Thur Aug 20, 10-11 AM on Zoom |
Contact
- For general course questions, use Piazza.
- For personal questions, email csc236-2026-05@cs.toronto.edu.
- Do not use Quercus messages at all.