IT5003 - Data Structures and Algorithms (Python)

Introduction

This course introduces non-computing students to efficient computational problem solving in an accelerated pace*. Students will learn to formulate a computational problem, identify the data required and come up with appropriate data structures to represent them, and apply known strategies to design an algorithm to solve the problem. Students will also learn to quantify the space and time complexity of an algorithm, prove the correctness of an algorithm, and the limits of computation. Topics include common data structures and their algorithms (lists, heap, hash tables, trees, graphs), algorithmic problem solving paradigms (greedy, divide and conquer, dynamic programming), and NP-completeness.

The programming language used for this course is Python 3.

We use very basic object-oriented programming concepts in various data structures implementations, e.g., Stack class inherits LinkedList class.

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.

* Since S1 AY 2024/25, IT5003 is now a full 12-weeks course (6-weeks in the first half + recess (to catch up) + 6-weeks in the second half) instead of the true accelerated 8-weeks (week 7-reading week) after students finish IT5001.

Course Registration

This is the going to be the twelfth time Prof Halim teaches this 12-weeks IT5003 course for MComp General Track (GT) — the main/largest group of students — (plus a bit of other MSc degree specializations: Digital Financial Technology (DFT) + Biomedical Informatics (BMI) + Industry 4.0 students) and also a few (usually around [15..25]-ish) Graduate Certificates in Computing Foundations (GC-CF) students. Prof Halim sets IT5003 (in Python) as a 'subset' (obviously, as we only have 12-weeks of 2 hours/week) of his full 13-weeks of 3 hours/week CS2040S/CS2040C Undergraduate version of similar course. The previous iterations were already (very) good. One thing to take note is that Prof Halim's teaching style is flipped classroom that may be quite surprising for some adult learners who are not used to this teaching style in the past.

For S1 AY 2026/27 (Aug-Nov 2026), Prof Halim expects about [70-100] students (S1 size is smaller) who have passed IT5001 in S2 AY 2025/26 (or earlier).

Some other 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 IT5003 classes. From AY 2020/21 until the present, he has received teaching feedback ratings from 4.2 (average) to 4.6 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.455 (good).
  2. 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 S1 AY 2026/27 is on how to prepare the current generation of (CS) students to co-exist with the ever-growing capabilities of Generative AI tools.

    Rating
    (out of 5.0)    		 Aug-Nov 26
    (n≥??/XY)
    ≥60%?    		 Jan-May 26
    (n=119/227)
    52% ▼    		 Aug-Dec 25
    (n=56/96)
    58% ▲    		 Jan-May 25
    (n=76/146)
    52% ▼    		 Aug-Nov 24
    (n=19/33)
    58%
    Course feedback (SoC CS avg lvl 5000 ~4.2) [4.1..4.3] (tgt) 4.0 (PW) ▼ 4.4 ▲ 4.1 ▼ 4.3
    Course difficulty (SoC CS avg lvl 5000 ~3.7) [3.9..4.1] (tgt) 4.2 (joint-PW) ▲ 4.0 == 4.0 ▼ 4.2 (joint-PW)
    Prof Halim's teaching (SoC CS avg lvl 5000 ~4.4) [4.3..4.5] (tgt) 4.2 (joint-PW) ▼ 4.6 (joint-PB) ▲ 4.2 (joint-PW) ▼ 4.6 (joint-PB)
    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    a/Sat, 1000-1200 COM1-B112 (PL1) — for part-time OR outbidded full-time (??/25) B3A @loveandbejoyful
    b/Mon, 1400-1600 COM1-B111 (PL4) — for full-time students (??/25) B1 @prof_halim
    b/Mon, 1600-1800 COM1-B111 (PL4) — for full-time students (??/25) B2 @loveandbejoyful
    b/Mon, 1600-1800 COM1-B112 (PL1) — for full-time students (??/25) B2A @platyan if he can [TBC]

    List of TAs for Aug-Nov 2026:

    1. @prof_halim, Associate Professor Steven HALIM (IT5003 course lecturer 12x)
    2. @loveandbejoyful, Tan Yu Wei (JEANETTE) (IT5003 full-time TA 9x, will take TWO lab groups: the Sat morning one and one of the Mon slots)
    3. @loveandbejoyful, Jeanette 2nd group
    4. @platyan, Lim Jun An BRYAN, ex CS2040S S2 AY24/25 (A) (peak rating: 4.6/CS2040 S1 AY25/26)
    Unless the class size suddenly grows above 100 pax, Prof Halim is probably not looking for another part-time TA...
  3. Have you passed (or exempted from) IT5001 or CS1010 (or its variants)? You have to...

