CS2040C - Data Structures and Algorithms (C++)

Introduction

This course introduces students to the design and implementation of fundamental data structures and algorithms. The course covers basic data structures (linked lists, stacks, queues, binary heaps, hash tables, trees, and graphs), searching and sorting algorithms, and basic analysis of algorithms, and basic object-oriented programming concepts.

The programming language used for this course is C++.

We use very basic object-oriented programming concepts in various data structures implementations, e.g., Stack class inherits LinkedList class (as most CS2040C students are not taking CS2030S, CS2040C needs to discuss more OOP than CS2040S).

Note: This introductory message will not be prominent the next time you visit this URL again. This behavior is normal. You can view it again by scrolling to the top of this page.

Course Registration

Prof Halim returns to teach CS2040C in C++ for CEG/InfoSecurity/exchange students in S2 AY 2025/26 (last time he taught a version of CS2040C was on S1 AY 2022/23).

Prof Halim expects around [120-150] students this semester.

Some facts:

  1. Prof Halim has implemented flipped classroom (a type of blended learning) techniques, employing machine-teach-(and-auto-test)-students-on-basic-stuffs, along with in-class live discussion of more challenging problems in his CS2040/C/S classes. From AY 2017/18 until the present, he has received teaching feedback ratings from 4.2 (average) to 4.8 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.469 (good).
  2. Apart from teaching CS2040/C/S on multiple occassions from 2017 to the present, Prof Halim has also taught similar courses that are variants of the current version of CS2040/C/S, namely CS2020 once (2011), CS2010 six times (2011-2016), CS1020E once (2016), and IT5003 ten times (2020-present).
  3. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo, a tool that is utilized extensively in this course.
    The primary goal for this S2 AY 2025/26 is to re-adapt to CEG/InfoSec/exchange students after spending the last 3 AYs focusing on CS cohort.
    The secondary goal is to relearn C++ again after spending most of 2025 solving ~half of LeetCode problems in Python, e.g., C++ std::priority_queue is a MAX heap unlike Python heapq (min heap).

    Rating
    (out of 5.0)
    Aug-Nov 25
    (n=??/1XY?)
    ??%
    Aug-Nov 25
    (n=163/206)
    79%
    Aug-Nov 24
    (n=128/161)
    80%
    Aug-Nov 23
    (n=90/128)
    70%
    Aug-Nov 22
    (n=162/206)
    79%
    Course feedback (SoC CS avg lvl 2000 ~3.9) [4.2..4.4] (tgt) 4.4 (PB for CS2040S) 4.2 == 4.2 == 4.2 ==
    Course difficulty (SoC CS avg lvl 2000 ~4.0) [3.9..4.1] (tgt) 4.0 (PB for CS2040S) 4.2 4.3 == 4.3
    Prof Halim's teaching (SoC CS avg lvl 2000 ~4.2) [4.4..4.6] (tgt) 4.6 (PB for 2040S) 4.5 4.4 4.5 (CS2040C)

    TAs:

    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    2/Tue, 1000-1200 COM1-B112 (PL?) (??/20) 01 TBA
    2/Tue, 1000-1200 COM1-B109 (PL2) (??/20) 04 TBA
    2/Tue, 1400-1600 COM1-B112 (PL?) (??/20) 02 TBA
    2/Tue, 1400-1600 COM1-B109 (PL2) (??/20) 07 TBA
    2/Tue, 1600-1800 COM1-B112 (PL?) (??/20) 10 TBA
    2/Tue, 1600-1800 COM1-B109 (PL2) (??/20) 11 TBA
    5/Fri, 2100-2300 Zoom Recurring Link (free and easy) - various TAs

    List of TAs:

    1. @junhano.o, Lew Choon Hean, ex CS3233 S2 AY24/25 (A) (peak rating: 4.7/CS2030S S1 AY25/26)
    2. @chronal_02, Winston Leonard Prayonggo (peak rating: 4.9/CS2040S S1 AY24/25)
    3. @mono.kanae, Tan Guan Qun, ex CS2040S S1 AY24/25 (A), (peak rating: 4.5/CS2040S S1 AY25/26)
    4. @wilkinsang, Ang Wei Jian, ex CS2040S S1 AY24/25 (A+), (peak rating: 4.6/CS2040S S1 AY25/26)
    5. Tom Schwarz (CS PhD student at NUS Computing)
    6. TBA soon, last slot
  4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
  5. For CS2040S, have you passed CS1231 (or its variants)? You have to...
  6. Have you taken CS1020/CS1020E/CS2010/CS2020? You cannot take CS2040/C/S if you have taken similar/older course(s) that have huge degree of overlap with this course.

