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 tenth 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 [20..30]-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 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 2025/26 (August-November 2025), Prof Halim expects a smaller class again, about [30-50] students who have passed IT5001 in S2 AY 2024/25 (or earlier).
This information will be refined as and when the information from IT5001 team and/or Graduate Office is available.

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.4 (above average) to 4.6 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.5 (very good).
  2. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo that is used very extensively in this course.
    The primary goal for this S1 AY 2025/26 is for Prof Halim to perfect the alignment of this course with its superset course CS2040S (that was started from S1 AY 2024/25).
    The secondary goal is to integrate as many key/recurring LeetCode tasks in this course, as LeetCode is currently one of the most popular coding interview website out there.

    Rating
    (out of 5.0)    		 Aug-Dec 25
    (n=??/[30..50]??)
    ≥50%    		 Jan-May 25
    (n≥29/146)
    ≥20%?    		 Aug-Nov 24
    (n=19/33)
    58% ▲    		 Mar-May 24
    (n=66/122)
    54% ▲    		 Oct-Dec 23
    (n=82/200)
    41% ▼    		 Mar-May 23
    (n=61/115)
    53% ▼
    Course feedback (SoC avg lvl 5000 ~4.1) [4.3..4.4] (tgt) [4.3..4.4] (tgt) 4.3 == 4.3 == 4.3 ▼ 4.5 ▲ (PB)
    Course difficulty (SoC avg lvl 5000 ~3.6) [4.0..4.1] (tgt) [4.0..4.1] (tgt) 4.2 == (uh oh) 4.2 ▲ (uh oh) 3.9 == 3.9 ==
    Prof Halim's teaching (SoC avg lvl 5000 ~4.3) [4.4..4.5] (tgt) [4.4..4.5] (tgt) 4.6 ▲ 4.4 ▲ 4.3 ▼ 4.6 == (PB)
    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    a/Sat, 1000-1200 One lab — for part-time students (??/20) B1 TBC
    b/Mon, 1400-1600 Another lab — for full-time students (??/20) B2 @loveandbejoyful

    List of TAs for Aug-Dec 2025:

    1. @loveandbejoyful, Tan Yu Wei (IT5003 full-time TA from the last few semesters)
    2. Another full-time TA, TBC
  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 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: I want to, but we do not have enough class contact time for that, so no.
Q: Will there be a mid-semester Midterm Test for your version of IT5003?
A: I also want to, but we do not have enough class contact time for that, so no.
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 August 2025?
A: Yes, that is a very good idea, use May-June-July 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 ~4500+ 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 2025/26 compared to your most recent semester (S2 AY 2024/25) version?
A: Not much, with average teaching feedback rating of ~4.5 so far, there is not much left to change.... Prof Halim only plan to change these variables this time (all others are planned to be kept roughly constant):
  1. Prof Halim will discuss DSA problems in the format that are more commonly found in recent technical interviews (i.e., via LeetCode), reducing his prior reliance on 'Competitive Programming'-style problems (with much more complicated storyline, via Kattis).
  2. Prof Halim is currently scheduled to attend only one international competition on Week 04 (the 2025 ICPC World Finals, Baku, Azerbaijan).

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 S2 AY 2024/25

The S1 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 Wed 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,
28 Jul-01 Aug 		Has Not Started Has Not Started,
but please revise your CS1101S/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 (CS1101S/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 CS1101S/IT5001/equivalent rough grade)
 		PS0: Easy Coding Challenges
(01-13 Aug)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
00,
04-08 Aug 		Has Not Started Has Not Started
Continue attempting Kattis PS0 and LeetCode programming-skills study plan
(hints in class Discord)
Singapore National Day on Sat, 09 August 2025
 		PS0, continued
Remember, solve any 3 for 1%
01,
11-15 Aug 		Has Not Started 01a. Course Admin, (Re-)Introduction to Python
Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + Kattis (NUS) + LeetCode
Basic Python review/new feature introduction
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 simple algorithms on unsorted array
(Slide 1 to 6-1) before the next 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, 13 Aug 25, 07.59pm
PS1: Basic Programming
Out: Wed, 13 Aug 25, 08.00pm
Mentioned at the end of the first lecture
IT5003 students do problem A+B
problem C is optional (extra challenge)
02,
18-22 Aug 		Saturday sessions
start from this Week 02
see T01+L01: tut01.pdf below
 		02a. Analysis of Algorithms (Slide 1 to 9-3)
