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 eleventh 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 S2 AY 2025/26 (January-May 2026), Prof Halim expects about [120-160] students who have passed IT5001 in S1 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.468 (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 S2 AY 2025/26 is to polish the integration of many key/recurring/most liked/popular LeetCode tasks in this course, as LeetCode is currently one of the most popular coding interview website out there for now (in AY 2025/26).
    The secondary goal is to calibrate the weightage and difficulty of various course components of IT5003.

    Rating
    (out of 5.0)    		 Jan-May 26
    (n=???/1??)
    ??%    		 Aug-Dec 25
    (n=56/96)
    58% ▲    		 Jan-May 25
    (n=76/146)
    52%    		 Aug-Nov 24
    (n=19/33)
    58% ▲    		 Mar-May 24
    (n=66/122)
    54% ▲    		 Oct-Dec 23
    (n=82/200)
    41% ▼
    Course feedback (SoC CS avg lvl 5000 ~4.2) [4.2..4.3] (tgt) [4.2..4.3] (tgt) 4.1 (PW) ▼ 4.3 == 4.3 == 4.3 ▼
    Course difficulty (SoC CS avg lvl 5000 ~3.7) [4.0..4.1] (tgt) [4.0..4.1] (tgt) 4.0 ▼ 4.2 == (uh oh) 4.2 ▲ (uh oh) 3.9 ==
    Prof Halim's teaching (SoC CS avg lvl 5000 ~4.5) [4.3..4.4] (tgt) [4.3..4.4] (tgt) 4.2 ▼ (drop) 4.6 ▲ 4.4 ▲ 4.3 ▼
    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    a/Sat, 1000-1200 COM1-0120 (PL6) — for part-time (??/20) B1A @prof_halim
    a/Sat, 1000-1200 COM4-02-03 (WS Lab 1) — for part-time (??/20) B1B TBA
    a/Sat, 1000-1200 COM4-02-05 (WS Lab 2) — for part-time (??/20) B1C TBA
    a/Sat, 1000-1200 COM4-02-04 (WS Lab 3) — for part-time (??/20) B1D TBA
    b/Mon, 1400-1600 COM1-B112 (PL1) — for full-time students (??/20) B2A TBA
    b/Mon, 1400-1600 COM1-B109 (PL2) — for full-time students (??/20) B2B TBA
    b/Mon, 1600-1800 COM1-B112 (PL1) — for full-time students (??/20) B3A TBA
    b/Mon, 1600-1800 COM1-0120 (PL6) — for full-time students (??/20) B3B TBA

    List of TAs for Jan-May 2026:

    1. @prof_halim, Associate Professor Steven HALIM (IT5003 course lecturer 11x)
    2. @loveandbejoyful, Tan Yu Wei (JEANETTE) (IT5003 full-time TA from the last few semesters, will take TWO lab groups)
    3. Prof Halim will check TA application at TMTF very soon
  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 S2 AY 2025/26, the weightage will be increased (but the difficulty will be decreased) to balance the difficulty of this course.
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 over ~5100+ 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 S2 AY 2025/26 compared to your most recent semester (S1 AY 2025/26) version?
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, on the weekend of Wk07 to start of Wk08 (06-09 March 2026) to attend the 2026 ICPC Asia Pacific Championship. The lecture side should not be affected, but B1A lab on Sat, 07 March 2026 needs a replacement TA.
  2. Prof Halim will increase the weightage of the newly introduced midterm test (from 10% to a slightly higher weightage), but will decrease its difficulty.
  3. Prof Halim had spent most of his year 2025 doing LeetCode from 0 AC to 1813+ AC today. At the start of semester (Mon, 12 Jan 26), he expects to have solved ~2000+ out of ~3773+ tasks (~53%, i.e., ask him any random LeetCode problem, it is more likely that Prof Halim had solved it than not). For the next ~15 weeks until exam period, he plans to continue solving at a rate of ~2 tasks per day, i.e., to reach ~2100+ tasks solved (~58%).

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

The 4 units IT5003 syllabus will be delivered over 12 weeks, and we will be back to the official exam period for final assessment.
This course is approximately 24/39 ~= 62% of the content of CS2040C 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 (follow up from IT5001) and VisuAlgo about the designated topic and attempt the e-Lecture/Online Quiz questions first (flipped classroom),
  2. On Tutorial+Lab day, attempt and then actively participate on 1-hour/week (effective 45 minutes) tutorial slot of past week X-1 topic to improve student's understanding of IT5003 material, short break, then for the second half, students will practice solve a "simple" problem (guided by TA) during the next 1-hour/week (effective 45 minutes) lab session of past week X-1 topic to improve student's coding skills. Currently, we have the following options starting from Sat of Wk02 (for Saturday groups) and from Mon of Wk03 (for Monday groups):
    1. Saturdays (4? sessions, start from Sat of Week 02),
    2. Mondays (2? + 2? sessions, start from Mon of Week 03),
  3. There is only one lecture session (two hours):
    1. 2-hour/week (effective 105m) in-class lecture 1 on Wed, 6.30-8.30pm @ LT9 (start on time at 6.30pm and end by around [8.05-8.10]pm - no other class after us), we will roughly do: 5m (admins) + 45m (fast in class review of the more difficult parts of the designated VisuAlgo e-Lecture topics) + 7m (break) + 40m (application 1 - solving at least 1 Online Judge problem live) + 3m (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),
  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) tool 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 or LeetCode demo problems (or more) that are related to IT5003 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 S2 AY 2025/26 timetable below is still tentative, especially those that are highlighted with pink color.
