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 sixth 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 + Biomed) 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.

This time, Prof Halim is preparing for a [161-200]-ish class size with all onsite components (more details in the lesson plan below). Update as of 15 Aug: There are 214 students...

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.540 (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)    		 Oct-Dec 23
    (n=1??/224)
    ≥ 50%    		 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% ▲    		 Oct-Dec 20
    (n=5/33)
    15% (too small)
    Course feedback (SoC avg ~3.8) ≥ 4.3 (target) 4.5 ▲ (PB) 4.4 == 4.4 ▲ 4.3 ▲ 4.2
    Course difficulty (SoC avg ~3.8) ≤ 3.9 (maintain) 3.9 == 3.9 == 3.8 ▼ 3.5 ▼ (PB) 4.0
    Prof Halim's teaching (SoC avg ~4.1) ≥ 4.3 (target) 4.6 == (PB) 4.6 == (PB) 4.6 ▲ (PB) 4.5 ▲ 4.4

    Update on 27 Sep 2023:
    Almost all students have a lab group by now.

    Date, Time Live Session (Venue) (#Stu/#Cap) No Tutor
    a/Sat, 1000-1200 COM1-B1-12 (PL1) (29/35) B5 Prof Halim
    a/Sat, 1000-1200 COM1-B1-10 (PL5) (23/23) B6 Hao Yi
    a/Sat, 1000-1200 COM1-01-20 (PL6) (31/31) B7 Chia Geng
    a/Sat, 1000-1200 COM1-01-13 (ESLab2) (23/24) B8 Devansh
    b/Mon, 1400-1600 COM1-B1-09 (PL2) — for full-time MComp students (30/35) B1 Jeanette
    b/Mon, 1400-1600 COM1-B1-10 (PL5) — for full-time MComp students (22/23) B2 Lian Ziyue
    c/Mon, 1600-1800 COM1-B1-09 (PL2) — for full-time MComp students (29/35) B3 Ren Weilin
    c/Mon, 1600-1800 COM1-B1-10 (PL5) — for full-time MComp students (20/23) B4 Ryan Tan
  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 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 (TBA)
  • Part 3: Various (Non-)Linear Data Structures (DSes):
    1. Priority Queue ADT and its Binary Heap (and Python-library) implementation (Divide and Conquer)
    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 (skipping the other versions)
  • 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 S1 AY 2023/24 be 100% onsite?
A: I think so. Unless there are special cases (see the Lesson Plan), the classes will be onsite.
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 October 2023?
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 ~3600+ 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 2023/24 compared to your last semester (S2 AY 2022/23) version?
A: Not much, with course rating of 4.5 last S2 AY 22/23, there is not much left to change.... However, these are the potential changes:
  1. NUS Well-Being Day for S1 AY 2023/24 is chosen to be Fri, 10 Nov 2023 (to make it a long weekend for NUS staffs and students) --- we are not allowed to have classes in the middle of the long weekend: Sat, 11 Nov 2023. Moreover, but Prof Halim is also totally away afterwards on Week 13 (to attend ICPC World Finals 2022+23 in Egypt). So, the topic of Graph Traversal (7th week) will be totally recorded.
  2. Prof Halim reduces the weightage of the weekly Problem Sets (it is too difficult to fight ChatGPT/generative AI...): from 24% down to 20%, then increase the weightage of the two (now three) VisuAlgo Online Quizzes: from 11+12% = 23% to 9+9+9% = 27%. 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. All others are planned to be kept roughly constant.

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 S1 AY 2023/24 timetable below is still tentative, especially those that are highlighted with pink color.

IT5003 classes comprises of Lecture, Tutorial+Lab Combo, and Weekly Problem Sets.

For Lectures (discussion of VA e-Lecture Slides, Q&A sessions, and live problem-solving segment), we have:

  1. Onsite: every Wed 6.30-8.30pm (2h) — venue: iCube-Auditorium (PS: SSG-funded students may have to register their physical attendance via additional Zoom session login, TBC...)
  2. (Optional Onsite) Recitation: every Fri 2-4pm (2h) — venue: COM1-0206 (SR1) (TBC)
  3. Onsite: every Sat 9-10am (1h) — venue: iCube-Auditorium

Lectures start from Wk07 (attendance is compulsory for those using SSG/SkillsFuture Credit).

Sat Sessions start from Wk07 (and ending on Sat, 25 Nov 2023 — the only clash with NUS first exam day) whereas Mon Sessions start from Wk08 (and ending on Mon, 27 Nov 2023 — the only clash with NUS first exam week).

For Weekly Problem Sets, you can do it at home.
One set of two 'simple' problems per week from Wk07.
It is expected that students spend around ~5 hours to complete one set each week.
The problems will be discussed in algorithmic (high-level) during each Lab session.
You can use ChatGPT (or alternative) tool as long as you eventually code the solution yourself (this part is for your own good).

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 Python 3 specific instructions @ Kattis,
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, 20 Sep 23, 08.00am
-01,
Bef Wed,
04 Oct 		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
(not graded yet)
extended to two weeks
07,
Session 1
04+07 Oct 		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
r1. Recitation: Basic Python
Extra QnA session on Basic Python,
discussion of more/alternative Python features,
review PS0: Easy Python/coding challenges tasks

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:
TBA

Reminder: Read sorting e-Lecture slides before Lecture 2a
At least until slide 11-11, preferably more
Sat, 07 Oct 2023 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: TBA,
PS1 Discussion (algorithmic)
 		PS0: Easy Python/coding challenges
Due: Wed, 04 Oct 23, 07.59pm
 (solve any 3 → 1%
— to speed up
registration admins)

PS1: Basic Python
Out: Wed, 04 Oct 23, 08.00pm
Easier subtasks showcased live during the first lecture
08,
Session 2
11+14 Oct 		2a. Sorting (Slide 1 to 11-11)
(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:
TBA
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:
TBA

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)
 		T02+L02: it5003lab2.pdf
Sorting Application(s),
Sorting Algorithms Review via mini experiment,
PS1 Quick Debrief,
VA OQ demo (sorting),
Hands-on: TBA,
PS2 Discussion (algorithmic)
 		PS1: Basic Python
Due: Wed, 11 Oct 23, 07.59am
 (1.5%)

PS2: Sorting Problems
Out: Wed, 11 Oct 23, 08.00am
09,
Session 3
18+21 Oct 		3a. List ADT: Array vs SLL, Stack & Queue ADT (Slide 1 to 5-6)
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, 18 Oct 23, 07.59am
 (2.5%)

PS3: List Problems
Out: Wed, 18 Oct 23, 08.00am
10,
Session 4
25+28 Oct 		4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3)
Introducing PQ ADT
Introducing basic Binary Heap structure and operations
BinaryHeapDemo.cpp | py | java
Python heapq
See priority_queue.py at GitHub repo of CPbook website
O(N log N) Heapify/Create Heap first
O(N log N) Heap sort first
VisuAlgo Online Quiz 1 (9%)
First 2 topics of IT5003: sorting and list only,
with a few new questions
8.10-8.20pm, onsite
Bring your own laptop
r4. Recitation: Priority Queue
Extra QnA session on anything about PQ, e.g.,
The extra PQ/Binary Heap operations.
Kattis problems discussed today:
TBA,
4b. Priority Queue (PQ) (to end)
O(N) Heapify/Create Heap
O(N + K log N) partial sort vs other sorting algorithms
Short remarks on past paper question involving greedy with PQ
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,
Max-Min PQ conversion (numbers only),
PS3 Quick Debrief,
VA OQ demo (heap),
Hands-on: TBA,
PS4 Discussion (algorithmic)
 		PS3
