**Subject Code/Name:** COMP4141 - Theory of Computation**Contact Hours:**- 2x 2 hour lectures

- 1x 1 hour tutorial

**Assumed Knowledge:** 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.

**Assessment:**- 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

**Lecture Recordings?** 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.

**Notes/Materials Available:** 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.

**Textbook:** “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.

**Lecturer(s):** Dr. Paul Hunter

**Year & Trimester of completion:** 21T1

**Difficulty:** 5/5

**Overall Rating:** 3.5/5

**Your Mark/Grade:** 94 HD

**Comments:**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.