IT5003 - Data Structures and Algorithms (Python)

Introduction

This module 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, hash tables, heap, 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.

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

This is the going to be the seventh time Prof Halim teaches this 8-weeks (+ 1.5 weeks more before final assessment) IT5003 course for MComp General Track — the main group of students — (plus a bit of other MComp specializations: Digital Financial Technology + Biomedical Informatics) and also a few (usually around 30-ish) Graduate Certificates in Computing Foundations (GC-CF). Prof Halim sets IT5003 (in Python) as a 'subset' (obviously, as we only have 8-weeks) of his full 13-weeks 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 S2 AY23/24, Prof Halim has prepared for a [126-150]-ish class size with all onsite components.
As of 19 Mar 2024, the third week of the class, the class roster is 125, slightly lower than predicted.

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.500 (very good).
  2. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo that will be used very extensively in this course.
    The main target for this semester is to maintain the already (very) good course ratings.

    Rating
    (out of 5.0)
    Mar-May 24
    (n=??/125)
    ≥ 50%?
    Oct-Dec 23
    (n=82/200)
    41%
    Mar-May 23
    (n=61/115)
    53%
    Oct-Dec 22
    (n=100/178)
    56%
    Mar-May 22
    (n=57/99)
    58%
    Oct-Dec 21
    (n=83/130)
    63%
    Course feedback (SoC avg lvl 5000 ~4.1) ≥ 4.3 (target) 4.3 4.5 (PB) 4.4 == 4.4 4.3
    Course difficulty (SoC avg lvl 5000 ~3.6) ≤ 3.8 (lower a bit) 3.9 == 3.9 == 3.9 == 3.8 3.5 (PB)
    Prof Halim's teaching (SoC avg lvl 5000 ~4.3) ≥ 4.5 (target) 4.3 4.6 == (PB) 4.6 == (PB) 4.6 (PB) 4.5
    Date, Time Live Session (Venue) (#Stu/#Cap) No Tutor
    a/Sat, 1010-1210 COM1-01-20 (PL6) (24/23) B1 Prof Halim
    a/Sat, 1000-1200 COM4-WSLab1 (19/23) B4 Ritul
    a/Sat, 1000-1200 COM4-WSLab2 (19/23) B5 Wen Jun
    a/Sat, 1000-1200 COM4-WSLab3 (18/23) B6 Dominic
    b/Mon, 1400-1600 COM1-B1-12 (PL1) — for full-time MComp students (25/23) B2 Jeanette
    c/Mon, 1600-1800 COM1-B1-12 (PL1) — for full-time MComp students (20/23) B3 Chia Geng

    List of TAs for Mar-May 2024:

    1. @prof_halim, Associate Professor Steven Halim (IT5003 course lecturer 7x)
    2. @Jeanette, Tan Yu Wei (IT5003 full-time TA from last four semesters)
    3. @chiageng, Chng Chia Geng (IT5003 from last semester, rating 4.9)
    4. Singh Ritul Kumar
    5. Woo Wen Jun
    6. Dominic Berzin Chua Way Gin
  3. Have you passed (or exempted from) IT5001 or CS1010 (or its variants)? You have to...

Syllabus

This is what you will learn in IT5003 as taught by Prof Halim:

  • Part 0: A quick review of IT5001 - Software Development Fundamentals
  • Part 1: (Complete Search, Divide and Conquer, or Greedy) Algorithms using the simplest Linear Data Structure: Array/Python list, e.g., Sorting (Divide and Conquer) and a few others (e.g., Greedy algorithms that are applicable after sorting the data).
  • Part 2: Various Linear Data Structures (DSes):
    1. List Abstract Data Structure (ADT)
    2. Stack, Queue, and Deque ADTs in their Linked List (and Python-library) implementations
    3. Stack and Queue in their (resize-able) Array/Python list implementations
  • Part 3: Various (Non-)Linear Data Structures (DSes):
    1. Priority Queue (PQ) ADT, its Binary Heap (and Python-library) implementation (DnC), and Greedy algorithm with PQ (Greedy)
    2. Table/Map (ADT) part 1 (unordered) and its Hash Table (straight to Separate Chaining version) (and Python-library) implementation (Divide and Conquer)
    3. Table/Map (ADT) part 2 (ordered) and its Binary Search Tree (BST) implementation (with a short exposure about the balanced BST version) (Divide and Conquer)
    4. Graph DS: Adjacency Matrix/Adjacency List/Edge List
  • Part 4: Algorithms for Two Graph Problems:
    1. Graph Traversal: Depth-First Search (DFS), Breadth-First Search (BFS) (Complete Search)
    2. Single-Source Shortest Paths (SSSP): BFS (for unweighted graph), (Modified) Dijkstra's algorithm (Greedy), Dynamic Programming for SSSP on DAG
  • Part 5: Beyond polynomial-time algorithms: Short introduction to the theory of NP-completeness
  • Throughought this course:
    1. More advanced data structures and algorithms design and analysis (compared to IT5001)
    2. Various trade-offs situations
    3. Real-life problem solving skills (Complete Search, Divide and Conquer, Greedy, Dynamic Programming)
    4. Recursive thinking
    5. Proper implementation (more emphasis this sem) of (some) data structures and algorithms in Python

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 IT5003 S2 AY 2023/24 be 100% onsite?
A: I think so, probably full-onsite too for SSG-funded students Yes, it is full-onsite for all students for this S2 AY 2023/24 edition (it was still hybrid for S1 AY2023/24 edition).
Q: I am from IT5001 (the most relevant course before this)/other courses that do not use Python, should I pick up Python on my own before March 2024?
A: Yes, that is a very good idea.
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 ~3875+ 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 2023/24 compared to your last semester (S1 AY 2023/24) version?
A: Not much, with average course rating of 4.5 so far (but drop a bit to 4.3 for S1 AY 23/24), there is not much left to change.... However, these are the potential changes:
  1. NUS Well-Being Day for S2 AY 2023/24 is chosen to be Thu, 28 Mar 2024 (to make it a long passion weekend for NUS staffs and students) — we are not allowed to have classes in the middle of the long weekend: Sat, 30 Mar 2024.
  2. Prof Halim further reduces the weightage of the weekly Problem Sets (it is too difficult to fight ChatGPT/generative AI...): from 20% down to 16%, then increase the weightage of the three (now four, the trivial OQ0 is counted) VisuAlgo Online Quizzes: from 9+9+9% = 27% to 1+10+10+10% = 31%. There will be slightly lesser questions in each official VA OQ so there is a bit more time per question instead of asking students to speedrun the Online Quiz...
  3. In S1 AY 23/24, the SSG-funded students must be given 'synchronous e-Learning' option... Running a hybrid class with just one lecturer is extremely hard :(... Prof Halim have asked for a review on this policy, i.e., he wants all 100% onsite for S2 AY 23/24 (as of 05 Jan 2024, this decision is still TBA). Update on 06 Mar 2024: Yes, all-onsite now.

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

News

Date News

Lesson Plan

The S2 AY 2023/24 timetable below is still tentative, especially those that are highlighted with pink color.

Week Lecture Tutorial+Lab Combo 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
-02
Not started, but please revise your CS1010/IT5001
Prof Halim assumes that all of you have taken
or exempted from this course/its variants,
i.e., you can code in Python 3

Register at Kattis (use full name as in Matric card),
read Kattis knowledge base if you are new with this judge,
and solve the selected optional Online Judge (OJ)
Problem Set 0 (PS0) by yourself (CS1010/IT5001 level):
(solving many 'trivial (many one-liner) problems' from this set
---trackable by Prof Halim, indirectly tells him
about your CS1010/IT5001 rough grade)
Not Started PS0: Easy Python/coding challenges
Out: Wed, 21 Feb 24, 08.00am
(already graded)
-01,
Bef Wed,
06 Mar
Not Started, continue doing PS0 if you have not solved at least 3...
This is a useful practice for those also taking IT5001 (ending soon)
Not Started PS0: Easy Python/coding challenges
(already graded)
07,
Session 1
06+09 Mar
1a. Course Admin, (Re-)Introduction to Python
Setting the tone for a flipped classroom but all ONSITE course
VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open)
Basic Python review/new feature introduction

VisuAlgo Online Quiz 0 (1% — to speed up admins)
There will be just 1 very trivial fill-in-the-blank question
We do this between 6.45-7.15pm during Lecture 1a
Bring your own laptop

r1. Recitation: Basic Python
Extra QnA session on Basic Python,
discussion of more/alternative Python features,
review PS0: Easy Python/coding challenges tasks
Kattis problems discussed today:
sifferprodukt (review simple function)
coffeecupcombo (review 1D array/list)
babypanda (backwards solve; binary number)
basicprogramming1 (somewhat IT5001 review)

Reminder: Read summary on algorithm analysis
before Lecture 1c

1b. Analysis of Algorithms (slide 6 to 6-11)
Live SpeedTest.py (vs cpp or java) demo
(measure runtime, count # of operations, vs asymptotic analysis)
Kattis problems discussed today:
thanos (Analysis: exponential growth, logarithmic steps)

Reminder: Read sorting e-Lecture slides before Lecture 2a
At least until slide 11-11, preferably more

Sat, 09 Mar 2024 PM is IT5001 final assessment time
for many IT5003 students. All the best.
T01+L01: it5003lab1.pdf
Introduction,
Algorithm Analysis,
SpeedTest.py mods,
PS0 review,
Hands-on: vaccineefficacy
(1D or 2D list/array processing)
PS1 Discussion (algorithmic)
PS1: Basic Python
Out: Wed, 06 Mar 24, 08.00am

PS0: Easy Python/coding challenges
Due: Wed, 06 Mar 24, 07.59pm
(solve any 3 → 1%
— to speed up
registration admins)

08,
Session 2
13+16 Mar
2a. Sorting (Slide 1 to 11-11)
Start with a simple problem involving sorting
(Re-)Introducing simpler but O(N^2) Sorting Algorithms + O(N log N) Merge Sort
SortingDemo.py (O(N^2) versions + O(N log N) Merge Sort)
Python list, list.sort(), or sorted(list)
Kattis problems discussed today:
nothanks (NEW: Python list.sort() or sorted(list) and linear pass),
mjehuric (review Bubble sort),
height (review Insertion sort),
sortofsorting (NEW: custom comparator, Python list.sort() is stable)

r2. Recitation: Analysis of Algorithms and Sorting
Extra QnA session on anything about Algorithm Analysis
Extra QnA session on anything about sorting, e.g.,
touching on Counting Sort,
or other potential applications of sorting
Kattis problems discussed today:
magicsequence (up to counting sort; not the full solution)

Last flipped classroom reminder:
Read most sorting e-Lecture slides
before Lecture 2c

2b. Sorting (Slide 11 to 13-2 and 17 to end;
but skipping Slide 14 to 16-2)
O(N log N) Merge Sort Fast Review
Introducing O(N^2) non-randomized Quick Sort
Introducing expected O(N log N) Randomized Quick Sort (no analysis)
SortingDemo.py (O(N log N) Merge Sort + expected O(N log N) Randomized Quick Sort)
Other topics of sorting e-Lecture
Sorting Online Quiz (medium)

Sat, 16 Mar 2024 is also SGP NOI 2024 Onsite Final
We had to release our Sat lab bookings
B4/B5/B6/B1 went to COM1-02-16/14/SR5/SR@LT19, respectively
PS: Prof Halim was very distracted during this morning...
(Jeanette has covered this session)
T02+L02: it5003lab2.pdf
Sorting Application(s),
Sorting Algorithms Review via mini experiment,
PS1 Quick Debrief,
VA OQ demo (sorting),
Hands-on: judging
(multiset intersection; greedy bipartite matching;
modified merge routine (other solution exists)),
PS2 Discussion (algorithmic)
PS1: Basic Python
Due: Wed, 13 Mar 24, 07.59am
(1%)

PS2: Sorting Problems
Out: Wed, 13 Mar 24, 08.00am
09,
Session 3
20+23 Mar
3a. List ADT: Array vs SLL, Stack & Queue ADT (Slide 1 to 5-7)
Introducing List ADT
Python list (actually not a linked list) for List ADT
Introducing (some of) SLL operations
Introducing Stack ADT
SLLDemo.py (custom SLL and Stack)
Python list as stack
Introducing Queue ADT
Python list as queue (dequeue/pop(0) is slow)
SLLDemo.py revisited (custom Queue, fast enqueue+dequeue)

r3. Recitation: List
Extra QnA session on anything about List, e.g.,
a few other ways to implement Linked List,
the art to actually avoid using Linked List,
(e.g., the clever way to use two Python lists as queue), etc.
Mock VA OQ 1 (medium level only),
Kattis problems discussed today:
TBA

3b. DLL and Deque ADT, Queue again (Slide 6 to end)
Detour to Doubly Linked List (DLL) and Deque ADT
Python deque for Queue ADT (fast)
Linked List Online Quiz (medium)
T03+L03: it5003lab3.pdf
SLL/Stack/Queue Review via mini experiment,
Additional classic list operations,
Python implementations for list, stack, and queue (deque),
PS2 Quick Debrief,
VA OQ demo (list),
Hands-on: TBA
PS3 Discussion (algorithmic)
PS2
Due: Wed, 20 Mar 24, 07.59am
(2%)

PS3: List Problems
Out: Wed, 20 Mar 24, 08.00am
10,
Session 4
27 Mar only
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to end)
Introducing PQ ADT (fast)
Introducing basic Binary Heap structure and operations (fast)
BinaryHeapDemo.cpp | py | java
Python heapq
See priority_queue.py at GitHub repo of CPbook website
Max-Min PQ conversion (numbers only)
O(N log N) Heapify/Create Heap + O(N log N) Heap sort (fast)
O(N) Heapify/Create Heap
O(N + K log N) partial sort vs other sorting algorithms
The extra PQ/Binary Heap operations: UpdateKey and DeleteKey

VisuAlgo Online Quiz 1 (10%)
First 2 topics of IT5003: sorting and list only,
with a few new questions
total 10 hard+2 new questions
8.15-8.30pm, onsite
Bring your own laptop

Thu, 28 Mar 2024 is chosen as
NUS well-being day S2 AY 2023/24
This is just before Fri, 29 Mar 2024 Good Friday PH
Thus, recitation r4 is cancelled
Also, we will not have a session
on Sat, 30 Mar 2024
(hence, the maximized Wed, 27 Mar 2024 session)
Prof Halim will be in Jakarta this weekend

Also, NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until our 8th/last week
T04+L04: it5003lab4.pdf
PQ ADT/Binary Heap Review,
PS3 Quick Debrief,
VA OQ demo (heap),
Hands-on: TBA
PS4 Discussion (algorithmic)

PS: This lab4 is only live for Monday groups
Saturday groups will watch the recording
For Saturday groups,
review one of Monday group recording
PS3
Due: Wed, 27 Mar 24, 07.59am
(2%)

PS4: PQ Problems
Out: Wed, 27 Mar 24, 08.00am
11,
Session 5
03+06 Apr
5a. Table ADT: Hash Table (Slide 1 to 7-11 and 10 to end,
but skipping Slide 8 to 9-4)
Table ADT
Direct Addressing Table (DAT)
Basic Hashing Concepts
Collission Resolution Techniques: Linear Probing vs Separate Chaining
HashTableDemo.cpp | py | java (all use SC)
Python set, dict, defaultdict, or Counter
See unordered_map_unordered_set.cpp | py | java at GitHub repo of CPbook website
Kattis problems discussed today:
TBA

r5. Recitation: More PQ + HT
A review of basic HT concepts (SC, LP),
A bit more HT, e.g., QP, DH, etc,
PQ plus HT combo,
Mock VA OQ 2 (medium level only, without bst yet),
Kattis problems discussed today:
TBA

5b. Table ADT part 2: Binary Search Tree (Slide 1 to 11)
Presenting alternative Table ADT: BST
BSTDemo.cpp | py | java
Short exposure about self-balancing trees
No built-in library for Python
BST Online Quiz (medium)
T05+L05: it5003lab5.pdf
One more Binary Heap question,
Table ADT Review,
Basic Hashing Concepts,
Hash Table Issues,
Quick BST Review,
PS4 Quick Debrief,
VA OQ demo (hashtable,bst),
Hands-on: TBA
PS5 Discussion (algorithmic)
PS4
Due: Wed, 03 Apr 24, 07.59am
(2%)

PS5: (Hash) Table Problems
Out: Wed, 03 Apr 24, 08.00am
12,
Session 6
13 Apr only
Wed, 10 Apr 2024 is Hari Raya Puasa PH
Thus, L6a is cancelled
But Prof Halim needs to use r6 (recorded)
and 6b to catch up

r6. Recitation: HT+BST+balanced BST
Review of BST, plus the non-examinable balanced BST
Extra QnA session on anything about graph,
Prof Halim will use the 2nd half of r6 to do 6a
Start of 6a. Graph DS lecture (recorded)
Introducing Graph Theory and special graphs
Introducing Graph Data Structures (fast)

6b. Graph DS Applications (read ALL slides)
Fast recap of what was mentioned during r6
No built-in C++ STL container | Python standard library | Java API,
See graph_ds.cpp | py | java at GitHub repo of CPbook website,

VisuAlgo Online Quiz 2 (10%)
Next 3 topics of IT5003: heap, hashtable, bst only,
[hashtable: QP/DH and bst: AVL tree questions are removed],
total 10 hard+2 new questions
9.35-9.50am, onsite
Bring your own laptop

Prof Halim has to attend the re-scheduled
ICPC World Finals 22+23 at Luxor, Egypt
(that has been postponed for 1.5+0.5 year(s), respectively)
So he will early record 7a this evening
Before he fly to Egypt on Sat, 13 Apr night

[RECORDING] 7a. Graph Traversal (Slide 1 to 7-11)
Introducing Graph Traversal Algorithm: DFS
No built-in C++ STL algorithm | Python standard library | Java API,
See dfs_cc.cpp | py | java,
Continuing with BFS
See UVa00469.cpp | py | java, and
bfs.cpp | bfs.py | java at GitHub repo of CPbook website,
DFS/BFS Online Quiz (medium),
Kattis problems discussed today:
TBA
T06+L06: it5003lab6.pdf
Graph DS Review,
Graph DS Conversion Exercise,
Graph Modeling exercise 1,
PS5 Quick Debrief,
VA OQ demo (graphds),
Hands-on: TBA
PS6 Discussion (algorithmic)
PS5
Due: Wed, 10 Apr 24, 07.59am
(2%)

PS6: Graph DS+Traversal 1
Out: Wed, 10 Apr 24, 08.00am
13,
Session 7
17+20 Apr
[RECORDING] 7a. Graph Traversal (Slide 1 to 7-11)
See the recording
No live class at LT8

Our COM1-02-SR1 venue
will be used for final assessment
So, r7+r8 are online

[Likely Online+Live from Luxor] r7. Recitation: Graph 1
Graph ds (implicit graph),
Graph traversal (especially cyclic test and toposort)
Kattis problems discussed today:
TBA

[RECORDING] 7b. Single-Source Shortest Paths (SSSP) Problem
(Slide 1 to 2; then BFS: slide 5 to 6-3)
Introducing SSSP Problem
BFS Review for unweighted cases (you have seen this on Lecture 6b/7a)
Preview of Modified Dijkstra's (to be discussed in more details next Wed),
Kattis problems discussed today:
TBA

Prof Halim will still be on plane back to SGP
(Jeanette will cover his B1 lab again)
T07+L07: it5003lab7.pdf
DFS Review,
BFS/unweighted SSSP Review,
Graph Modeling exercise 2,
PS6 Quick Debrief,
VA OQ demo (dfsbfs),
Hands-on: TBA
PS7 Discussion (algorithmic)
PS6
Due: Wed, 17 Apr 24, 07.59am
(2%)

PS7: Graph DS+Traversal 2
Out: Wed, 17 Apr 24, 08.00am
Reading,
Session 8
24+27 Apr
8a. Single-Source Shortest Paths (SSSP) Problem
(Modified Dijkstra's: slide 8 to 8-5)
Alternative Venue: LT18 (manual Zoom recording)
Introducing (Modified) Dijkstra's Algorithm
Introducing SSSP on DAG (involving toposort/bottom-up DP)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
SSSP Online Quiz (medium),
Kattis problems discussed today:
TBA
Last few words

r8. Recitation: SSSP
Venue: Online
Extra QnA session on anything about IT5003 topics
using past paper(s) as the backdrop

NUS Online Teaching Feedback closes on Friday of Study Week

8b. [Optional] NP-complete (but compulsory VA OQ 3)
Alternative Venue: LT18 (no recording)
Showing the limit of computation:
Introduction to the theory of NP-completeness

VisuAlgo Online Quiz 3 (10%)
Next 3 topics of IT5003: graphds, dfsbfs, sssp only,
[sssp: Bellman-Ford and negative weight questions are removed],
total 10 hard+2 new questions
9.30-9.45am, onsite
Bring your own laptop
T08+L08: it5003lab8.pdf
SSSP Review 2 (weighted),
Graph Modeling exercise 3 (from past papers),
Hands-on: Just do PS8 in-class until end.
or
Hands-on: TBA
(for those who have completed PS8)

Lab participation marks given (3%)
PS7
Due: Wed, 22 Nov 23, 07.59am
(2%)

PS8: Weighted SSSP Problems
Out: Wed, 22 Nov 23, 08.00am
"Study Window", 30 Apr-08 May 2024

Final Assessment Discussions at Class Discord

Final Assessment Past Papers (recent 3 AYs only):
AY 2021/22: S1-final.pdf, S2-final.pdf,
AY 2022/23: S1-final.pdf, S2-final.pdf,
AY 2023/24: S1-final.pdf, S2-final.pdf (will be our paper; should another step easier than last semester).
PS8
Due: Wed, 01 May 24, 07.59am
(2%)
Make-up slot for VA OQ 1 (x pax), OQ 2 (y pax), and OQ 3 (z pax)
Date and Time: Thu, 09 May 2024, 3.30-4.00pm
Venue: TBA

Final Assessment (50%)
Date and Time: Thu, 09 May 2024, 5-7pm
Venue: TBA
Open book but *not* Open Laptop (prepare accordingly)
Other details TBA