This is the website for the Winter 2020 session of CSC240, Enriched Introduction to the Theory of Computation, taught by James Cook. In this course you will learn about mathematical logic and proofs, and some applications of mathematics to computer science. Topics include:
- Predicate and propositional logic
- Proofs
- Induction
- Diagonalization arguments
- Big-Oh notation (O(.), Ω(.), Θ(.)) and recurrences
- Correctness and analysis of algorithms
- Languages and automata
Most of the material we'll use in this course is closely based on or copied from Professor Faith Ellen's course material. Thanks to Prof. Ellen for creating it.
For some information on how the course will work now that in-person classes are cancelled, see this post.
Announcements
Announcements are posted here and in the forum.
-
April 29: The final assessment is released on MarkUs, and open for remark requests until May 14 11:59pm.
I've also re-opened remark requests for Assignments 6, 8, 9 and 10 and the last two quizzes, since you only had a day or two for remark requests originally.
-
April 24: That's a wrap!
Thanks for your all of your hard work and dedication on this difficult course, and for all the great questions.
Some of you were asking what else I've been working on. Here's a video of a talk I gave earlier this month. Unfortunately it's kind of long and technical, but if you do end up watching it, look out for the places it intersects CSC240: complexity classes (we talked about two of these in CSC240: computable functions and regular languages); upper and lower bounds; and runtime of recursive algorithms. I also talk about "branching programs", which are a bit like finite state automata that can read the input in any order they choose.
Feel free to contact me after the semester is over. You can email me directly at jcook@cs.berkeley.edu; I don't know how long the csc240 email alias will last.
So long, and good luck with all your future studies!
-
Older announcements are archived here.
Online quiz
Posted March 31 evening:
The Week 11 Quiz is a take-home quiz, due this Friday (April 3) at 11:59pm. Start on it whenever you're ready.
- Do not discuss it with anyone else! Don't post on the forum about it! Read the instructions on the quiz for more information, and email me if you have questions.
- 10-15 minutes should be enough to write it, but I'm giving you three days because I didn't give you any advance warning. There is no time limit other than the April 3 deadline.
- Submit via MarkUs (
q11). Latex not required. See quiz for details. - It covers material from last week (week 11).
- Optional Latex template in case you decide to use Latex and want a starting point.
Resources
-
For help, try Office hours, the CS Help Centre, the course discussion forum (but don't discuss assignment solutions there), or email me at csc240-2020-01@cs.toronto.edu.
-
For reading material, see Textbooks, Further reading and More. The last link also includes some sample problems.
Office hours
All remaining office hours will be held online. For now, we're using Quercus; to join, find CSC240 on Quercus and choose "Bb Collaborate".
The last scheduled office hours will be Monday April 6 from 1pm to 2pm.
After that, you can email me to set up an appointment.
Contact
- Office hours: see the Office hours section, or email me to make an appointment.
- You can email me at csc240-2020-01@cs.toronto.edu and I'll try to respond within 48 hours excluding weekends.
- Consider posting to our course discussion
forum instead of emailing
me. You might get a faster response, and it helps your fellow students.
- Do not discuss assignment solutions on the discussion forum until after the deadline for late submissions has passed and the solutions are posted on the course website. See Collaboration and academic integrity.
- The CS Help Centre can also help with course material.
Important information
Textbooks
We'll use three textbooks in this course, listed below. You don't need to buy them: the first two are freely available to anyone online, and the relevant parts of the third will be made available electronically through the library when we need them.
-
Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, MIT. (Also available here.)
-
Course notes for CSC B36/236/240 by Vassos Hadzilacos. (Also available here.)
-
An Introduction to Formal Languages and Automata, 5th edition, by Peter Linz. Parts of Chapters 2, 3 and 4 will be made available online when we get to those topics. Update March 22: sorry, I put in the requset a bit too late, and so we're still waiting for it to be available. It should eventually appear on Quercus in the "Library Course Reserves" section of the course page. In the meantime, use the previous textbook on this list.
If you want more things to read, see Further reading.
Working with other students
You can learn a lot from other students, so I encourage you to talk about the course, but when it comes to homework assignments, there are some strict rules to follow: see Collaboration and academic integrity.
Lectures and tutorials
Starting on March 16:
-
Instead of lectures, I will post lecture videos and hold virtual office hours during the scheduled lecture period.
-
Instead of tutorials, I will post tutorial problems. For now, a TA (Stephanie) will be holding office hours during tutorial period 11am-12pm on Wednesdays; we may change this plan depending on how well it works.
Online lectures
We'll use online lecture videos for the second and third weeks, which you should watch before class. See Online lectures.
Dropping down
Before January 31, if there's space, students may drop down from CSC240 to CSC165 or CSC236. See here for more information.
Calendar
| Date | Attend | Due |
|---|---|---|
| Monday Jan 6 | Lecture (Week 1) | |
| Wednesday Jan 8 | Tutorial | |
| Monday Jan 13 | Problem session (Week 2) | Watch online lecture before class. |
| Wednesday Jan 15 | Tutorial | Assignment 1 due |
| Monday Jan 20 | Problem session (Week 3) | Watch online lecture before class. |
| Wednesday Jan 22 | Tutorial | Assignment 2 due |
| Monday Jan 27 | Lecture (Week 4) | |
| Wednesday Jan 29 | Tutorial | Assignment 3 due |
| Friday Jan 31 | Deadline to drop down to CSC165 or CSC236 | |
| Monday Feb 3 | Lecture (Week 5) | |
| Wednesday Feb 5 | Tutorial | Assignment 4 due |
| Monday Feb 10 | Lecture (Week 6) | |
| Wednesday Feb 12 | Tutorial | Assignment 5 due |
| Feb 17-21 | Reading week: no classes | |
| Monday Feb 24 | Lecture (Week 7) (midterm moved to Mar 2) | |
| Wednesday Feb 26 | Tutorial | |
| Monday Mar 2 | Midterm: 11:10am-1pm | |
| Wednesday Mar 4 | Lecture (Week 8): 11:10am-12pm. No quiz. | Assignment 6 due |
| Monday Mar 9 | Lecture (Week 9) | |
| Wednesday Mar 11 | Tutorial | Assignment 7 due |
| Sunday Mar 15 | Last day to drop from academic record and GPA | |
| Monday Mar 16 | Lecture (Week 10) | |
| Wednesday Mar 18 | Tutorial | |
| Monday Mar 23 | Lecture (Week 11) | |
| Wednesday Mar 25 | Tutorial | |
| Friday Mar 27 | Quiz 10 due | |
| Monday Mar 30 | Lecture (Week 12) | |
| Wednesday Apr 1 | Tutorial | |
| April 7-9 | Take-home assessment | |
Monday April 13 |
Assignment 10 due |