Syllabus

This is what students learn in IT5003 as taught by Prof Halim, compare it with the superset CS2040S/CS2040C version:

Course Registration Additional FAQ

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

Q: Will there be a Practical Exam (PE) for your version of IT5003?
A: We do not have enough class contact time for IT5003, so no.
Q: Will there be a mid-semester Midterm Test for your version of IT5003?
A: Starting from S1 AY 2025/26, yes, on Week 07. For S1 AY 2026/27, the weightage will be increased further (from 16% to 20%) to match the new CS2040S S1 AY 2026/27 setup.
Q: I am from IT5001 (the most relevant course before this), but I don't think my Python skill is up-to-the-requirement, should I improve my Python coding ability on my own before January 2026?
A: Yes, that is a very good idea, use December 2025 University holiday for that. We will start with the optional PS0.
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 a lot of problems in that book, near impossible to solve them all in just one semester.
Q: I heard from my friend/senior that your version of IT5003 is a flipped classroom course?
A: You heard that correctly. Get ready :).
Q: What are the potential changes that you will apply to IT5003 in S1 AY 2026/27 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 - with assumption that S2 AY2025/26 dip was due to personal reasons):
  1. Prof Halim adjusts the weightage of this course to now match CS2040S version (notably, midterm goes up from 16% to 20%; VisuAlgo Online Quizzes total goes down from (1+5+5+5 = 16%) to (0+4+4+4 = 12%)).
  2. Prof Halim plans to disappear twice this semester, on Week 01 (to attend IOI 2026, Tashkent, Uzbekistan) and on Reading Week - not affecting this class (to attend ICPC World Finals 2026, Dubai, United Arab Emirates). Most likely, the first week's class will be recorded.
  3. Prof Halim has lots of experience with LeetCode. Therefore, he has extended the Optional Essential LeetCode daily tasks from 13 weeks x 5 (Monday to Friday) = 65 tasks last year to 15 weeks (adding Week 0 and reading weeks) x 6 (Monday to Saturday) = 90 tasks this semester. At least 3 out of 6 --, i.e., half of -- these weekly tasks will be officially discussed in Lecture or Lab session with the rest to be openly discussed in our internal class Discord.
  4. Possible tweak: Lab sessions (the 2nd hour of each Monday tutorial+lab combo) will likely be turned into mock interview sessions (details TBC).

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 S1 AY 26/27

The 4 units IT5003 syllabus will be delivered over 12 weeks.
This course is a subset of a similar CS2040S course, approximately 2*12/3*13 = 24/39 ~= 62% of the content of CS2040S.
The weekly lesson plan of Week X is typically as follows (1+(1+1)+(2+2)+3 = 10 hours/week):

  1. Give yourself about 1-hour/week to self-study as much as you can from various online Python references (especially during the early transition weeks) and VisuAlgo about the designated topic and attempt the e-Lecture/Online Quiz questions first (flipped classroom),
  2. There is only one lecture session (two hours):
    1. 2-hour/week (effective 95m) in-class lecture on Wed, 6.30-8.30pm @ LT18 (start on time at 6.30pm and end by around 8.05pm), we will roughly do: 5m (buffer) + 5m (admins) + 35m (fast in class review of the more difficult parts of the designated VisuAlgo e-Lecture topics) + 7m (break) + 30m (application 1 - solving at least 1 Online Judge problem live) + 13m (buffer),
      Note that attendance is compulsory for those using SkillsFuture Singapore (SSG) funding. PS: SSG-funded students have to declare their lecture attendances via this method.
  3. On Tutorial+Lab (combo) day (on the following week), attempt and then actively participate on 1-hour/week (effective 50 minutes) tutorial slot of past week X-1 topic to improve student's understanding of course material, short 5m break, then for the second half, students will practice solve a "simple" problem (guided by TA, possibly turned into mock coding interview practices) during the next 1-hour/week (effective 40 minutes) lab session of past week X-1 topic to improve student's coding skills. This semester, we have 4 timing options:
    1. Saturdays (1 session, start from Sat of Week 02),
    2. Mondays (1 + 2 sessions, start from Mon of Week 03).
  4. Attempt a ~two-weeks Problem Set (PS) @ home, approximately 3 hours of work per week on average or (~6++ hours/set), starting from Wk01. The problems will be discussed in algorithmic (high-level) during each Tut+Lab session. You can use ChatGPT (or alternative GenAI) tool(s) if you have spent more than 2 hours attempting any PS task without external help (other human or AI, which means in the 2 hours final assessment, you cannot solve this yet), and as long as you eventually (re-)code the solution yourself (this part is for your own good), Plagiarism checker is built-in inside Kattis and extremely similar code can be easily identified,
  5. TOTALLY OPTIONAL: (Re-)solve some Kattis and/or LeetCode demo problems (or more) that are related to this course using Prof Halim's Methods to Solve page. WARNING: Doing this will significantly increases your study time per week for this course.

