CS3230 Design and Analysis of Algorithms

Module: CS3230 Design and Analysis of Algorithms

Semester taken: AY 2021/22 Semester 1

Lecturer: Dr Arnab Bhattacharyya

Tutor: Mr Christian James Welly

Textbook: Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, Stein, 2009. MIT Press

What it is about

This module takes a more theoretical approach when studying algorithms, and students will be taught different skills on analysing algorithms. Topics taught include asymptotic analysis, amortised analysis, NP-completeness, etc. A few types of algorithms will also be introduced in this module, including divide-and-conquer, randomised, hashing, dynamic programming, network, etc.

Assessment components

• 9 coarsely graded assignments: 18%

• 3 graded assignments: 18%

• Tutorial participation: 4%

• 2 programming assignments: 4% (bonus)

• Midterm test: 30%

• Final exam: 30%

Comments

This module is famous for being one of the tougher modules that a Computer Science student will encounter in their 4-year journey. This was true for me as well, as this module takes a more theoretical approach when looking at algorithm, which is a significant change from the other core modules that I have taken previously. Expect to see quite a bit of mathematical and statistical theory involved here, as they form the bedrock of how algorithms are analysed in the field of theoretical Computer Science.

The textbook used in this module is also a famous one, and even has its own Wikipedia page. We often call the book "CLRS", derived from the initials of the four authors of the book. While the module only covers some topics in this book, it is still very useful even after the module has ended. I have seen many software engineers out there still relying on this book as a reference for their day-to-day work.

However, this module is only somewhat useful when it comes to job hunting, as the concepts taught are much more difficult than what is expected during a job interview. However, the topic on dynamic programming can be quite useful when you are aiming for companies that ask DP questions, mainly the MANGA (previously FAANG) companies.

Lectures and Tutorials

There is a 2-hour lecture every week and given the amount of content in this module, most of the lectures overrun the time. It was also because this is the first time that this professor has taught this module, so there were some hiccups in terms of the module planning. Most of the content is in the lecture slides, but it is still worthwhile to attend the lecture, as the professor will be taking the time to explain the thought process behind the concept or algorithm. This definitely helps in understanding how you should approach similar problems in the future, which is an important skill for the test and exams.

There is also a 1-hour tutorial each week, which will go through a series of tutorial questions related to the topic taught in lecture a week prior. The tutorial participation component was measured by the participation in answering the multiple choice questions using the Archipelago. I was rather fortunate to get a great TA (who is a friend too!) for the tutorial session, and he puts in a lot of effort in preparing for the lessons. His explanations and analogies were also very helpful in understanding the difficult concepts, some of which were not even properly taught during lectures.

Assignments

There are 3 types of assignments in this module. 2 of them are written assignments, where you are required to answer questions using words and pseudocode, sometimes using proving techniques (contradiction, mathematical induction, cut-and-paste argument, etc). For 12 weeks in the semester, there is usually one written assignment to be completed for that week, but only 3 of those assignments are graded. The remaining 9 assignments are coarsely graded, in the sense that full credit is given if you attempted all the questions (even if the answers are incorrect).

The third type of assignment is a programming assignment. There were 2 programming assignments during the semester, but both are optional and can grant you bonus marks, if your assignments and tutorial participation marks have not yet exceeded 40%. However, being bonus marks, the assignments given are extremely difficult. It is rare for people to be able to obtain the full credit for the programming assignments.

Given the frequency and difficulty of the assignments, my advice would be to read through the questions as soon as you receive it, and think about the questions every now and then, so that you have more time to arrive at your answer. Some questions may require you to come up with an algorithm with a certain time complexity, which can be time-consuming if you are not skilled in this area.

Midterm Test and Final Exam

The midterm test was 1 hour and 30 minutes to answer 3 questions with various parts. It was an open book exam, and the answers need to be handwritten. The final exam had 2 hours (later extended by 15 minutes) to answer 4 questions with various parts. For both tests, the questions are delivered via a PDF file over LumiNUS, and there was Zoom proctoring.

The questions are around the same difficulty as the ones given in the assignment, and also includes coming up with algorithms on the spot. The test is not easy, and I would recommend that you devote time to revise and practice the questions in CLRS. The markers were also quite lenient, so be sure to attempt every question, even if you do not arrive at your answer or only have a faint idea of what you are doing. The majority of the marks will be given if you are in the right direction.

Lastly, manage your time well, as the amount of time given is usually not enough to finish the paper. It is also a handwritten exam with lots of things to write, which can be challenging if you are used to writing on the keyboard for the entire semester.

Other information

Assignment workload: Heavy. There are 12 written assignments and maybe 2 programming assignments to be completed.

Project workload: None

Readings: None

Recommended if: A compulsory module for Computer Science students. I do not recommend anyone else taking this, except maybe for the Mathematics major students.

Rating: 4.0/5. Tough module but the amount of support in the module and online is a lot.

Expected grade: A-

Actual grade: A- (gentle bell curve)