COMP4141: Theory of Computation

- Assignments (50%; 12.5% each)
- Final exam (50%)

The rating would be a 5/5 if the issue of administration were resolved but alas, even after a year, it has not changed. The course material is really fascinating but definitely not a typical COMP course. If you decide to take the course, be prepared to work your butt off. The assignments are really fun to do, but they can take so much of your time if you're not up to date with the course material.
The main complaint of the course (and the sole reason why this is deserving of a 4/5 and not a 5/5) is because of administration. It seems somewhat ridiculous to receive marks or feedback (if at all) so late in the term, especially when all of the assignments have been submitted. It makes the feedback that we receive meaningless because we can't use it to improve on the quality of the work. If feedback and/or marks were returned back to us in a timely fashion, then I may consider bumping this up to a 5/5.

- 2 x 2 hour lectures
- 2 hour tutorial

4/5

Yes.

Dr. Paul Hunter

Lecture slides and tutorial solutions are available.

4/5

The formal prerequisites are: COMP9020, and COMP9024.

Recommended textbook: Introduction to the Theory of Computation by M. Sipser.

The formal prerequisites are: MATH1081, and (COMP1927 or COMP2521).

2022 Term 1

90 HD.

- 4x written assignments, worth 50% of your course mark in total (each equally weighed at 12.5%)
- final exam, worth the remaining 50% of your course mark

MATH1081, and either COMP1927 or COMP2521.

Be warned that the jump from something like 2521 to this is quite significant. If you wanted to be the most prepared, it would probably help if you did COMP3121/3821 beforehand, since you are at least introduced to the kind of problem solving you do in this course - make sure to pay attention to reductions in particular.

This is a really nice course, and it’s very interesting if you want to learn more about the fundamentals of how we define and analyse computation in its purest forms. The first half of the course answers the question “how can we model computation?” by looking at various types of languages and their corresponding machines. After these models have been sufficiently established, the second half of the course switches gears in order to answer the question “how can we properly analyse computation?”, by introducing formally the notion of resource-bounded computation and examining many complexity classes that generalise/extend the two most famous classes, P and NP. In some sense it’s a bit of a crime that people studying CS don’t have to do this course or anything similar: computation is the literal basis of the field, yet I think many would struggle to explain what exactly it means when asked. This is an essential for the theoretically-minded CSE student, or anyone who really likes mathematical COMP courses.

There is a price to pay for all of this fun, though - this is quite a hard course. There is no programming to speak of (although we did get to write Turing machines to be run on an online simulator, which is about as close as it gets), so if you struggle with some of the more CS-style math (think MATH1081), proving things and particularly at coming up with constructions, then it’s likely that you’re going to struggle to keep up with assessment tasks.
While this has been one of my favourites, what drags down my rating of the course in terms of the quality of experience is timing issues. Unfortunately, it seems like Paul was dealing with some personal issues on the side of lecturing this term, so there were quite a few instances of delays. A lot of the assignments were released a few days later than anticipated, we didn’t get a lot of the exam prep stuff promised (we ended up getting tutorial and assignment solutions, but none of the past assignment/exam questions) and we didn’t receive any marks back for the assignments until after the final exam. It’s a shame, because if he was a bit more prompt with things, or was at least up front that he was busy and couldn’t get them to us, this course would be an easy 5/5. I hope in future offerings he’s a bit more timely with releasing things.

- 2x 2 hour lectures
- 1x 1 hour tutorial

5/5

Yes, screen and voice recorded. Tutorials, on the other hand, were actively discouraged from being recorded, so you either had to turn up to those or miss out.

Dr. Paul Hunter

There is a weekly set of tutorial questions, but solutions were very scarce - proper solutions to all were released < 24 hours before the exam started, but informal scratch solutions were given by one of the tutors a few days earlier at least.

3.5/5

“Introduction to the Theory of Computation” by Sipser is the primary resource for this course and its analogues at other universities, and many references are made to it in lectures. If you really want more reading material though, then you can also try “Introduction to Automata Theory, Languages, and Computation” by Hopcroft, Motwani and Ullman. This book gets occasional references in lectures.

21T1

94 HD

Prerequisites:

A really fun course, especially if you're mathematically-inclined, or you're interested in theoretical computer science. All of the assignments and exams are proof-heavy, so you'll need to be pretty well-versed in formal proofs and proof techniques. If you've done COMP3821, you may have been introduced to the P/NP complexity classes already, which is the starting point for the course. There's a lot of hardness reductions (if you know what they are) throughout the course, and quite a bit of construction, requiring a different kind of problem solving than many of the courses that you've done beforehand. I really enjoyed this course though, probably more so than any previous COMP course.

Content-wise, you start off going over some very basic proof stuff, revising some of the techniques from MATH1081, but the pace picks up pretty quickly. The whole course revolves around the foundations (not the basics) of theoretical computer science, from defining basic complexity classes like P and NP, leading to more involved classes like PSPACE, L, etc. Towards the end of the course you'll start looking at the polynomial hierarchy, and some of the more unknown areas of computer science with some (less-known) open problems.
Once again, I highly recommend this course to anyone interested in theoretical computer science.

1x 2hr, 1x 1hr Lectures, 1x 1hr Tutorial

3.5/5

Yes; recorded, and transitioned to live online lectures.

Paul Hunter

Lecture slides and tutorial problem provided online. A few solutions, but only the first few tutorials.

5/5

2020 T1

SY