Then, repeat this throughout the semester :).

The S1 AY 2026/27 timetable below is still tentative, especially those that are highlighted with pink color. The Wed night of IT5003 will be as close as possible with Thu morning of CS2040S.

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,
27-31 Jul 		Has Not Started Has Not Started,
but please revise your IT5001/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 Python specific instructions @ Kattis,
pick up basic Python by yourself,
and solve the selected Kattis Online Judge (OJ)
Problem Set 0 (PS0) by yourself (IT5001/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 IT5001/equivalent rough grade)
 		PS0: Easy Coding Challenges
(01-12 Aug)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
00,
03-07 Aug 		Has Not Started

Essential LeetCode exercises mostly from programming-skills 1:
Mon: to-lower-case (simple string processing),
Tue: average-salary-excluding-the-minimum-and-maximum-salary (use library),
Wed: count-odd-numbers-in-an-interval-range (PIE),
Thu: find-the-highest-altitude (simple one pass),
Fri: plus-one (simulate +1 on a 'big' integer),
Sat: matrix-diagonal-sum (2D grid processing, but still with one loop),
 		Has Not Started
Continue attempting Kattis PS0 and LeetCode programming-skills study plan
(hints in class Discord)
 		PS0, continued
Remember, solve any 3 for 1%
01,
10-14 Aug 		Has Not Started

Essential LeetCode exercises mostly from programming-skills 2:
Mon: find-winner-on-a-tic-tac-toe-game (small (3x3) 2D grid processing),
Tue: spiral-matrix (interesting 2D grid traversal variant),
Wed: move-zeroes (use two pointers),
Thu: is-subsequence (use two pointers),
Fri: robot-return-to-origin ((virtual) 2D grid traversal with one loop),
Sat: robot-bounded-in-circle (a bit harder than robot-return-to-origin).
 		Singapore National Day on Sun, 09 Aug 26
The following Mon, 10 Aug 26 is a Public Holiday
but this class is not affected with that PH but of something else

Prof Halim is away for national service:
IOI 2026, Tashkent, Uzbekistan
The first two classes will be combined into one recording...
01a. Course Admin, (Re-)Introduction to course programming language
1. Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + Kattis (NUS) + LeetCode
2. Basic course programming language review/new feature introduction
3. Kattis/LeetCode problem(s) discussed today:
A few PS0 and/or programming-skills problems review (just for warm-up)
In the middle of 01a: VisuAlgo Online Quiz 0 (1% → 0%)
There is 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 sorting intro, algorithm analysis,
and O(N^2) sorting algorithms (Slide 1 to 9-3)
before the next lecture
 PS0 (1%)
Due: Wed, 12 Aug 26, 07.59pm
PS1: Basic Programming
Out: Wed, 12 Aug 26, 08.00pm
Mentioned at the end of the first lecture
IT5003 students do problem A+B
problem C is optional (extra challenge)
02,
17-21 Aug 		Saturday sessions
start from this Week 02
see T01+L01: tut01.pdf below

Essential LeetCode exercises involving (simple) problems with two (or more) solutions:
Mon: monotonic-array (a monotonic array is a sorted array),
Tue: container-with-most-water (O(n^2) vs O(n) solutions),
Wed: product-of-array-except-self (O(n^2) vs O(n) solutions),
Thu: maximum-score-of-a-split (O(n^2) vs O(n) solutions),
Fri: shortest-unsorted-continuous-subarray (O(n log n) vs O(n) solutions),
Sat: largest-perimeter-triangle (sort the lengths first)
 		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)
maximum-score-of-a-split
nothanks (sorting library and linear pass)
Last flipped classroom reminder:
Read all sorting e-Lecture slides before next lecture
 PS1 (2%)
Due: Sat, 22 Aug 26, 07.59am
PS2: Sorting-related Problems
Out: Sat, 22 Aug 26, 08.00am
03,
24-28 Aug 		T01+L01: tut01.pdf
Introduction,
OOP review (List ADT, ListArrayTest.py | java)
Algorithm Analysis,
Simulated coding interview 1 (TA as interviewee),
PS1 Debrief (short),
PS2 Discussion (algorithmic)

