CS5234 Review
Taken in AY21/22 Sem 1 under Prof Seth Gilbert. All classes were conducted online due to the pandemic.
This graduate-level module is an introduction to four topics about algorithms for large datasets — sublinear time graph algorithms, streaming algorithms (sublinear space), cache-efficient algorithms, and parallel algorithms. These topics are reasonably unrelated and self-contained, and each topic is only covered briefly. Basic results in probability (such as Markov’s and Chebyshev’s inequalities, and Hoeffding and Chernoff bounds) are used liberally. This module is mathematically rigorous, and students are expected to already be very comfortable with performing proofs relating to algorithms.
Graded components:
Most of each lecture is spent explaining one or two problems in detail, complete with mathematically rigorous proofs. In this sense, the concepts are taught in an example-driven manner. Lectures do not cover a lot of content since most of each lecture is spent working out the chosen problems in detail. Lectures usually last around two hours, and Prof Gilbert stays around in the third hour to answer questions from students.
Problem sets are self-contained long questions where students apply concepts covered in the lectures to a new problem setting. Exams contain both true/false questions and long questions, but these are generally easier than the problem sets. Students are expected to produce mathematically sound proofs in the problem sets and exams.
The exams were graded fairly leniently — Prof Gilbert usually awards most of the marks if the main proof ideas are present. This means that it is usually better to submit rough sketches for all questions in the exams than to solve half of them perfectly and leave the other half blank.
The final project is pair work, and students are allowed to choose their partners. Each team is required to choose a research paper (from a list given by Prof Gilbert), read and summarise it (week 10), think of a small extension (either theory or implementation, week 11), create a video lecture (of between 20 minutes to an hour, week 12), and write a final report (week 13). The report submissions (weeks 10, 11, and 13) build on one another, so the final report (week 13) usually also contains everything that were already submitted in weeks 10 and 11. Students are also assigned two video lectures (created by other teams) to watch and review, but it is not clear if and how the reviews will affect the grade of the team being reviewed.
Prof Gilbert is a very good lecturer who is both knowledgeable and entertaining, and his lectures are always fun to listen to. He is also always open and happy to discuss further about the topics covered after each lecture. If you like algorithms and do not fear mathematics, I highly recommend this module.