CS2040S: pass the exams, not just read the notes
Your complete guide to National University of Singapore's data structures and algorithms course. See where the marks are, work real practice questions, and study with an AI tutor that knows CS2040S.
Sia generates CS2040S practice questions, walks through analysis of algorithms; algorithms on sorted arrays and sorting step by step, and quizzes you on the material the exam weights most heavily.
Find what is wrong
You need a data structure supporting three operations on a set of integers, all as fast as possible: insert a value, remove the smallest value, and check whether a given value is present. Which choice is best?
Check each structure against all three operations rather than the one it is famous for. That habit is most of what this course tests.
A hash set gives expected constant insert and contains, but it stores no order at all, so extracting the minimum means examining every element, again O(n).
A sorted array gives O(log n) contains by binary search and O(1) access to the minimum, but insertion has to shift elements, so it is O(n).
A balanced BST such as an AVL tree keeps the elements ordered and the height logarithmic, so all three operations are O(log n). It is the only option that is good at all three at once.
The trap: Picking the structure that is fastest at the operation you noticed first. The heap looks right because extract-min is its headline operation, and the hash set looks right because contains is. Both options in this question quote a complexity the structure does not actually deliver, which is the standard trap in this course: the claimed bound is plausible for that structure in general but wrong for that particular operation. classic slip!
One exam decides 50% of your grade. Half the course. The weighting previously carried by the practical exam was moved into this component when the practical exam was removed from Semester 1 of AY2025/26. This whole page is built around that.
Overview
What CS2040S is, and where it sits
CS2040S is the data structures and algorithms course taken by NUS Computer Science undergraduates, taught in Java. It introduces the design and implementation of fundamental data structures, linked lists, stacks, queues, binary heaps, hash tables, trees and graphs, together with searching and sorting algorithms and the analysis that tells you which to reach for.
It is run as a flipped classroom. You are expected to work through the designated e-lecture material and attempt the online quiz questions before class, and the in-class time is spent reviewing the harder parts and solving judge problems live. The published weekly shape is about ten hours: two hours of self-study, three hours of lecture, two hours of tutorial and lab combined, and around three hours on the current problem set.
The content arc runs from linear structures to non-linear ones and then to graphs. It opens with algorithm analysis and sorting, moves through the list ADT and its stack, queue and deque implementations, then priority queues and binary heaps, hash tables, union-find disjoint sets, and binary search trees including AVL balancing. The last third is graphs: representations, DFS and BFS with their applications, single-source shortest paths including Bellman-Ford and Dijkstra, minimum spanning trees with Kruskal and Prim, and a closing preview of NP-completeness that leads into CS3230.
One design choice shapes how the course feels: the problem sets are submitted to an online judge that tests them automatically, and code is checked for similarity. The course explicitly permits using generative AI tools only after you have spent more than two hours on a task without external help, and requires that you re-code the solution yourself. The reasoning given is practical rather than moral, which is that the final assessment gives you two hours and no assistance.
Always treat your own course outline and the exam timetable as authoritative.
Difficulty & time commitment
Is CS2040S hard, and how much time does it take?
CS2040S is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the course.
Is this course for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You keep up with the flipped-classroom preparation. Lectures review the hard parts of material you were meant to have read, so arriving unprepared costs you the session.
- You are comfortable being tested continuously. Seven problem sets and three quizzes mean the grade is built steadily rather than in one push.
- You think in trade-offs. Almost every examinable question is really asking which structure fits the constraints.
- You can write correct Java under time pressure, including from a language background that is not Java.
You may struggle if
- You expect open book to mean easy. Both papers are open book precisely because they test application and analysis, which notes do not supply.
- You outsource the problem sets. The submission system checks for similarity, and more to the point, the final gives you two hours alone.
- You defer the Java transition. The course reviews it only briefly in the first weeks.
- You treat analysis as a separate topic. Asymptotic reasoning is threaded through every week and is the vocabulary the papers are written in.
- For every structure, write down the complexity of all its operations, not just the one it is known for. The examinable questions live in the operations people forget.
- Do the online judge problems without looking at the discussion first. The value is in the failed attempt; that is the two hours the AI policy is describing.
- Redo past midterm and final papers under real time constraints. The course publishes the recent papers, and open book means practising with your notes is the realistic rehearsal.
- When a problem looks new, ask what graph or table it is secretly about. Most of the harder tasks are modelling exercises in disguise.
Syllabus
The 13 topics, week by week
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
W1 · Course setup and Java review; algorithms on unsorted arrays
Part 0, Part 1The transition week. Students arriving from Python or JavaScript courses are expected to pick up Java largely on their own, with only a brief in-class review. Then simple array algorithms, complete search and two-pointer techniques.
W2 · Analysis of algorithms; algorithms on sorted arrays
Part 1Asymptotic analysis introduced against measured runtime, then the quadratic sorting algorithms and what sortedness buys you. Everything later in the course is discussed in this vocabulary.
W3 · Sorting
Part 1Merge sort and randomised quick sort, the library sorts that implement them, the comparison-based lower bound, and counting sort as the special-purpose linear-time exception.
W4 · List ADT: linked list, stack, queue, deque
Part 2Array versus singly linked list implementations, then the stack, queue and deque abstractions built on them, contrasted with the Java library classes that provide them.
W5 · Priority queue and binary heap
Part 3The priority queue abstraction and its binary heap implementation, insert and extract-max, heap construction in linear time, and heapsort. The first online quiz falls in this week's lecture.
W6 · Table ADT part 1: hash tables
Part 3Hashing and collision resolution by separate chaining and by open addressing with linear probing, quadratic probing and double hashing, then the Java hash-based collections.
W7 · Midterm test; union-find disjoint sets
Part 3The midterm falls here and covers material up to priority queues, with hash tables excluded. The remaining session introduces union-find disjoint sets, which return later in connected components and minimum spanning trees.
W8 · Table ADT part 2: binary search trees and AVL
Part 3BST operations, the difference between a randomly built tree and a balanced one, AVL trees, and the ordered map and set classes that rely on them.
W9 · Graph data structures; depth-first search
Part 3, Part 4Adjacency matrix, adjacency list, edge list and implicit graphs, then DFS and its first applications. The second online quiz sits in this lecture.
W10 · Graph traversal applications: DFS and BFS
Part 4BFS alongside DFS, and the standard applications: connected components, flood fill on implicit grid graphs, cycle detection and level-order traversal.
W11 · Single-source shortest paths
Part 4Bellman-Ford in general, BFS for unweighted graphs, Dijkstra for non-negative weights, and the special cases on trees and directed acyclic graphs. Choosing the right one for the graph you have is the skill being tested.
W12 · Minimum spanning tree
Part 4Kruskal and Prim, both greedy, their variants and applications, and mixing them with the structures from earlier in the course. The third online quiz and the tutorial participation mark land here.
W13 · Wrap-up and beyond polynomial time
Part 5Course summary, a short introduction to NP-completeness as a preview of CS3230, and final assessment guidance.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Final assessment | 50% | Two hours, open book. No electronic device is permitted except one calculator. Examination period. Half the course. The weighting previously carried by the practical exam was moved into this component when the practical exam was removed from Semester 1 of AY2025/26. |
| Midterm test | 20% | 90 minutes, open book. One structured box question plus three essay questions, marked with a partial-credit scheme. Week 7. Covers material up to priority queues; hash tables are excluded. The weighting was raised from 10% to 20% for Semester 1 of AY2026/27. |
| Problem sets | 13% | Seven sets released roughly fortnightly and submitted to an online judge, which tests them automatically. A plagiarism checker is built into the submission system. Across the semester. Individually weighted 1% for the warm-up set and 2% for each of the remaining six. Around 6 hours of work per set is the published expectation. |
| Online quizzes | 12% | Three in-lecture quizzes on the visualisation platform used throughout the course, taken on your own laptop. Weeks 5, 9 and 12. 4% each. A zero-weighted practice quiz runs in the first lecture. |
| Tutorial and lab participation | 5% | Assessed across the weekly tutorial and lab combination sessions. Across the semester. Awarded in Week 12. |
- No single-component hurdle is published. In practice the final at 50% decides the grade, and the continuous components are where a comfortable margin is built before it.
- Both timed papers are open book. The midterm is 90 minutes with one structured box question and three essay questions marked with partial credit; the final is two hours. Because the papers are open book, marks come from applying the right structure and analysing it correctly rather than from recall.
- Calculator policy: One calculator is permitted in the final assessment. No other electronic device is allowed. For the in-lecture online quizzes you bring your own laptop, which must run for at least 15 minutes on battery.
This is an exam-cram course. With the exams at 50% of the grade and the final assessment alone at 50%, your result is overwhelmingly decided by how well you perform under time pressure. Half the course. The weighting previously carried by the practical exam was moved into this component when the practical exam was removed from Semester 1 of AY2025/26.
Final exam timing: 2026-11-24. Confirm the exact date and venue on your exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The course rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Asymptotic analysis, including deriving complexity from code rather than recognising it
- Sorting algorithms, their complexities and when each is appropriate
- List ADT and its stack, queue and deque implementations
- Priority queues and binary heaps, including construction and heapsort
- Note the scope: the midterm covers material up to priority queues and excludes hash tables
Before the final heaviest topics
- Hash tables and both families of collision resolution
- Union-find disjoint sets and where they reappear
- Binary search trees and AVL balancing, including the rotation cases
- Graph representations, and the complexity consequence of choosing one
- DFS and BFS with their applications: components, flood fill, cycle detection, topological order
- Shortest paths: Bellman-Ford, BFS on unweighted graphs, Dijkstra, and the tree and DAG special cases
- Minimum spanning trees by Kruskal and by Prim
The mistakes that cost marks
Quoting a complexity the structure does not deliver. A heap does not support O(log n) membership testing and a hash set does not support O(1) minimum extraction. Marks are lost on the operation nobody rehearsed.
Choosing Dijkstra reflexively. It requires non-negative weights. On an unweighted graph BFS is simpler and faster, on a DAG the dynamic programming approach is better, and with negative weights you need Bellman-Ford.
Submitting late to the judge. Problem sets have hard deadlines and are auto-graded. Code that would have passed an hour later is worth nothing.
Treating open book as a substitute for fluency. Two hours is not enough time to look things up. Notes help you confirm a detail; they do not help you decide which structure the problem needs.
Teaching team
Who teaches CS2040S
The bios below are factual. We do not rate lecturers; any star ratings are submitted by students who have taken CS2040S.
Steven Halim
Lecturer for CS2040S in Semester 1 of AY2026/27 and for the CS2040 family since 2017. He created the algorithm visualisation platform the course uses extensively, and runs the course as a flipped classroom with live problem solving in lectures.
Teaching team as listed in the course materials reviewed. AskSia does not rate lecturers; star ratings are submitted by students who have taken CS2040S.
Formula & concept sheet
The vocabulary and formulas you must own
- Abstract data type (ADT)
- A structure defined by the operations it supports rather than how it stores anything; the course's organising idea.
- Asymptotic analysis
- Describing how running time grows with input size, ignoring constants; the vocabulary every topic is discussed in.
- Complete search
- Solving by examining all candidates, the baseline against which cleverer approaches are measured.
- Divide and conquer
- Splitting a problem into smaller instances of itself, as in merge sort and quick sort.
- Greedy algorithm
- Taking the locally best choice at each step, correct only when the problem has the right structure, as in Kruskal and Prim.
- Binary heap
- A complete binary tree with the heap property, giving logarithmic insert and extract-min and linear-time construction.
- Hash table
- Mapping keys to slots for expected constant-time access, with separate chaining or open addressing to resolve collisions.
- Open addressing
- Resolving collisions within the table itself by probing: linearly, quadratically, or by double hashing.
- Union-find disjoint sets
- A structure tracking a partition under merging, used for connected components and in Kruskal's algorithm.
- Binary search tree
- An ordered tree giving logarithmic search when balanced and degrading to linear when not.
- AVL tree
- A self-balancing BST that rotates to keep its height logarithmic, guaranteeing the worst case.
- Adjacency list and adjacency matrix
- The two main graph representations; the choice changes traversal and edge-lookup complexity.
- DFS and BFS
- Depth-first and breadth-first traversal; BFS also solves shortest paths on unweighted graphs.
- Bellman-Ford
- Shortest paths tolerating negative edge weights, at higher cost than Dijkstra.
- Dijkstra's algorithm
- Greedy shortest paths for graphs with non-negative weights, usually implemented with a priority queue.
- Minimum spanning tree
- The cheapest set of edges connecting every vertex, found greedily by Kruskal or by Prim.
- NP-completeness
- The class of problems with no known polynomial-time algorithm, introduced at the end of the course as a preview of CS3230.
Common acronyms: {'term': 'ADT', 'def': 'Abstract data type'} · {'term': 'PQ', 'def': 'Priority queue'} · {'term': 'UFDS', 'def': 'Union-find disjoint sets'} · {'term': 'BST', 'def': 'Binary search tree'} · {'term': 'AVL', 'def': 'The self-balancing binary search tree named for Adelson-Velskii and Landis'} · {'term': 'SSSP', 'def': 'Single-source shortest paths'} · {'term': 'MST', 'def': 'Minimum spanning tree'} · {'term': 'DnC', 'def': 'Divide and conquer'} · {'term': 'DP', 'def': 'Dynamic programming'} · {'term': 'PS', 'def': 'Problem set'}.
Where it fits
Prerequisites, related courses & why it matters
You need CS1010 or one of its variants, and for CS2040S specifically you also need CS1231 or its variant. You cannot take it if you have already taken an older overlapping course such as CS1020, CS2010 or CS2020. Because CS2040S has NUS course prerequisites, the satisfactory/unsatisfactory option does not apply to it.
Your CS2040S study toolkit
Study the course with Sia, not just read about it
Each tool already knows CS2040S: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
What is the difference between CS2040, CS2040C and CS2040S?
Same core material, different cohorts and languages. CS2040 is the Java version for non-CS students, CS2040C is the C++ version for computer engineering, information security and exchange students, and CS2040S is the CS cohort version in Java, which additionally requires CS1231 or its variant.
How is CS2040S assessed?
Final assessment 50%, midterm 20%, seven problem sets 13% in total, three online quizzes 12% in total, and tutorial and lab participation 5%.
Is there still a practical exam?
No. The practical exam was removed from Semester 1 of AY2025/26 and its weighting moved into the final assessment. Any older breakdown you find that includes a practical exam is out of date.
Are the papers open book?
Yes, both the midterm and the final are open book. The final permits one calculator and no other electronic device. Open book changes what is tested: not recall, but whether you can pick the right structure and analyse it correctly under time pressure.
I did not learn Java in my first programming course. Is that a problem?
It is manageable but you should start early. The course reviews basic Java only in the first few weeks and expects you to self-learn the rest along the way, so picking it up before the semester starts is worth doing.
Can I use generative AI on the problem sets?
The course sets a specific condition: only after you have spent more than two hours attempting a task without any external help, and you must eventually re-code the solution yourself. The stated reason is that the final assessment gives you two hours with no assistance, so a task you could not do alone is a gap you need to close.
Is CS2040S bell curved?
The course page states that a bell curve is used, on the basis that the class is far larger than the threshold at which it applies. The Semester 1 AY2026/27 class is around 230 students.
Study CS2040S with Sia
Work through analysis of algorithms; algorithms on sorted arrays, sorting, list adt: linked list and the rest of the course with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