Syllabus

This is what students learn in CS2040/C/S as taught by Prof Halim, compare it with the subset IT5003 version:

Course Registration Additional FAQ

If you have any important questions regarding this course, email dcssh at nus edu sg. Relevant answers will be posted here to reach wider audiences.

Q: Will there be a Practical Exam (PE) for your version of CS2040/C/S?
A: Starting from S1 AY2025/26, no... The weightage (that was previously for the stressful PE) will be passed to Final Assessment instead.
Q: Will this course be graded using Bell curve?
A: CS2040C has much more than 40 students each semester. Bell curve system will obviously be used.
Q: I am from CS1010 (C)/other courses that do not use C++, should I pick up C++ on my own before mid January 2026?
A: Yes, that is a very good idea. We will only review basic C++ in the first few weeks of this course and then Prof Halim will encourage you to self-learn C++ along the way.
Q: What Integrated Development Environment (IDE) that we will use in your version of CS2040/C/S?
A: The choice of IDE to do the bi-weekly assignments is "up to you" (as there is no PE).
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my CS3233 textbook: Competitive Programming book: CP4, Book 1 (get a copy legally from lulu.com (eBook) or lulu.com (physical, need shipping from overseas)) should be a good book to have. The answers for many of my test questions may be inside that book. The problem is... I discuss over ~5000+ problems in that book, near impossible to solve them all in just one semester.
Q: Can I S/U this course if I am a freshman when I take this course?
A: No, as this is a level-2 core course. CS2040/C/S has CS1101S/CS1010/variant as pre-requisite and according to Registrar's Office: "The S/U option will apply to all Level 1000 courses (with or without pre-requisites) and Level 2000 courses without other NUS courses as pre-requisites, unless otherwise stipulated by the Faculties/Departments.". So factor this information when taking this course.
Q: I heard from my friend/senior that your version of CS2040/C/S is a flipped classroom course?
A: You heard that correctly. Get ready :).
Q: What are the potential changes that you will apply to CS2040/C/S in S2 AY 2025/26 compared to your many earlier runs of this course?
A: Prof Halim only plan to change these variables this time (all others are planned to be kept roughly constant):
  1. Prof Halim will disappear once this semester, at the end of Week 07 - early of Week 08 (to attend the ICPC Asia Pacific Championship 2026, Taoyuan, Taiwan). My lectures on Week 07 (Tue+Wed) and on Week 08 (Tue+Wed) should not be affected, but I will be quite tired around those two weeks.
  2. Prof Halim will transition back to mostly coding in C++ after mostly spending 2025 to solve ~half of LeetCode tasks.

Note: This course registration section will not be prominent from Week 1 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.

News

Date News

Lesson Plan

Week Tutorial+Lab Combo Lecture Interesting Problem Set
Cells with course material that have not been updated are highlighted with pink color, past classes more than one week ago are hidden so that we can focus on the current and future classes, but you can restore them by clicking 'Show Past' button above, future classes are not highlighted
-01,
29 Dec-02 Jan
Has Not Started Has Not Started,
but please revise your CS1101S/CS1010/equivalent
Prof Halim assumes that all of you have taken
or exempted from this course/its variants

Register at Kattis and LeetCode (use full name as in Matric card),
read C++ specific instructions @ Kattis,
pick up basic C++ by yourself,
and solve the selected Kattis Online Judge (OJ)
Problem Set 0 (PS0) by yourself (CS1101S/CS1010/equivalent level)
and LeetCode OJ programming-skills study plan
(solving many 'trivial problems' from these exercises
---the Kattis one is trackable by Prof Halim, indirectly tells him
about your CS1101S/CS1010/equivalent rough grade)

New Year's Day on Thu, 01 January 2026
Has Not Started
00,
05-09 Jan
Has Not Started Has Not Started
Continue attempting Kattis PS0 and LeetCode programming-skills study plan
(hints in class Discord)
PS0: Easy Coding Challenges
(05-14 Jan)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
01,
12-16 Jan
Has Not Started

