CS5330 Review
Taken in AY20/21 Sem 2 under Prof Arnab Bhattacharyya. All classes were conducted online due to the pandemic.
This is a graduate-level module covering various fundamentals of randomised algorithms. Topics covered include Markov’s and Chebyshev’s inequalities, Yao’s minimax principle, the Hoeffding and Chernoff bounds, universality of hash functions, Markov chains, coupling, fully polynomial randomised approximation schemes (FPRAS) and fully polynomial almost uniform samplers (FPAUS), and martingales. Online learning is covered in the last two lectures, but is not tested.
This module is quite mathematically rigourous, as one might expect in an algorithms module. While the proofs of some theorems are skipped, students are expected to write many formal proofs for the homework assignments and midterms.
Graded components:
The first midterm covers topics until hash functions, while the second midterm covers the remaining topics. Both midterms are open-book, but this may be due to the pandemic (the midterms were conducted over Zoom).
There is a graded homework assignment every week, making 10 assignments in total, of which the top 9 are counted. Each homework assignment consists of 3 questions, and are generally rather difficult when compared to the questions in the midterms. However, discussion is explicitly allowed.
Scribing is the process of creating lecture notes after attending a lecture. Each student is required to join a group of around 4 people to collectively scribe one lecture, and group sign-up is done on a first-come-first-served basis. Once completed, the lecture notes are distributed to the rest of the class.
The final project is done in groups of around 3 students each. Each group is required to read two research papers on a particular topic (outside the scope of the lectures), and make a report and presentation about them, including additional contributions (such as writing code for the algorithms in the research papers or investigating other potential future research directions) where possible. Students are allowed and encouraged to choose their groupmates, and may attend the presentations of other groups. It is also possible (but probably not recommended) to do an individual project. The research papers given are fairly complicated and may be difficult to understand at times. However, Prof Arnab grades the project extremely leniently.
This module has been tough but enjoyable, and Prof Arnab gives a clear picture of the high-level ideas of the concepts that are taught. It was my most enjoyable module that semester. Grading is lenient in general, and it is probably not necessary to overly worry about the difficulty of this module.