Essential LeetCode exercises involving sorting:
Mon: squares-of-a-sorted-array (CS2040S final S1 AY25/26, B.2, discussed in Lab01),
Tue: find-pivot-index (pivot here is not identical to Quicksort Partition),
Wed: merge-strings-alternately (variant of merge of Merge sort),
Thu: sort-colors (Dutch National Flag problem),
Fri: verifying-an-alien-dictionary (CS2040C midterm S2 AY25/26, B.1),
Sat: separate-black-and-white-balls (IT5003 midterm S2 AY25/26, B.1),
 		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: Python list, list.sort(), or sorted(list)
3. Kattis/LeetCode problem(s) discussed today:
sortofsorting (custom comparator, stable sorting library)
merge-strings-alternately
sort-colors
 		PS2, continued
04,
31 Aug-04 Sep 		T02+L02: tut02.pdf
Sorting Application(s),
Sorting, mini experiment,
QuickSelect,
ADT/List ADT,
VA OQ demo (sorting),
Simulated coding interview 2 (one student as interviewee),
PS2 Discussion (algorithmic)

Essential LeetCode exercises involving list:
Mon: arithmetic-subarrays (there is an easy solution with sorting, discussed in Lab02),
Tue: reverse-linked-list (there are several ways to do this),
Wed: design-linked-list (use SLLDemo),
Thu: delete-the-middle-node-of-a-linked-list (two passes or two pointers),
Fri: removing-stars-from-a-string (bracket matching variant),
Sat: maximum-twin-sum-of-a-linked-list (in SLL, we can only go forward?).
 		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/Deque (DLL) ADT
Linked List Online Quiz (easy)
White-box: SLLDemo.cpp | py | java implementation
Black-box: Stack, but using (resize-able) Array implementation, i.e., Python list as stack
Python list as queue, circular list, versus Python deque as queue
3. LeetCode problem(s) discussed today:
design-linked-list
 		PS2 (2%)
Due: Sat, 05 Sep 26, 07.59am
PS3: List+PQ Problems
Out: Sat, 05 Sep 26, 08.00am
05,
07-11 Sep 		T03+L03: tut03.pdf
Linked List, mini experiment,
Applications: Reversing/Sorting a List,
Application: Stack-related,
PS2 Debrief (short),
Python list/deque,
VA OQ demo (list),
Simulated coding interview 3 (TA as a failed interviewee),
PS3 Discussion (algorithmic)

Essential LeetCode exercises involving PQ:
Mon: add-two-numbers-ii (use two stacks; do LSB to MSB, discussed in Lab03),
Tue: last-stone-weight (IT5003 Final S2 AY24/25, B.2),
Wed: remove-stones-to-minimize-the-total (max PQ simulation),
Thu: kth-largest-element-in-an-array (O(n log k) version),
Fri: smallest-number-in-infinite-set (min PQ simulation; with lazy deletion),
Sat: minimum-operations-to-exceed-threshold-value-ii (IT5003 Midterm S2 AY25/26 B.3),
 		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
LeetCode problem(s) discussed today:
kth-largest-element-in-an-array
Last 15m of 05a: VisuAlgo Online Quiz 1 (5% → 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.
 		PS3, continued
06,
14-18 Sep 		T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
Python heapq,
VA OQ demo (heap),
Simulated coding interview 4 (TA as another failed interviewee),
PS3 last Discussion (algorithmic)

Essential LeetCode exercises involving hash table:
Mon: total-cost-to-hire-k-workers (min PQ simulation, discussed in Lab04),
Tue: unique-number-of-occurrences (map and set application),
Wed: design-hashmap (use HashTableDemo),
Thu: longest-consecutive-sequence (use set to help checks),
Fri: group-anagrams (sort and hash),
Sat: top-k-frequent-elements (PQ and hash combo)
 		06a. 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. LeetCode problem(s) discussed today:
design-hashmap
longest-consecutive-sequence
 		PS3 (2%)
Due: Sat, 19 Sep 26, 07.59am
PS4: Hash Table Problems
Out: Sat, 19 Sep 26, 08.00am
Recess Week, 19-27 Sep 2026
You can take a break this week :)
07,
28 Sep-02 Oct 		T05+L05: tut05.pdf [Special]
Past midterm paper(s) discussions