Due: Wed, 25 Oct 23, 07.59am
 (2.5%)

PS4: PQ Problems
Out: Wed, 25 Oct 23, 08.00am
11,
Session 5
01+04 Nov 		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 bit more PQ,
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
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, 01 Nov 23, 07.59am
 (2.5%)

PS5: (Hash) Table Problems
Out: Wed, 01 Nov 23, 08.00am
12,
Session 6
08+11 Nov 		6a. Graph DS + Applications (read ALL slides), plus
6b. Graph Traversal + Simple Applications (Slide 1 to 7-1)
FAST: Introducing Graph Theory
FAST: Introducing Graph Data Structures
No built-in C++ STL container | Python standard library | Java API,
See graph_ds.cpp | py | java at GitHub repo of CPbook website,
Graph DS Online Quiz (medium),

Introducing Graph Traversal Algorithms,
No built-in C++ STL algorithm | Python standard library | Java API,
See dfs_cc.cpp | py | java, UVa00469.cpp | py | java, and
bfs.cpp | bfs.py | java at GitHub repo of CPbook website,
Kattis problems discussed today:
TBA
VisuAlgo Online Quiz 2 (9%)
First 5 topics of IT5003: sorting, list, heap, hashtable, bst only,
[hashtable: QP/DH and bst: AVL tree questions are removed],
with a few new questions
8.35-8.45pm, onsite
(we need extra time due to the long weekend)
Bring your own laptop
Fri, 10 Nov 2023 is chosen as
NUS well-being day S1 AY 2023/24
Thus, recitation r6 is cancelled
Also, we are not allowed to have a session
on Sat, 11 Nov 2023
(hence, the long(er) Wed, 08 Nov 2023 session)