The Wed evening of IT5003 will be as close as possible with Tue morning of CS2040C.

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 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)
New Year's Day on Thu, 01 January 2026
 		PS0: Easy Coding Challenges
(01-14 Jan)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
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, continued
Remember, solve any 3 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 Python
1. Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + Kattis (NUS) + LeetCode
2. Basic Python 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 (1%)
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 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
IT5003 students do problem A+B
problem C is optional (extra challenge)
02,
19-23 Jan 		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).
Saturday sessions
start from this Week 02
see T01+L01: tut01.pdf below
 		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)
At the end of 02a: VisuAlgo Online Quiz 0 (make-up) (1%)
There will be another 1 trivial question (not the same as last week)
Bring your own laptop
Only for those who really absent for the first lecture (for legit reasons)
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 CS2040S 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: Python list, list.sort(), or sorted(list)
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)
 		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 CS2040S Lec04b),
Thu: removing-stars-from-a-string (discussed in CS2040S 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: Stack, but using (resize-able) Array implementation, i.e., Python list as stack
Python list as queue, circular list, versus Python deque as queue
Kattis/LeetCode problem(s) discussed today: N/A
 		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),
Python 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 CS2040S 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 (7% → 5%)
Bring your own laptop that can run at least 20 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,
16-20 Feb 		CNY Eve (Reunion Dinner): 16 Feb 2026 PM (Mon)
so, NO Monday Lab, 16 Feb 2026
(and previous Sat, 14 Feb 2026)
But Sat, 21 Feb 2026 is for tut04.pdf
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)
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,
Python heapq,
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% → 16%)
Open book
A few MCQs, three essay questions (with partial marks scheme) and one special box
Material: Up to PQ (L05a on Week 05 + T04+L04 on Week 07)

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 is for next sem.
 		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 		tut05-midterm debrief (TBC)
First half review
(Python, 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)
 PS4, continued
09,
16-20 Mar 		T06+L06: tut06.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
Python set, dict, defaultdict, Counter
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)
 		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,
The issue of no equivalent Python standard library,
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 (7% → 5%)
Material: /heap (3 Qs), /hashtable (3 Qs), /bst (3 Qs)
and 3 'new' questions.
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

But we still run tut08.pdf on Sat, 04 Apr 2026
(no other time) 		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)
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
2. QnA on BFS algorithm for unweighted SSSP
QnA on Dijkstra's algorithm (only modified Dijkstra's this time)
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. Kattis/LeetCode problem(s) discussed today:
rotting-oranges (SSSP; implicit unweighted grid graph; BFS)
network-delay-time (basic Dijkstra's)
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 (7% → 5%)
Material: /graphds (4 Qs), /dfsbfs (4 Qs), /sssp (2 Qs) - no other time,
and 2 'new' questions.
 		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%) 		13a. No lecture, make-up time window
Details TBA
 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):
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 (to be our paper).
Final Assessment (50%)
Date and Time: ???, ?? Apr/May 2026, 5-7pm?
Venue: TBA (invigilators: Prof Halim, 1 TA: Jeanette TBC) + ??? (a few special needs + TA: ???)

Open book
No electronic device except one non-programmable calculator
Details TBC