Live SpeedTest.cpp | py | java demo
(measure runtime, count # of operations, vs asymptotic analysis)
Fast review of O(N^2) sorting algorithms
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, 23 Aug 25, 07.59am
PS2: Sorting-related Problems
Out: Sat, 23 Aug 25, 08.00am
03,
25-29 Aug 		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)
 		03a. Sorting (Slide 10 to 13-2)
O(N log N) Merge Sort algorithm (Java Collections.sort; Python list.sort)
Expected O(N log N) (Rand) Quick Sort algorithm (C++ sort; Java Arrays.sort (primitives))
See the details at SortingDemo.cpp | py | java
Python list, list.sort(), or sorted(list)
Sorting Online Quiz (medium)
Kattis/LeetCode problem(s) discussed today:
merge-strings-alternately (variant of merge of Merge sort)
 		PS2, continued
04,
01-05 Sep 		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)
 		04a. List ADT: SLL/Stack/Queue/DLL/Deque (all slides)
Introducing List ADT, (resizeable) array versus SLLDemo.cpp | py | java implementation
Introducing Stack ADT and MyStack implementation (extension of SLLDemo)
Stack, but using (resize-able) Array implementation, i.e., Python list as stack
Introducing Queue ADT and MyQueue implementation (another extension of SLLDemo)
DLL and Deque ADT
(Fixed-size) Python list as queue, circular list, versus Python deque as queue
Linked List Online Quiz (medium)
A few other LL technicalities
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)
Prof Halim will be at Baku, Azerbaijan,
for the 2025 ICPC World Finals.
Lec04a will likely be delivered by Jeanette (TBC).
 		PS2 (2%)
Due: Sat, 06 Sep 25, 07.59am
PS3: List+PQ Problems
Out: Sat, 06 Sep 25, 08.00am
05,
08-12 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),
Hands-on, a list application,
PS3 Discussion (algorithmic)
 		05a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-2)
Introducing PQ ADT
Introducing basic Binary Heap structure and its Insert+ExtractMax operations
Discussing CreateHeap (two versions) and HeapSort operations
BinaryHeapDemo.cpp | py | java
Python heapq; see priority_queue.cpp | py | java at GitHub repo of CPbook website
Kattis/LeetCode problem(s) discussed today:
kth-largest-element-in-an-array (long and short ways)
Last 20m of 05a: VisuAlgo Online Quiz 1 (7%)
Bring your own laptop that can run at least 20 minutes on battery power.
(we do not provide any spare laptop).
Material: /array (1Q + 3 'new'), /sorting (4 Qs), /list (4 Qs),
and 4 'new' questions especially on asymptotics.
 		PS3, continued
06,
15-19 Sep 		T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
Python heapq,
VA OQ demo (heap),
Hands-on, a simple problem involving PQ,
PS3 last Discussion (algorithmic)
 		06a. Table ADT part 1: Hash Table (slide 1 to 10-5)
Table ADT and DAT
Basic Hashing Concepts
Easiest Collision Resolution Technique: CA (SC)
Another Collision Resolution Technique: OA (LP)
More Collision Resolution Techniques: OA (QP and DH)
Comparing CA: SC with OA: DH
Other technicalities of Hash Table
Hash Table Online Quiz (easy; a bit too tedious on medium/hard settings)
Kattis/LeetCode problem(s) discussed today:
determine-if-two-strings-are-close (heavy library solution)
 		PS3 (2%)
Due: Sat, 20 Sep 25, 07.59am
PS4: Hash Table Problems
Out: Sat, 20 Sep 25, 08.00am
Recess Week, 20-28 Sep 2025
You can take a break this week :)
07,
29 Sep-04 Oct 		T05 is cancelled for IT5003
As we do not have midterm test 		First half quick review, especially 04a
Followed by CS2040S Midterm Quiz live discussion
Kattis/LeetCode problem(s) discussed today:
container-with-most-water (introducing two pointers idea)
max-consecutive-ones-iii (like two pointers; but the 'sliding window' is visualized)
 		PS4, continued
08,
06-10 Oct 		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)
 		07a. Table ADT part 2: BST (Slide 1 to 12-1)