Prof Halim will depart to Sharm el-Sheikh, Egypt,
on Sat, 11 Nov 2023 night
 		T06+L06: it5003lab6.pdf is cancelled

Sat, 11 Nov 2023 is part of NUS long weekend
Sun, 12 Nov 2023 is Deepavali PH
Thus, Mon, 13 Nov 2023 is also a PH

Discussion of the easy PS6 via Class Discord
 		PS5
Due: Wed, 08 Nov 23, 07.59am
 (2.5%)

PS6: Graph DS+Traversal Problems
Out: Wed, 08 Nov 23, 08.00am
13,
Session 7
15+18 Nov 		Prof Halim will be in Sharm el-Sheikh, Egypt,
for combo ICPC World Finals 2022+2023 (12-17 Nov 2023)
Prof Halim plans to record only the Wed session for this week...
Prof Halim's current return flight will arrive on Fri, 17 Nov, 8.30am
on time for r7 and 7b.
7a. Graph Traversal continued (Slide 7-2 to 7-11)
THIS ONE IS 100% RECORDED.
Recap of session 6b.
DFS/BFS Online Quiz (medium),
Kattis problems discussed today:
TBA
r7. Recitation: (Balanced) BST + Graph 1
[ONSITE]
Review of BST, plus the non-examinable balanced BST
Extra QnA session on anything about graph,
Review of Graph DS and Graph Traversal
i.e., graph ds (implicit graph),
graph traversal (especially cyclic test and toposort),
Kattis problems discussed today:
TBA
Our venue may be prepped for UG final assessment venue
If that happens (again), we will plan around it...
7b. Single-Source Shortest Paths (SSSP) Problem
(Slide 1 to 2; then BFS: slide 5 to 6-3)
[ONSITE]
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
 		T07+L07: it5003lab7.pdf
Graph DS Fast Review,
Graph DS Conversion Exercise,
DFS/BFS Review,
SSSP Review 1 (unweighted/BFS),
Graph Modeling exercise,
PS5+6 Quick Debrief,
VA OQ demo (graphds,dfsbfs),
Hands-on: TBA,
PS7 Discussion (algorithmic) 		PS6
Due: Wed, 15 Nov 23, 07.59am
 (2.5%)

PS7: Graph Traversal+SSSP Problems
Out: Wed, 15 Nov 23, 08.00am
Reading,
Session 8
22+25 Nov 		8a. Single-Source Shortest Paths (SSSP) Problem
(Modified Dijkstra's: slide 8 to 8-5)
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
r8. Recitation: SSSP
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. Course wrap up
Showing the limit of computation:
Introduction to the theory of NP-completeness
Last few words
VisuAlgo Online Quiz 3 (9%)
All topics of IT5003 (including /sssp), with a few new questions
[hashtable: QP/DH, bst: AVL tree, sssp: Bellman-Ford questions are removed],
with a few new questions
9.30-9.40am, onsite
Bring your own laptop
 		T08+L08: it5003lab8.pdf
SSSP Review 2,
Graph Modeling exercise 3,
Hands-on: Just do PS8 in-class until end.
(there may be extras for those who have completed PS8)
Lab participation marks given (3%) 		PS7
Due: Wed, 22 Nov 23, 07.59am
 (2.5%)

PS8: Weighted SSSP Problems
Out: Wed, 22 Nov 23, 08.00am
"Study Window", 28 Nov-06 Dec 2023

Final Assessment Discussions at Class Discord

Final Assessment Past Papers (recent 3 AYs only):
AY 2020/21: S1-final.pdf, S2 (A/P Soo Yuen Jien, N/A),
AY 2021/22: S1-final.pdf, S2-final.pdf,
AY 2022/23: S1-final.pdf, S2-final.pdf,
AY 2023/24: S1-final.pdf (will be our paper; will be easier than last semester; I promise).
 PS8
Due: Wed, 29 Nov 23, 07.59am
 (2.5%)
Final Assessment (50%)
Date and Time: Thu, 07 Dec 2023, 5-7PM
Venue: TBA
45% MCQs (very tricky); 25% easy short questions; 30% differentiator questions