CS2040C - Data Structures and Algorithms Review

CS2040C

Taken in: AY21/22 Semester 2
Lecturer: Dr Steven Halim (First half) and Dr Alan Cheng (Second half)
Tutor: Audrey

Grading:

• 3% - Tutorial Participation
• 16% - 6 Kattis Problem Sets PSET1 to PSET6 (2-3 weeks to complete), 3% each, PSET1 is 1%.
• 16% - VisuAlgo Quiz
• 4% Quiz 1
• 12% Quiz 2
• 10% - Midterm Test
• 15% - Practical Exam
• 40% - Final Exam

---

This is a variant of the CS2040 module, taught using C++ instead of Java. While there will be slight differences in the teaching style between 2040, 2040C, and 2040S, concepts should remain the same. You'll learn about (as the name says) data structures and algorithms. Specifically, you'll learn about the following data structures: Array/List, Linked Lists, Stack/Queue/Deque, Priority Queue, Binary Search Tree, Hash Table, Union-Find disjoint sets, and Graphs. (There may be variants of each data structure but overall it's all built from these). The 'algorithms' part refers to algorithmic/asymptotic analysis (big O notation, time complexity, space complexity). So, in this module you'll learn how and what data structures and algorithms to use to perform required tasks, to maintain efficient computer speed and memory.

This is a core module for CEG and Info Sec students. I took this as a UE to test the waters and see if I should apply for a restricted minor in CS. While it's a bonus (or guaranteed if you're in CEG/InfoSec track) if you took CS1010 and CS1231, I didn't take either, and still survived. The advantages are: Easy transition from C to C++, better understanding of some mathematical concepts (When dealing with stuff like algorithm analysis), and graph theory (Majority of last part of CS2040C is graphs. Actually a lot of the data structures explored are graphs of some kind). I think C++ may be a little hard to transition from Python (I took CS1010E), but the problem sets gave me ample practice and I am rather fluent in C++ now. I would say the learning curve for this module is exponential. Things will start out difficult at first, since you are learning a (new?) language and certainly new concepts, but I soon found myself improving by leaps and bounds near the end. The data structures also became less and less muddy the more I studied and applied them. I used to take very long to do my first few problem sets, but with practice I became better in time for PE and the later problem sets.

This was one of the better, if not best mods I took this semester. The class culture is very nice. Prof Steven made a discord server for us and it's really good for clarifying concepts and getting help for assignments, as the Profs and TAs are all very active and transparent on the server. It's also very informative, considering this module covers CS fundamentals I really learned a lot. Workload is really not that high as there is only one problem set every 2-3 weeks, doable within 1-3 days, plus you discuss the solution during tutorial and the TAs help on Discord. Take note that problem set questions have been used in past-year PEs (and vice versa) so the difficulty level is not absurd (Doable in 2 hours basically). The concepts are all taught on VisuAlgo so you should read in advance if you're worried. Lectures cover mostly stuff that's taught on VisuAlgo, but there were also lectures that cover implementation, actual code snippets and application.

Do note that the problem sets and PE make use of competitive programming questions which you have to code in C++. Well, it's Prof Steven after all. Don't be daunted by this fact, they're very doable questions, and honestly if you're studying CS you're bound to have to do these questions in job interviews. On the flip side, the midterm and finals are more open-ended where you discuss mostly in pseudocode, with emphasis on understanding and application.

Lectures were split into two separate days: 2h lecture on concepts (Going through slides + VisuAlgo content), and 1h lecture on implementation of said concepts. Tutorial goes deeper into these concepts. All resources are readily available on the website.

Note that Dr Steven Halim will likely no longer teach this module after this semester, and it will likely be taken over by Dr Alan Cheng. The teaching method may change a little, as prof Steven prefers to use VisuAlgo while prof Alan has his own slides. In the past, Dr Alan also uses Coursemology, instead of Kattis which was used this semester.

---

Detailed Breakdown

Problem Sets

The problem sets are back to back and each lasts a few weeks. They test on concepts taught during lecture but are released before the topic is concluded (So unless you pre-read early on, you won't be able to solve them efficiently). That's ok, as mentioned, you're given loads of time to do the Problem sets, and you discuss them during tutorials. Tutors will give increasingly helpful hints each week coming up to the deadline, until it's really giving away the answer already. This problem set discussion is part of syllabus, it's not dependent on tutor. So, you should be able to clear all problem sets fully.

If you want to practice or look at past Kattis difficulty level, the past questions are all available online.

On Kattis leaderboards, prof will show the top 25% (Meaning the ones who complete the problem set earliest). He mentioned that if you show up here you should be around A grade. Of course this isn't the most accurate indicator...

Practical Exam (PE)

Like the problem sets, the PE is also on Kattis. This means you have immediate feedback on your grades as you submit on Kattis. PE Questions, if you noticed, eventually become Problem Set questions. So, I practiced my PE by treating my Problem Sets like a PE. The difference between Pset and PE is you need to come up with a solution quick, so definitely practice past PE and problem sets (all on the Kattis!).

This year's PE was way, way, WAY easier than the past years. I don't know if it's because the class had been performing quite badly or what but Prof Steven really threw us a bone here such that 190/200 was the 75th Percentile wtf. The make-up PE was also incredibly easy.

Midterm and Finals

These follow the same format of some MCQ, short-answer, and essay questions. You'll have some questions on analysing time complexity, maybe fill in snippets of code, or maybe questions about data structure properties.

The essay questions, which carry more marks, usually ask you to solve a problem just like the Problem sets, except you explain in pseudocode. You'll have to mention the time/space complexity, data structures and algorithims used. These are usually based off actual Kattis questions (The final questions are all existing Kattis questions which you can practice - check out the Kattis link above).

Final Note

I heard from my friends that CS2040C is the hardest among CS2040 variants. The bell curve probably has two peaks, the actual median and the smurfs. I find it ridiculous people who have had competitive programming experience still have to take this module, but oh well!

Expected grade: A-

Actual grade: A

Had to slog for this A. I'm satisfied.

Reviewed by: ZH