Academic Year 2022 - 2023
Semester 1
This module introduces different techniques of designing and analysing algorithms. Students will learn about the framework for algorithm analysis, for example, lower bound arguments, average case analysis, and the theory of NP-completeness. In addition, students are exposed to various algorithm design paradigms. The module serves two purposes: to improve the students’ ability to design algorithms in different areas, and to prepare students for the study of more advanced algorithms. The module covers lower and upper bounds, recurrences, basic algorithm paradigms (such as prune-and-search, dynamic programming, branch-and-bound, graph traversal, and randomised approaches), amortized analysis, NP-completeness, and some selected advanced topics.
This module was taught by Prof Arnab and Prof Prashant.
There is a midterm and a final. There is an assignment to be submitted every week and it is graded by effort, except for 3 weeks where it will be graded for correctness. I tend to overkill my assignments by proving everything really rigorously with mathematics. (I am also a maths major and I believe it is expected to be more rigorous than my CompSci peers.) There are also 2 code problems which can get you extra credit.
This has to be my favourite module I have taken so far. I have always enjoyed problem-solving using algorithms and now I am learning much more advanced topics and solving harder problems. Everyone, except me and my group of friends, tends to hate this module. It really shows in the result statistics when the median and mean for the midterm and final are both a fail. I got above the 75th percentile for all my assessments and got an A as a result. I really expect this because I want to avenge my failure (A- for CS2040S and B+ for CS1231S, booooooo)
I really enjoyed my tutorial as well. The questions are challenging enough and it is a good use of the morning to crack some hard problems and get the brain starting. My tutor is also very dedicated and explained things clearly. He also made sure to go around to everyone to check on their progress and make sure they understood what is going on.