Essential LeetCode exercises (mix and match; UFDS):
Mon: max-sum-of-a-pair-with-equal-sum-of-digits (CS2040S midterm S1 AY25/26, A.1),
Tue: split-linked-list-in-parts (CS2040C midterm S2 AY25/26, B.3),
Wed: min-stack (CS2040S midterm S1 AY23/24, B),
Thu: number-of-provinces (simple with UFDS),
Fri: redundant-connection (simple with UFDS),
Sat: making-a-large-island (hard UFDS LC task).
 		Midterm Test (16% → 20%)
Venue: TBC
Date and Time: Wed, 30 Sep 26 (wk7), 6:35-8:05pm (90 mins), TBC
Open book
Details TBC

Midterm Test Past Papers (recent 3 AYs only):
For earlier AYs, refer to old CS2040/C/S papers (in language agnostic way)
AY 2025/26: S1-midterm.pdf, S2-midterm.pdf,
AY 2026/27: S1-midterm.pdf (to be our paper), for next S2.
 PS4, continued
08,
05-09 Oct 		T06+L06: tut06.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
Python set/dict/defaultdict/Counter,
PS3 Debrief (short),
Skipped in IT5003: UFDS review,
VA OQ demo (hashtable),
Simulated coding interview 5,
PS4 Discussion (algorithmic)

Extra exercises:
Mon: determine-if-two-strings-are-close (anagram checker variant, discussed in Lab06),
Tue: validate-binary-search-tree (simple recursive check),
Wed: search-in-a-binary-search-tree (implement recursive BST search),
Thu: delete-node-in-a-bst (implement the three cases of BST deletion),
Fri: minimum-absolute-difference-in-bst (use the correct tree traversal),
Sat: sum-root-to-leaf-numbers (preorder traversal; process leaves)
 		08a. Table ADT part 2: BST (all slides)
1. BST concepts, BST operations, and the multiset idea
BSTDemo.cpp | py | java
2. Randomly built BST versus a balanced BST, e.g., AVL Tree
QnA about AVL Tree concepts
AVL.cpp | TO ADD PY SOON | java
No built-in bBST in Python
See map_set.cpp | (no built-in py) | java at GitHub repo of CPbook website
3. LeetCode problem(s) discussed today:
search-in-a-binary-search-tree [not live]
delete-node-in-a-bst [not live]
Fri, 09 Oct 2026 is NUS Well-Being Day
This class is not affected
 		PS4 (2%)
Due: Sat, 10 Oct 26, 07.59am
PS5: Combo DS + Graph 1
Out: Sat, 10 Oct 26, 08.00am
09,
12-16 Oct 		T07+L07: tut07.pdf
Table ADT 2 - ordered,
(balanced) BST advanced stuffs: Select and Rank,
PQ ADT alternative implementation,
Comparison with Table ADT 1: unordered vs ordered,
No built-in py,
PS4 Debrief (short),
VA OQ demo (bst or avl (need to clear pre-req))
Simulated coding interview 6,
PS5 Discussion (algorithmic)

Extra exercises:
Mon: construct-binary-tree-from-preorder-and-inorder-traversal (classic, discussed in Lab07),
Tue: maximal-network-rank (just degree and edge existence checks),
Wed: count-good-nodes-in-binary-tree (modified preorder; precursor of DFS),
Thu: destination-city (in/out degree checks; use hash table),
Fri: keys-and-room (visitation check from 0; showing DFS way),
Sat: minimum-number-of-vertices-to-reach-all-nodes (compute in-degrees).
 		09a. 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. LeetCode problem(s) discussed today:
destination-city
Last 15m of 09a: VisuAlgo Online Quiz 2 (5% → 4%)
Material: /heap (3 Qs), /hashtable (3 Qs), /bst (3 Qs)
with 3 new questions
 		PS5, continued
10,
19-23 Oct 		T08+L08: tut08.pdf
Graph DS Review,
Some Graph Properties Discussion,
Graph DS Conversion Exercise,
DFS/BFS Review,
Custom graph DS implementation review,
VA OQ demo (graphds,dfsbfs),
Simulated coding interview 7,
PS5 Discussion (algorithmic)

Essential LeetCode exercises (graph 1):
Mon: maximum-star-sum-of-a-graph (CS2040S final S1 AY25/26, B.5, discussed in Lab08),
Tue: reorder-routes-to-make-all-paths-lead-to-the-city-zero (make undirected to simplify).
Wed: max-area-of-island (DFS flood fill on an implicit 2D grid graph),
Thu: course-schedule (using DFS ternary states to detect back edge (cycle)),
Fri: binary-tree-right-side-view (BFS on a binary tree: level order traversal),
Sat: number-of-islands (BFS flood fill on an implicit 2D grid graph).
 		10a. 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. LeetCode problem(s) discussed today:
max-area-of-island
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 (2%)
Due: Sat, 24 Oct 26, 07.59am
PS6: Graph 2
Out: Sat, 24 Oct 26, 08.00am
11,
26-30 Oct 		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),
Simulated coding interview 8,
PS6 Discussion (algorithmic)

Essential LeetCode exercises (graph 2):
Mon: course-schedule-ii (Kahn's algorithm, discussed in Lab09),
Tue: nearest-exit-from-entrance-in-maze (SSSP; implicit unweighted grid graph; BFS),
Wed: rotting-oranges (SSSP; implicit unweighted grid graph; BFS; MSSP),
Thu: network-delay-time (basic Dijkstra's),
Fri: snakes-and-ladders (SSSP; implicit (with a twist) unweighted grid graph; BFS),
Sat: minimum-genetic-mutation (SSSP; implicit unweighted graph; BFS).
 		11a. SSSP Problem (all slides)
1. Review of basic SSSP problem + O(VE) / O(kE) Bellman-Ford algorithm
2. QnA on BFS algorithm for unweighted SSSP
QnA on Dijkstra's algorithm (modified Dijkstra's first)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
Quick discussion of SSSP on Tree and on DAG
SSSP Online Quiz (medium)
3. LeetCode problem(s) discussed today:
rotting-oranges
network-delay-time
 		PS6, continued
12,
02-06 Nov 		T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (sssp),
Simulated coding interview 9,
PS6 Discussion (algorithmic)

Essential LeetCode exercises (graph 3):
Mon: word-ladder (similar with minimum-genetic-mutation, discussed in Lab10)
Tue: find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance (IT5003 final S2 AY24/25, B.6)
Wed: minimum-cost-path-with-edge-reversals (IT5003 final S2 AY25/26, A.5),
Thu: min-cost-to-connect-all-points (basic MST),
Fri: minimum-time-to-visit-disappearing-nodes (SSSP; weighted graph; with a small twist),
Sat: find-edges-in-shortest-paths (CS2040C final S2 AY25/26, A.6).
Tut+Lab participation marks given (5%) 		12a. SSSP Problem (all slides)
1. LeetCode problem(s) discussed today:
minimum-cost-path-with-edge-reversals
minimum-time-to-visit-disappearing-nodes
Finale: NP-completeness, and Course Wrap-Up
Showing the limit of computation:
Introduction to the theory of NP-completeness
Course wrap-up
Last 15m of 12a: VisuAlgo Online Quiz 3 (5% → 4%)
Material: /graphds (4 Qs), /dfsbfs (3 Qs), /sssp (2 Qs),
and 3 'new' questions (inclusive of 2 specifically unweighted SSSP).
 		PS6 (2%)
Due: Sat, 07 Nov 26, 07.59am
Optional Final Tracker
Out: Sat, 07 Nov 26, 08.00am
13,
09-13 Nov 		Deepavali PH on Sun, 08 Nov 2026
The following Mon, 09 Nov 2026 is PH in lieu
We cancel the last lab
No session on last week, only online exercises

Essential LeetCode exercises (past finals 1):
Mon: List Review,
Tue: ugly-number-ii (Min Priority Queue + Hash Table Review),
Wed: map-sum-pairs (Hash Table Review),
Thu: flatten-binary-tree-to-linked-list (Skewed Right BST (LL) Review),
Fri: Sat:
13a. No lecture, make-up time window
Details TBC
 		Optional, continued
Reading,
14-20 Nov 		Essential LeetCode exercises (past finals 2):
Mon:
Tue:
Wed:
Thu:
Fri: map-of-highest-peak ((unweighted) SSSP Review)
Sat:
Final Assessment Past Papers (recent 3 AYs only):
AY 2023/24: S1-final.pdf, S2-final.pdf,
AY 2024/25: S1-final.pdf, S2-final.pdf,
AY 2025/26: S1-final.pdf, S2-final.pdf,
AY 2026/27: S1-final.pdf (will be our paper), for next S2.
NUS Online Teaching Feedback System closes on Friday of Reading Week
Final Assessment (50%)
Date and Time: Sat, 21 Nov 2026, 9-11am
Venue: TBA
Open book
No electronic device except one calculator
Details TBC