Extra exercises from programming-skills:
Mon: plus-one (simulate +1 on a 'big' integer),
Tue: to-lower-case (trivial task),
Wed: robot-return-to-origin ((virtual) 2D grid traversal),
Thu: matrix-diagonal-sum (2D grid processing),
Fri: count-odd-numbers-in-an-interval-range (PIE).
01a. Course Admin, (Re-)Introduction to C++
1. Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + Kattis (NUS) + LeetCode
2. Basic C++ review/new feature introduction
3. Kattis/LeetCode problem(s) discussed today:
A few PS0 and/or programming-skills problems (just for warm-up)

In the middle of 01a: VisuAlgo Online Quiz 0 (0%)
There will be 1 trivial question during the first lecture
Bring your own laptop
This one is put here to speed-up admins (don't skip the first lecture)

Reminder: Read simple algorithms on unsorted array
(Slide 1 to 6-1) before the next lecture

01b. Algorithms on Unsorted Array
Kattis/LeetCode problem(s) discussed today:
rankproblem (a List ADT task; Java ArrayList operations:
add (2 versions), indexOf, remove; and using Java class)

Reminder: Read sorting intro, algorithm analysis,
and O(N^2) sorting algorithms
(Slide 1 to 9-3)
before the next lecture
PS0 (1%)
Due: Wed, 14 Jan 26, 07.59pm

PS1: Basic Programming
Out: Wed, 14 Jan 26, 08.00pm
Mentioned at the end of the first lecture
CS2040C students do problem B+C
problem A is optional (extra (easy) exercise)
02,
19-23 Jan
Has Not Started

Next exercises mostly from programming-skills again:
Mon: monotonic-array (a monotonic array is a sorted array),
Tue: spiral-matrix (interesting 2D grid traversal variant),
Wed: robot-bounded-in-circle (a bit harder than robot-return-to-origin),
Thu: shortest-unsorted-continuous-subarray (discussed in CS2040S Lec02b),
Fri: average-salary-excluding-the-minimum-and-maximum-salary (just do it).

But (e-)Consultation starts
from Fri, 23 Jan
Focus on PS1B+C late birds discussion
02a. Analysis of Algorithms (Slide 1 to 9-3)
1. Live SpeedTest.cpp | py | java demo
(measure runtime, count # of operations, vs asymptotic analysis)
2. Fast review of O(N^2) sorting algorithms
3. Kattis/LeetCode problem(s) discussed today:
thanos (analysis: exponential growth, logarithmic steps)
mjehuric (bubble sort simulation)
height (insertion sort simulation)
nothanks (sorting library and linear pass)

02b. Algorithms on Sorted Array
Kattis/LeetCode problem(s) discussed today:
classfieldtrip (merge of mergesort; or any other solution that works)
shortest-unsorted-continuous-subarray (O(n log n) vs O(n) solutions)

Last flipped classroom reminder:
Read all sorting e-Lecture slides before next lecture
PS1 (2%)
Due: Sat, 24 Jan 26, 07.59am

PS2: Sorting-related Problems
Out: Sat, 24 Jan 26, 08.00am
03,
26-30 Jan
T01+L01: tut01.pdf
Introduction,
OOP review (List ADT, ListArrayTest.py | java)
Algorithm Analysis,
Hands-on, a basic List ADT task,
PS1 Debrief (short),
PS2 Discussion (algorithmic)

Extra exercises:
Mon: kids-with-the-greatest-number-of-candies (simple exercise),
Tue: merge-strings-alternately (discussed in Lec03a),
Wed: sort-colors (discussed in Lec03a),
Thu: find-the-highest-altitude (discussed in CS2040C Lec03b),
Fri: product-of-array-except-self (may help to solve something in PS2).
03a. Sorting (Slide 10 to 13-2)
1. O(N log N) Merge Sort (C++ stable_sort; Java Collections.sort; Python list.sort)
2. Exp O(N log N) (Rand) Quick Sort (C++ sort; Java Arrays.sort (primitives); N/A in Python)
Sorting Online Quiz (easy)
White-box: SortingDemo.cpp | py | java
Black-box: C++ std::vector and std::sort
3. Kattis/LeetCode problem(s) discussed today:
sortofsorting (custom comparator, stable sorting library)
merge-strings-alternately (variant of merge of Merge sort)
sort-colors (Dutch National Flag problem)

03b. Sorting Extras (until end)
A preview of Ω(N log N) lower-bound of comparison-based sorting algorithms
Special-purpose O(N) sorting algorithm: Counting Sort (Only)
Other topics of sorting, e.g., counting inversions, counting minimum swaps
Kattis/LeetCode problem(s) discussed today:
find-the-highest-altitude (prefix sum, for PS2)
PS2, continued
04,
02-06 Feb
T02+L02: tut02.pdf
Sorting Application(s),
Sorting, mini experiment,
QuickSelect,
ADT/List ADT,
VA OQ demo (sorting),
Hands-on, sorting applications,
PS2 Discussion (algorithmic)

Extra Exercises:
Mon: can-make-arithmetic-progression-from-sequence (discussed in Lab02),
Tue: design-linked-list (try adapting SLLDemo (lec03a) to solve this),
Wed: delete-the-middle-node-of-a-linked-list (discussed in CS2040C Lec04b),
Thu: removing-stars-from-a-string (discussed in CS2040C Lec04b),
Fri: add-two-numbers (the second LeetCode problem).
04a. List ADT: SLL/Stack/Queue/DLL/Deque (all slides)
1. Introducing List ADT, (resizeable) array versus Singly Linked List (SLL) way
2. Introducing Stack/Queue ADT
3. Wrapping up with DLL and Deque ADT
Linked List Online Quiz (easy)
White-box: SLLDemo.cpp | py | java implementation
Black-box: C++ std::forward_list, std::stack, std::queue, std::list, std::deque
Kattis/LeetCode problem(s) discussed today:
design-linked-list (try adapting SLLDemo (lec03a) to solve this)

04b. List Extras
Kattis/LeetCode problem(s) discussed today:
delete-the-middle-node-of-a-linked-list (two passes versus two pointers strategies)
removing-stars-from-a-string (bracket matching variant)
PS2 (2%)
Due: Sat, 07 Feb 26, 07.59am

PS3: List+PQ Problems
Out: Sat, 07 Feb 26, 08.00am
05,
09-13 Feb
T03+L03: tut03.pdf
Linked List, mini experiment,
Applications: Reversing/Sorting a List,
Application: Stack-related,
PS2 Debrief (short),
C++ forward_list/stack/queue/list/deque,
VA OQ demo (list),
Hands-on, a list application,
PS3 Discussion (algorithmic)

Extra Exercises:
Mon: merge-two-sorted-lists (discussed in Lab03),
Tue: reverse-linked-list (there are several ways to do this),
Wed: kth-largest-element-in-an-array (discussed in Lec05a),
Thu: smallest-number-in-infinite-set (discussed in CS2040C Lec05b),
Fri: remove-stones-to-minimize-the-total (max PQ simulation).
05a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-2)
1. Introducing PQ ADT
2. Introducing basic Binary Heap structure and its Insert+ExtractMax operations
3. Discussing CreateHeap (two versions) and HeapSort operations
Binary Heap Online Quiz (easy)
White-box: BinaryHeapDemo.cpp | py | java
Black-box: priority_queue.cpp | py | java
Kattis/LeetCode problem(s) discussed today:
kth-largest-element-in-an-array (only short way; proper version at home)

Last 15m of 05a: VisuAlgo Online Quiz 1 (4%)
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: /array (1Q + 2 'new'), /sorting (3 Qs), /list (3 Qs),
and 3 'new' questions especially on asymptotics.

05b. PQ Extras (until end)
1. O(N) CreateHeap analysis and O(N+K log N) PartialSort
2. Discussing UpdateKey(i, newv) and Delete(i) operations
Kattis/LeetCode problem(s) discussed today:
smallest-number-in-infinite-set (min PQ simulation; with lazy deletion)
PS3, continued
06,
16-20 Feb
CNY Eve (Reunion Dinner): 16 Feb 2026 PM (Mon)
CNY Day 1: 17 Feb 2026 (Tue)
so, NO Tuesday Lab, 17 Feb 2026

Extra exercises:
Mon: To find,
Tue: min-stack (CS2040S midterm S1 AY23/24, Part B),
Wed: last-stone-weight (IT5003 Final S2 AY24/25, but n *= 10000),
Thu: To find,
Fri: To find.
CNY Day 1: 17 Feb 2026 (Tue)
so, NO Tuesday Lecture on 17 Feb 2026
CNY Day 2: 18 Feb 2026 (Wed)
so, NO Wednesday Lecture on 18 Feb 2026
PS3 (2%)
Due: Sat, 21 Feb 26, 07.59am

OPTIONAL: Midterm Practice
Out: Sat, 21 Feb 26, 08.00am
NOT GRADED
Recess Week, 21 Feb-01 Mar 2026
You can take a break this week :)
07,
02-06 Mar
T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
C++ std::priority_queue,
VA OQ demo (heap),
Hands-on, a problem involving PQ,
PS3 last Discussion (algorithmic)

