NUS Module Reviews

CS2040 Data Structures and Algorithms

Taken in AY21/22 ST 2 under Dr Chong Ket Fah

NOTE: I took this under the RNSMen Special Term programme after completing CS1010X, and this review will mostly be tailored to future incoming freshmen who are considering doing the same.

Summary:

Consider carefully if you want to do this under the RNSMen ST programme. It WILL clash with orientations (I spent 8 of the last 10 days before the finals at orientation camps), and it WILL be fairly time-consuming (if nothing else because of the graded attendance/participation components). I juggled a full-time internship + this module + attending all the relevant orientation camps - my performance in all 3 along with my mental and physical health suffered quite badly. For my batch, all the CS1010X -> CS2040 students made a Telegram group together for academic and moral support. I highly recommend that future batches do the same.

Special Note on Module Planning: There will be a note on the Special Term 2 registration saying that “Computer Science Undergraduates cannot take CS2040”. If you are an RNSMan NG student majoring in Computer Science, you can still take CS2040 in Special Term because you aren’t an Undergraduate yet :). For Computer Science majors, taking this lets you do your Data Structures and Algorithms module 2 semesters ahead, since once you matriculate you must do CS2040S which has CS1231/S as a prerequisite, while CS2040 only needs CS1010-equivalent. This lets you do funny things like take CS2220 or CS2105 in Year 1 Semester 1, and CS3233, CS3230, CS2103T, CS3241, CS4236, CS5342 in Year 1 Semester 2 (which other CS1010-exempt students can’t). If you are an EE/CEG major, you may have to wrestle with department admin staff who may get annoyed that you didn’t do Data Structures and Algorithms in C++ (CS2040C), but it should work out in the end.

Topics:

Unchanged since the comment by Rain and Coffee. Note that the content of CS2040/S is tied to the lecturer, not module code. If you are taking CS2040S under Prof Chong, the topics will apply to you. If you are taking CS2040 under a different Lecturer, the topics will not apply to you.

Workload:

There are also 2x take-home labs and 2x one-day labs every week, which are completed on the online judge Kattis in Java. They range from extremely trivial to pretty tricky (teque) to hellishly time-consuming (the AVL tree one).

Assessment:

We were only given access to the min, mean, max for each assessment component. Midterm mean was 39/100, Finals mean was ~55/100. The grade ranges are large, with each exam having a low of mid-teens to a high of up to 97 for finals. Cut-off for A+ was ~83%, and cut-off for A was likely mid-to-high 70s.

For CS1010X students who may be worried about their performance (since now you’ll be matched up against real NUS students and not just other NSFs), it is still possible to excel. There were at least 5 CS1010X -> CS2040 students who got A+ for the module, but the caveat is that 4 out of us 5 had prior NOI/Leetcode experience, and a few did not attend orientation camps that were held around the dates of our Finals. If you are a CS1010X student looking to take and excel in CS2040 in ST2 with no Data Structures and Algorithms background, my advice would be to start pre-solving CS2040 labs on Kattis (just find previous semesters’ labs) before ST2 starts, so you can spend most of your time during the Special Term learning the theory properly. You could also go through CS2040 topics on https://visualgo.net/en. However, expect to put in way more effort compared to CS1010X.

VisuAlgo quizzes may seem daunting, but as long as you just keep repeating the “Hard” difficulty quizzes for the appropriate topics, you will quickly realise that there are only a few types of questions for each topic, often with answers that can be pre-computed or otherwise trivially calculated.

Content:

There is a ton of content that is squished within 6 weeks, so you will have a pretty rough time regardless of your background.

CS2040 under Prof Chong is more focused on data structures. Algorithms come in when graphs are introduced, but they seem to mostly serve as motivators for the data structures taught. Instead of learning algorithmic problem-solving paradigms (eg. Greedy, Divide & Conquer, DP, etc.), you will learn the ins and outs of classical data structures (eg. you will learn about collision resolution and hash function choice in hash maps). This was personally quite interesting to me as someone who previously only used these data structures to solve problems without thinking deeply about their nuts and bolts.

Of course, you will be required to have a decent grasp of time and space complexity analysis. However, this mostly comes down to knowing how the data structures work, and any code-tracing type of complexity analysis questions we encountered were easier than those in Prof Tan Tiow Seng’s CS1010X.

There isn’t a big jump in difficulty from Tutorials to Exams. Therefore, grinding Past-Year Papers isn’t as essential as it may be for other modules, but you should do them to at least read through “model answer” pseudocode so you understand how Prof Chong likes his pseudocode answers to look like.

Our exams consisted of MCQs (theory), True/False + short explanation questions (theory), and just over 50% of the paper would be problem-solving questions. These would usually involve applying knowledge of the data structures and algorithms covered in class, but with a small twist/trick for each question. For example, while you’ve learnt Prim’s/Kruskal’s to find a Minimum Spanning Tree in class, an exam question might want you to return a set of edges that happen to be all the edges not within a graph’s Minimum Spanning Tree! Or maybe you need to apply multiple UFDS-es to keep track of multiple “group memberships”, or maybe you need to do a basic SSSP but reverse the edge directions!

Excelling in these problem-solving questions requires both good intuition and a genuine understanding of the content taught. Do practices and make sure you clarify any doubts you have on each data structure’s purpose, operations, efficiency, etc.

Teaching:

Lectures were taught by Prof Chong and were recorded. I did not watch the lectures. However, his slides were great and my friends say he lectures well so he probably does lecture well.

Labs are taught by 2 TAs. All the CS1010X -> CS2040 students were in the same Lab group… except for me 😔. During Lab sessions, the Lab TAs will first introduce relevant Java libraries for the topic at hand, go through the previous Lab’s solutions, and provide hints for this Lab’s problems. Then, you are supposed to submit pseudocode for the Lab’s problems to the TAs during the Lab session. As mentioned before, I would recommend pre-solving the Lab problems because you can just submit them on Kattis (which accepts submissions 30mins before the Lab sessions), pre-write the pseudocode alongside your real code, then during the 2-hour Zoom call you can AFK and go back to your internship/orientation camp/to sleep.

Tutorials are taught by 1 TA. All the CS1010X -> CS2040 students were in the same Tutorial group. I would like to especially mention my Tutorial TA Sun Yucheng, who was extremely knowledgeable, clear, and inspiring. He explained the core concepts of each topic and question well, made extra practices and bonus questions for us to consider, and handled Tutorial Participation grades as transparently and fairly as he could. I genuinely ascribe most of my good performance in this module (especially the theory-heavy exams) to the fact that I got Yucheng as my Tutorial TA.