CS2040 Data Structures and Algorithms

Module: CS2040 Data Structures and Algorithms

Semester taken: AY 2018/19 Special Term 2

Lecturer: Dr Chong Ket Fah

Tutor: Mr Ng Tzer Bin

Textbook: CP3: Competitive Programming

What it is about

This module is all about tackling problems and the tools that you can use. You will learn to analyse algorithms, understand its efficiency and be exposed to the different contexts in which you have to tweak certain algorithms to achieve what is desired.

Assessment components

• Tutorial attendance/participation: 3%

• Lab attendance: 2%

• In-lab Assignments: 20% (2.5%/problem)

• Take Home Assignments: 12% (2%/problem)

• Online Quiz: 8% (4% each)

• Midterm: 15%

• Final Exam: 40%

Comments

Moving away from learning the language of Java as taught in CS1010J and in CS2030, this module focuses more on the discussion of the tools that you can use to solve problems. Perhaps up till this point, most of the problems that I have encountered can mostly be solved with a couple of loops, maybe recursion. However, this module is the one that exposes you to the wide array (pun intended) of ways to approach a certain problem, and even evaluate if the way that you are solving the problem is the most efficient.

As I took this module during the special term (plus I was also interning at NUS IT), the workload is rather intensive as they had to squeeze the usual 2 weeks into 1 teaching week here. However, this also meant that the lecturer is forced to cut back on some assessment components, although overall the content matches (if not exceeds) those that were taught in the usual semesters.

There are about 4 hours of lecture, 2 hours of tutorial and 4 hours of labs per week (concentrated on Tuesdays and Thursday). You essentially spend the whole day in NUS reading 1 module. Accompany that with the take home assignments and you will have a pretty busy week ahead.

To me, this module was rather eye-opening as you get to approach problems from a different perspective. However, there are some math involved in this, especially when you come to graphs, so watch out, though some parts of this module should have been covered in CS1231.

Tutorials

The tutorials are 2 hours per week split into 2 1-hour slots, which most of the time will be spent on going through the tutorial questions. However, the tutorial questions are worded such that it encourages some form of discussion about the topic, especially regarding the efficiency of the algorithm used. I did not really expect much, but after we had a replacement tutor for 1 or 2 lessons, I was quite glad that I had this tutor.

There is also an online test component, but it is just the Visualgo-generated questions. Before the test, just grind as much as possible and make a small cheatsheet for some of the more tedious questions that you encounter, and you will be fine. Most, if not all, students get full marks for the online test.

Laboratory

For labs, we will be given 1 or 2 questions on Kattis to solve for the session, and you must get all test cases to pass within the specified time frame before the end of the lab session. Most of the questions are easy and I usually get to leave within the first half hour. There are times, however, that you just don’t get it, and seeing your classmates leave one by one can be a rather stressful thing. I do pity the girl that cried for the last lab session, hope you did alright.

There is also a take-home lab assignment that you have to complete over the week, also on Kattis. These questions are much harder to complete and for me personally, I spent almost the whole weekend getting them done. Some of the answers are available online if you know how to Google for them, which definitely saved a lot of time since Kattis does not provide you with feedback on why you have failed a particular test case.

Mid-terms and Finals

The mid-terms and finals were all written questions and were of similar format. The first part requires you to prove if the given statement is true or false (recall how to prove such statements in CS1231), whereas the second part will give you scenarios and to devise out an algorithm to solve the problem. Writing actual code is not necessary (though it might help in your thought process, if you are more of a coder), and it is definitely possible to score by writing point form, as long as you articulate the steps of your algorithm clearly to the examiner.

The tests are open book and I would advise you to come up with a cheatsheet which lists out all the algorithms that you have learnt in the module and the different situations that such algorithms can be applied to. It would also be beneficial to know which parts of the algorithm can be tweaked so that you can adapt it for the given problem.

I didn’t get to see how other people performed for this module, but mid-terms I got 26/40 and for finals I felt that it was a very easy paper (which was also admitted by the prof prior to the exam). I am guessing it is because most of the students taking this module are not from Computing, so they had to make the module easier after the mid-terms.

Other information

Assignment workload: There are 10 in-lab assignments (best 8 of 10), 4 take-home lab assignments and 3 online quizzes (best 2 of 3)

Project workload: There were no projects.

Readings: None

Recommended if: A compulsory module for some computing majors and is a good module for those that are interested in analysing algorithms and their efficiency, which is not usually a concern in day-to-day practice.

Rating: 4.0/5. Interesting module but the workload killed me a little inside.

Expected grade: A (was a little worried about mid-terms but the rest were good)

Actual grade: A