Prof: Sanjay Jain

CS3231 is a challenging theoretical module that introduces topics from theory of computation. The notes and tutorials are all on the course website, and I have published my own notes ([pdf]  [tex]) that covers every topic, these notes are more comprehensive than the slides since the slides lack a lot of details that the professor only covers during the lectures.

This module had 3 main topics:

1. Regular languages
2. Context free languages
3. Turing machines and complexity

Each topic introduces a model of computation, and we spend a few weeks studying their definitions, their limits, and their properties.

Personal opinion

This was the best module I have taken in NUS so far. I looked forward to weekly lectures and tutorials as the theory in this module felt really interesting and fun. The lecturer, Prof Sanjay, is clearly passionate about the topic which makes his lectures really engaging. The slides are not very detailed because he doesn't just read off the slides, but explains each topic while drawing diagrams on the whiteboard. The only TA, Ivan Koswara, marks tutorials for the whole class (60 students) every week, while at the same time answering questions on the discord and providing a substantial amount of practice question before each assessment.

I strongly recommend every CS student to take this module. Given that we work with computers, shouldn't we know the limits that of what our devices can do? After taking this module, I have a better understanding of how RegExs work, how different parsers can be designed for context free grammars, what Turing Machines actually are and their many equivalent forms of computation, and what NP completeness actually means and how to prove problems are NP hard.

I will warn that the bell curve for this module is definitely tough, given that this is not a compulsory module. However there is a midterm that occurs before reading week, and the professor marks the paper in 1 day, so you can drop the mod before reading week if your midterm 1 score is bad. The prof is also very lenient in his marking, and brushes off minor mistakes as long as you know what you are doing. If you study and absorb the lecture material every week, you are sure to do well in this module.

Workload: 7/10
Tutorials on average took 2-3 hours for me, I also spent every week writing my own notes.

Enjoyability: 10/10
As said above, my favourite mod in NUS so far 😃

Difficulty: 7/10
The earlier topics on regular languages and context free grammars are pretty easy. Turing machines is where it gets hard and I got a little complacent (as evident from my finals marks below)

Grade breakdown

The way tutorial participation was graded is as follows:

• Each time you present gives you 1 mark (capped at 4), the prof makes sure everyone gets a chance to present every tutorial.
• Each tutorial attended gives you 0.25 marks
• Each tutorial submission gives you 0.25 marks

This sums up to 10, and your final score is rounded up to the nearest integer. That means you can miss a total of 3 submissions/attendance and still get the full participation mark.

Assessment	Marks	LQ	Med	UQ
Tutorial Participation	9/10	9	10	10
Midterm 1	21/25	12	15.5	21
Midterm 2	25/25	14	19	22.5
Finals	26/40	-	-	-
Total	81/100	-	-	-

Excepted grade: B+/A-
Final grade: A-