Extra exercises:
Mon: total-cost-to-hire-k-workers (discussed in Lab04),
Tue: To find,
Wed: To find,
Thu: group-anagrams (discussed in CS2040S Lec06b),
Fri: making-a-large-island (hard UFDS LC task).
Midterm Test (10% → 12%)
Venue: TBA
Date and Time: Tue, 03 Mar 26 (wk7), 12:10-1:30pm (80 mins)
Open book
Three essay questions (with partial marks scheme) and one special box
Material: Up to List (L04ab on Week 04 + T03+L03 on Week 05), No PQ yet
A few special needs students do the test at TBA

Midterm Test Past Papers (recent 3 AYs only):
AY 2023/24: S1-midterm.pdf, [I didn't teach CS2040S in S2],
AY 2024/25: S1-midterm.pdf, [I didn't teach CS2040S in S2],
AY 2025/26: S1-midterm.pdf, this will be our paper in S2.

07b. Union-Find Disjoint Sets (all slides)
Quick Recap with VisuAlgo
See unionfind_ds.cpp | py | java at GitHub repo of CPbook website
Kattis/LeetCode problem(s) discussed today:
tildes (basic UFDS task)
PS: UFDS is reused in Connected Component (CC) and MST topics
OPTIONAL (0%)
Due: Wed, 04 Mar 26, 06.29pm
NOT GRADED

PS4: Hash Table Problems
Out: Sat, 07 Mar 26, 08.00am
08,
09-13 Mar
T05+L05: tut05.pdf - midterm debrief (TBC)
First half review
(C++, analysis, sorting, LL, PQ)

Extra exercises:
Mon: To find,
Tue: design-hashmap (try adapting HashTableDemo (lec08a) to solve this),
Wed: longest-consecutive-sequence (discussed in Lec08a),
Thu: To find,
Fri: To find.
08a. Table ADT part 1: Hash Table (slide 1 to 10-5)
1. Table ADT, DAT, Basic Hashing; Easiest Collision Resolution (CR): CA (SC)
HashTableDemo.cpp | py | java (all use SC)
2. More CR Techniques: OA (LP, QP, DH); Comparing CA: SC with OA: DH
Hash Table Online Quiz (easy; a bit too tedious on medium/hard settings)
3. Kattis/LeetCode problem(s) discussed today:
design-hashmap (use HashTableDemo)
longest-consecutive-sequence (use set to help checks)

08b. Hash Table Extras (until end)
Other technicalities of Hash Table
Java HashSet/HashMap/Hashtable classes
See unordered_map_unordered_set.cpp | py | java at GitHub repo of CPbook website
Kattis/LeetCode problem(s) discussed today:
group-anagrams (sort and hash)
PS4, continued
09,
16-20 Mar
T06+L06: tut06.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
C++ std::unordered_set, std::unordered_map
PS3 Debrief (short),
VA OQ demo (hashtable),
Hands-on, a hash table application
PS4 Discussion (algorithmic)

Extra exercises:
Mon: determine-if-two-strings-are-close (discussed in Lab06),
Tue: search-in-a-binary-search-tree (discussed in Lec09a),
Wed: delete-node-in-a-bst (discussed in Lec09a),
Thu: minimum-absolute-difference-in-bst (discussed in Lec09b),
Fri: validate-binary-search-tree (recursive check).

Hari Raya Puasa is on Sat, 21 Mar 2026
(Subject to further confirmation)
Sat lab groups move backwards by one week
09a. Table ADT part 2: BST (Slide 1 to 12-1)
1. BST concepts, BST operations, and the multiset idea
BST (only) Online Quiz (medium)
BSTDemo.cpp | py | java
2. Randomly built BST and a preview of balanced BST, e.g., AVL Tree
3. Kattis/LeetCode problem(s) discussed today:
search-in-a-binary-search-tree (implement what we discuss today)
delete-node-in-a-bst (implement the three cases)

09b. Balanced BST and Applications (until end)
QnA about AVL Tree concepts
A short discussion of Select and Rank operations
BST+AVL Online Quiz (hard; need to clear pre-req)
AVL.cpp | (no py yet) | java
Java TreeSet/TreeMap classes
See map_set.cpp | (no built-in py) | java at GitHub repo of CPbook website
Kattis/LeetCode problem(s) discussed today:
minimum-absolute-difference-in-bst (use the correct tree traversal)
PS4 (2%)
Due: Fri, 20 Mar 26, 11.59pm
(so that it does not end on a PH)

PS5: Combo DS Problems
Out: Sun, 22 Mar 26, 08.00am
(so that it does not start on a PH)
10,
23-27 Mar
T07+L07: tut07.pdf
Table ADT 2 - ordered,
(balanced) BST advanced stuffs: multiset, select/rank,
PQ ADT alternative implementation,
Comparison with Table ADT 1: unordered vs ordered,
C++ std::set, std::map,
PS4 Debrief (short),
VA OQ demo (bst)
Hands-on, a tree-related task,
PS5 Discussion (algorithmic)

Extra exercises:
Mon: construct-binary-tree-from-preorder-and-inorder-traversal (discussed in Lab07),
Tue: maximal-network-rank (simple graph DS task),
Wed: destination-city (discussed in Lec10a),
Thu: keys-and-room (discussed in Lec10b),
Fri: reorder-routes-to-make-all-paths-lead-to-the-city-zero (custom traversal).
10a. Graph DS (all slides) + DFS Traversal (Slide 1 to 5-8)
1. Concept checks: Graph DS Online Quiz (medium),
Implementations of graph DS and its applications
No built-in C++ STL container | Python standard library | Java API,
See graph_ds.cpp | py | java at GitHub repo of CPbook website,
2. Early discussion of the basic forms of Graph Traversal algorithms: DFS first
See dfs_cc.cpp | py | java
3. Kattis/LeetCode problem(s) discussed today:
destination-city (degree checks)

Last 15m of 10a: VisuAlgo Online Quiz 2 (4%)
Material: /heap (3 Qs), /hashtable (3 Qs), /bst (3 Qs)
and 3 'new' questions.

10b. Graph Traversal Applications (Slide 7-3 to 7-8)
Finding Connected Components
Kattis/LeetCode problem(s) discussed today:
weakvertices (AM demo)
keys-and-room (visitation check from 0)

NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until you have completed the course
PS5, continued
11,
30 Mar-03 Apr
T08+L08: tut08.pdf
Graph DS Review,
Some Graph Properties Discussion,
Graph DS Conversion Exercise,
DFS Review,
Custom graph DS implementation review,
VA OQ demo (graphds,dfsbfs),
Hands-on, a Graph-related task,
PS5 Discussion (algorithmic)

Extra exercises:
Mon: To change (discussed in Lab08),
Tue: count-good-nodes-in-binary-tree (modified preorder; precursor of DFS),
Wed: number-of-provinces (discussed in Lec11a),
Thu: course-schedule (discussed in Lec11b),
Fri: binary-tree-right-side-view (BFS on a binary tree).

NUS Well-Being Day on Thu, 02 Apr 2026
Good Friday on Fri, 03 Apr 2026
and Easter Sunday on Sun, 05 Apr 2026
11a. Graph Traversal Applications (Slide 6 to 7-12)
1. Review DFS and introducing BFS
2. Focus on a few more basic DFS/BFS applications
(we skip slide 8-11, out of CS2040/C/S and IT5003 scope)
DFS/BFS Online Quiz (medium)
No built-in C++ STL algorithm | Python standard library | Java API,
See UVa00469.cpp | py | java, and
bfs.cpp | bfs.py | java at GitHub repo of CPbook website,
3. Kattis/LeetCode problem(s) discussed today:
number-of-provinces (AM; count #CC; DFS or BFS way)

11b. Graph Traversal Extras
Kattis/LeetCode problem(s) discussed today:
course-schedule (check if the graph is acylic)
builddeps (AL of Strings + postorder DFS toposort demo)
PS5 (2%)
Due: Sat, 04 Apr 26, 07.59am

PS6: Graph(-Related) Problems
Out: Sat, 04 Apr 26, 08.00am
12,
06-10 Apr
T09+L09: tut09.pdf
DFS/BFS advanced stuffs:
Cycle Detection, Toposort++, Floodfill/CC, Bipartite Graph Checker
Modeling exercise,
PS5 Debrief (short),
VA OQ demo (dfsbfs,sssp),
Hands-on, an unweighted SSSP task,
PS6 Discussion (algorithmic)

Extra exercises:
Mon: course-schedule-ii (discussed in Lab09),
Tue: rotting-oranges (discussed in Lec12a),
Wed: network-delay-time (discussed in Lec12a),
Thu: snakes-and-ladders (discussed in Lec12b),
Fri: nearest-exit-from-entrance-in-maze (BFS on grid).
12a. SSSP Problem (all slides)
1. Review of basic SSSP problem (O(VE)/O(kE) Bellman-Ford algorithm skipped)
2. QnA on BFS algorithm for unweighted SSSP
QnA on Dijkstra's algorithm (only modified Dijkstra's)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
SSSP Online Quiz (medium)
3. Kattis/LeetCode problem(s) discussed today:
rotting-oranges (SSSP; implicit unweighted grid graph; BFS)
network-delay-time (basic Dijkstra's)

Last 15m of 12a: VisuAlgo Online Quiz 3 (4%)
Material: /graphds (4 Qs), /dfsbfs (4 Qs), /sssp (2 Qs) - no other time,
and 2 'new' questions.

11b. SSSP Extras
Now CS2040/C/S side discuss Modified Dijkstra's
Other special cases of SSSP problem: on Tree, on DAG
Kattis/LeetCode problem(s) discussed today:
snakes-and-ladders (SSSP; implicit unweighted grid graph; BFS; harder)
PS6, continued
13,
13-17 Apr
T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (sssp),
Hands-on, an SSSP task,
PS6 Discussion (algorithmic)

Extra exercises:
Mon: minimum-genetic-mutation (discussed in Lab10),
Tue: check-knight-tour-configuration (classic BFS),
Wed: minimum-time-to-visit-disappearing-nodes (Dijkstra's variant),
Thu: ugly-number-ii (Min Priority Queue + Hash Table Review).
Fri: flatten-binary-tree-to-linked-list (Skewed Right BST (LL) Review).

Tut+Lab participation marks given (5% → 3%)
13a. MST Problem (all slides)
1. Review of basic MST problem
2. QnA on Kruskal's and Prim's algorithms
Mix and Match of various data structures/algorithms covered so far
3. Kattis/LeetCode problem(s) discussed today:
min-cost-to-connect-all-points (basic MST)
Onsite class photo as momento

Last 15m of 12a: VisuAlgo Online Quiz 3 (4%)
Material: /graphds (4 Qs), /dfsbfs (3 Qs), /sssp (2 Qs),
and 3 'new' questions (inclusive of 2 specifically unweighted SSSP).

13b. No lecture, make-up time window
Details TBA
For the 80m make-up midterm,
it maybe done during NUSOne time window
PS6 (2%)
Due: Sat, 18 Apr 26, 07.59am
Study Week, 18-24 Apr 2026

Final Assessment Discussions at Class Discord

Final Assessment Past Papers (recent 3 AYs only, note the transition from CS2040C/C++ to CS2040S/Java):
AY 2023/24: S1-final.pdf, [I didn't teach CS2040S in S2],
AY 2024/25: S1-final.pdf, [I didn't teach CS2040S in S2],
AY 2025/26: S1-final.pdf, S2-final.pdf (will be our paper).

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (60%)
Date and Time: Sat, 24 Apr 2026, 1-3pm
Venue: TBA (invigilators: Prof Halim, X TA(s): TBA) + ??? (a few special needs TBA + TA: ???)

Open book
No electronic device except one calculator
Details TBC