BST concepts and the various BST operations
The multiset idea
BST (only) Online Quiz (medium)
BSTDemo.cpp | py | java
Randomly built BST and a preview of balanced BST, e.g., AVL Tree
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: Sat, 11 Oct 25, 07.59am
PS5: Graph DS + Traversal Problems
Out: Sat, 11 Oct 25, 08.00am
09,
13-17 Oct 		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 combo DS task,
PS5 Discussion (problemset preview only)
 		08a. Graph DS (all slides) + DFS Traversal (Slide 1 to 5-8)
Implementations of graph DS and its applications
Graph DS Online Quiz (medium),
No built-in C++ STL container | Python standard library | Java API,
See graph_ds.cpp | py | java at GitHub repo of CPbook website,
Early discussion of the basic forms of Graph Traversal algorithms: DFS first
See dfs_cc.cpp | py | java
Kattis/LeetCode problem(s) discussed today:
destination-city (degree checks)
Last 20m of 08a: VisuAlgo Online Quiz 2 (7%)
Material: /heap (4 Qs), /hashtable (4 Qs), /bst (4 Qs)
and 4 'new' questions.
 		PS5, continued
10,
20-24 Oct 		As Mon, 20 Oct 2025 is Deepavali PH
and Tue, 21 Oct 2025 is NUS well-being day
We move our last three downwards
 		09a. Graph Traversal Applications (Slide 6 to 9)
Review DFS and introducing BFS
Focus on a few more basic DFS/BFS applications
For S2 AY 2024/25, we discuss slide 8!!
(we skip slide 10-12, 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,
Kattis/LeetCode problem(s) discussed today:
number-of-provinces (AM; count #CC; DFS vs BFS way)
course-schedule-ii (cycle detection and provide one topological order if acyclic)
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,
27-31 Oct 		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 simple Graph DS task,
PS5 Discussion (algorithmic)
 		10a. SSSP Problem (all slides)
Review of basic SSSP problem
Preview of O(VE) / O(kE) Bellman-Ford algorithm
QnA on BFS algorithm for unweighted SSSP
QnA on Dijkstra's algorithm (original Dijkstra's first;
but focus on modified Dijkstra's for IT5003)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
Quick discussion of SSSP on Tree and on DAG
SSSP Online Quiz (medium)
Kattis/LeetCode problem(s) discussed today:
rotting-oranges (SSSP; unweighted undirected implicit grid graph; BFS)
network-delay-time (basic Dijkstra's; focus on easy lazy-minPQ implementation)
 		PS5 (2%)
Due: Sat, 01 Nov 25, 07.59am
PS6: Graph(-Related) Problems
Out: Sat, 01 Nov 25, 08.00am
12,
03-07 Nov 		T09+L09: tut09.pdf
BFS Review
DFS/BFS advanced stuffs:
Cycle Detection, Toposort++, Floodfill/CC, Bipartite Graph Checker
Modeling exercise,
PS5 Debrief (short),
VA OQ demo (dfsbfs),
Hands-on, a Graph Traversal task,
PS6 Discussion (algorithmic)
 		12a. SSSP, NP-completeness, and Course Wrap-Up
QnA on a few other special cases of SSSP problem
Showing the limit of computation:
Introduction to the theory of NP-completeness
Course wrap-up
Last 20m of 12a: VisuAlgo Online Quiz 3 (7%)
Material: /graphds (4 Qs), /dfsbfs (4 Qs), /sssp (4 Qs),
and 4 'new' questions.
 		PS6, continued
13,
10-14 Nov 		T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (sssp),
Hands-on, an SSSP task,
PS6 Discussion (algorithmic)
Tut+Lab participation marks given (5%) 		No more lecture

Make-up slot for VA OQ 1 (? pax ), OQ 2 (? pax), and OQ 3 (? pax)
Date and Time: Wed, 12 Nov 2025,
Timing: TBA
Venue: TBA
 		PS6 (2%)
Due: Sat, 15 Nov 25, 07.59am
Study Week, 19-25 Apr 2054

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 (to be archived soon).
AY 2025/26: S1-final.pdf (to be our paper).
Final Assessment (60%)
Date and Time: ???, ?? Nov? 2025, 5-7pm (back to exam period)
Venue: TBA
Open book
No electronic device except non-programmable calculator (as with Online Quiz)
11 MCQs (11x2 = 22%, very tricky), and
6 essay questions, the harder ones (6x13 = 78%)