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, 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 fifth time Steven teaches this 8-weeks IT5003 MComp General Track (and a bit of other MComp specializations: Digital FinTech + Biomed) + Graduate Certificates in Computing Foundations (GC-CF) course (in Python). Steven set IT5003 as a 'subset' (obviously, as we only have 8-weeks) of his full 13-weeks CS2040C Undergraduate version of similar course. The previous four iterations were 'reasonably good'. One thing to take note is that Steven'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, Steven is preparing for a 120-ish class size with mostly onsite components (more details in the lesson plan below).

Some other facts:

  1. Steven uses flipped classroom, machine-teach-(and-auto-test)-students-on-basic-stuffs, and in-class live discussion of (hard)er problems in his IT5003/CS2040C classes many times in recent AYs (AY 2017/18 - present). His teaching feedback ratings for those IT5003 offerings vary in [4.4..4.6 (v good)] bracket out of maximum 5.0.
  2. Teaching staffs:
    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used very extensively in this course.
    The main target for this semester is to have many onsite components (see below for the details).
    Rating
    (out of 5.0)
    Mar-May 23
    (n≥58/115)
    ≥ 50%
    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.9) Target ≥ 4.1 (target) 4.4 == (PB again) 4.4 (PB) 4.3 4.2
    Course difficulty (SoC avg ~3.8) Target ≤ 3.9 (ok, maintain this) 3.9 (as per target) 3.8 3.5 (PB, too easy) 4.0
    Steven's teaching (SoC avg ~4.2) Target ≥ 4.3 (target) 4.6 == (PB again) 4.6 (PB) 4.5 4.4
    Date, Time Live (or E-Learn) Session (Venue) (#Stu/#Cap) No Tutor
    a/Sat, 1000-1200 SR@LT19 (27/24) B1 @the lecturer
    b/Sat, 1000-1200 COM3-SR91 (24/24) B4 @hao_yi
    c/Sat, 1000-1200 COM2-TR9 (21/24) B5 @daryllzy
    d/Mon, 1400-1600 COM1-B-112 (PL1) + SR@LT19 — for full-time MComp students (25/24) B2 @Jeanette
    e/Mon, 1600-1800 COM1-B-112 (PL1) + SR@LT19 — for full-time MComp students (19/24) B3 @Yuheng

    List of TAs:

    1. @the lecturer, Dr Steven Halim
    2. @Jeanette, Tan Yu Wei (full-time TA)
    3. @hao_yi, Cheah Hao Yi
    4. @Yuheng, Chen Yuheng
    5. @daryllzy, Lian Ziyue
  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 Steven:

  • 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
  • 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 S2 AY 2022/23 be 100% onsite?
A: Now the default has shifted back for even more normalcy in 2023. Now both Wed night and Sat morning lectures are onsite at COM1-0206 (SR1). Almost everything in this course is now onsite, except perhaps some parallel lab sessions on Sat (two slots) and special cases when our lecture/recitation/lab venue is not available. Please take this information into account when taking this course. Update on 06 Mar: ALL Sat morning lab classes are also converted to fully onsite now.
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 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 S2 AY 2022/23 compared to your last semester (S1 AY 2022/23) version?
A: Not much, these are the potential changes:
  1. IT5003 starts from Wed, 01 Mar 2023 (Week 07), one week earlier than in the recent semester (thanks to IT5001 teaching colleagues who have agreed to re-map 8 weeks IT5001 to 7 weeks for this to happen). This very important change is done so that the 8-weeks IT5003 does not clash with NUS exam week 1 on its 8th week (but still clash with NUS reading week, no choice) and IT5003 final assessment can be scheduled a few days earlier than the last Sat of NUS exam week 2.
  2. Onsite (F2F) course components are the default now, the most notable change is the Wed night lectures.
  3. NUS Well Being Day for S2 AY 2022/23 is chosen to be Thu, 06 Apr 2023 (to make it a long weekend for NUS staffs and students) --- this does not affect IT5003, but the following Good Friday Public Holiday (Fri, 07 Apr 2023) cancels one of IT5003 Fri recitation slot and apology in advance for not cancelling Sat, 08 Apr 2023 classes (we really need that timeslot...).
  4. Another iterative small enhancement to various VA e-Lecture slides and VA Online Quizzes.
  5. VisuAlgo Online Quiz system weightage will be increased again from 9+10 = 19% to 11+12 = 23% this semester with more interesting automatically graded questions added. Consequently, the heavier PSes (but are mostly not grade differentiator) weightage will be decreased again from 8x3.5 = 28% last semester to 8x3 = 24% this semester.

Note: This course registration section will not be prominent from Week 8 of S1 AY 2022/23 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 2022/23 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
-03 and -02
Not started, but please revise your CS1010/IT5001
(Steven assumes that all? of you have taken
or exempted from this course/its variants,
i.e., you can code in simply 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 0a (PS0a) by yourself (CS1010/IT5001 level):
(solving many 'trivial (many one-liner) problems' from this set
---trackable by Steven, indirectly tells Steven
about your CS1010/IT5001 rough grade)
Not Started PS0a: Easy Python/coding challenges
Out: Wed, 15 Feb 23, 08.00am
-01,
Bef Wed,
01 Mar
Not Started, but Steven sets another easy PS0b...
This is a useful practice for those also taking IT5001 (ending soon)
Not Started PS0a: Easy Python/coding challenges
Due: Wed, 22 Feb 23, 07.59am
(not graded yet)

PS0b: Easy Python/coding challenges
Out: Wed, 22 Feb 23, 08.00am
07,
Session 1
01+04 Mar
1a. Course Admin, (Re-)Introduction to Python
Setting the tone for a flipped classroom but mostly onsite classes
VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open)
Basic Python review/new feature introduction

Reminder: Read summary on algorithm analysis
before Lecture 1c

COM1-02-06 is booked for Open House
on Fri-Sat, 03-04 Mar 23
We do the first recitation and Sat lecture online

1b. Recitation: Basic Python [ONLINE]
Extra QnA session on Basic Python,
discussion of more/alternative Python features,
review PS0a and PS0b: Easy Python/coding challenges tasks

1c. Analysis of Algorithms (slide 6 to 6-11) [ONLINE]
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)
T01+L01: it5003lab1.pdf
Introduction,
Algorithm Analysis,
SpeedTest.py mods,
PS0a and PS0b review,
Hands-on: vaccineefficacy
(1D or 2D list/array processing)
PS1 Discussion (algorithmic)
PS0b: Easy Python/coding challenges
Due: Wed, 01 Mar 23, 07.59pm
(0.5% — to speed up admins)

PS1: Basic Python
Out: Wed, 01 Mar 23, 08.00pm
Easier subtasks showcased live during the first lecture
08,
Session 2
08+11 Mar
Reminder: Read sorting e-Lecture slides before Lecture 2a
At least until slide 11-11, preferably more

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:
nothanks (NEW: Python list.sort() or sorted(list) and linear pass),
mjehuric (review Bubble sort),
height (review Insertion sort)

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

2b. 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:
sortofsorting (NEW: custom comparator, Python list.sort() is stable)
lineup (extra O(N log N) vs O(N) exercise)

2c. 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: judging
(multiset intersection; greedy bipartite matching;
modified merge routine (other solution exists)),
PS2 Discussion (algorithmic)
PS1: Basic Python
Due: Wed, 08 Mar 23, 07.59am
(2.5%)

PS2: Sorting Problems
Out: Wed, 08 Mar 23, 08.00am
09,
Session 3
15+18 Mar
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)

3b. 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, etc.
Kattis problems discussed today:
throwns (NEW: application of Stack ADT; modulo)

3c. 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: integerlists
(interesting list problem; pop(0)?, reverse?)
PS3 Discussion (algorithmic)
PS2
Due: Wed, 15 Mar 23, 07.59am
(3%)

PS3: List Problems
Out: Wed, 15 Mar 23, 08.00am
10,
Session 4
22+25 Mar
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3)
Introducing PQ ADT
Introducing basic Binary Heap structure and operations
BinaryHeapDemo.py
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

4b. Recitation: Priority Queue
Extra QnA session on anything about PQ, e.g.,
The extra PQ/Binary Heap operations.
Mock VA OQ 1 (medium level only)
Kattis problems discussed today:
rationalsequence3 (combo DS: pq+stack)

4c. Priority Queue (PQ) (to end)
O(N) Heapify/Create Heap
O(N + K log N) partial sort vs other sorting algorithms
Kattis problems discussed today:
TBA

VisuAlgo Online Quiz 1 (11%)
First 3 topics of IT5003: sorting, list, heap (only a bit),
with a few new questions
9.30-9.45am, onsite at COM1-0206 (SR1)
Bring your own laptop
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, 22 Mar 23, 07.59am
(3%)

PS4: PQ Problems
Out: Wed, 22 Mar 23, 08.00am
11,
Session 5
29 Mar+01 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: Separate Chaining vs Linear Probing
HashTableDemo.py
Python set, dict, defaultdict, or Counter
See unordered_map_unordered_set.py at GitHub repo of CPbook website
Kattis problems discussed today:
TBA

5b. 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,
Kattis problems discussed today:
TBA

5c. Table ADT part 2: Binary Search Tree (Slide 1 to 11)
Presenting alternative Table ADT: BST
BSTDemo.py
Short exposure about self-balancing trees
No built-in library for Python
BST Online Quiz (medium)

NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until our 8th/last week
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, 29 Mar 23, 07.59am
(3%)

PS5: (Hash) Table Problems
Out: Wed, 29 Mar 23, 08.00am
12,
Session 6
05+08 Apr
6a. Graph DS + Applications (read ALL slides)
Introducing Graph Theory
Introducing Graph Data Structures
No built-in Python library,
See graph_ds.py at GitHub repo of CPbook website,
Graph DS Online Quiz (medium),
Kattis problems discussed today:
TBA

Thu, 06 Apr 2023 is chosen as
NUS well being day S2 AY 2022/23
Then, we have Good Friday PH on Fri, 07 Apr 2023
Thus recitation 6b is cancelled and merged with 7b
But Sat, 08 Apr 2023 classes remain as per normal
(apology in advance for this, rescheduling lecture 6c
and Sat lab sessions at other times are impossible)

6c. Graph Traversal + Simple Applications (Slide 1 to 7-1)
Introducing Graph Traversal Algorithms,
No built-in Python algorithm,
See dfs_cc.py and UVa00469.py at GitHub repo of CPbook website,
See bfs.py at GitHub repo of CPbook website,
Kattis problems discussed today:
TBA
T06+L06: it5003lab6.pdf
Graph DS Review,
Create DAG,
Graph DS Conversion Exercise,
Graph Modeling exercise 1,
DFS/BFS Review 1,
PS5 Quick Debrief,
VA OQ demo (graphds,dfsbfs),
Hands-on: TBA
PS6 Discussion (algorithmic)
PS5
Due: Wed, 05 Apr 23, 07.59am
(3%)

PS6: Graph DS+Traversal Problems
Out: Wed, 05 Apr 23, 08.00am
13,
Session 7
12+15 Apr
7a. Graph Traversal continued (Slide 7-2 to 7-11)
DFS/BFS Online Quiz (medium),
Kattis problems discussed today:
TBA

7b. Recitation: (Balanced) BST + Graph 1
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

COM1-2-SR1 will be prepped for UG final assessment venue
by this weekend; therefore for 7b, 8a, and recitation 8b,
we will be moved to iCube-Auditorium

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)
No built-in Python algorithm, see bfs.py at GitHub repo of CPbook website,
Preview of Modified Dijkstra's (to be discussed in more details next Wed),
Kattis problems discussed today:
TBA
T07+L07: it5003lab7.pdf
DFS/BFS Review 2,
SSSP Review 1,
Graph Modeling exercise 2,
PS6 Quick Debrief,
VA OQ demo (dfsbfs),
Hands-on: TBA
PS7 Discussion (algorithmic)
PS6
Due: Wed, 12 Apr 23, 07.59am
(3%)

PS7: Graph Traversal+SSSP Problems
Out: Wed, 12 Apr 23, 08.00am
Reading,
Session 8
19+22 Apr
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)
No built-in Python algorithm, see dijkstra.py at GitHub repo of CPbook website,
SSSP Online Quiz (medium),
Kattis problems discussed today:
TBA
Course wrap up

VisuAlgo Online Quiz 2 (12%)
All topics of IT5003, with a few new questions
We may need to go beyond 8.30pm tonight
As we don't have lecture 8.c...
Details TBC

8b. e-Recitation: Semester Recap + a bit of NP-completeness
Extra QnA session on anything about IT5003 topics
Focus on SSSP first, BFS for unweighted graph, Modified Dijkstra's for non-negative weighted graph,
effect of negative weights, other special cases of SSSP problems, etc.
Showing the limit of computation:
Introduction to the theory of NP-completeness
Kattis problems discussed today:
TBA

NUS Online Teaching Feedback closes on Friday of Study Week
We have Hari Raya Puasa PH on Sat, 22 Apr 2023
Thus the last Sat lecture 8.c is cancelled
And Sat lab groups are encouraged
to attend any of the last Mon session on Mon, 24 Apr 2023 (recorded)
Lab08 is only for Mon, 24 Apr 2023

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, 19 Apr 23, 07.59am
(3%)

PS8: Weighted SSSP Problems
Out: Wed, 19 Apr 23, 08.00am
"Study Window", 26 Apr-03 May 2023

Final Assessment Consultations (per request)

Final Assessment Past Papers:
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 (most recent past paper); S2-final.pdf (obviously N/A yet).
PS8
Due: Wed, 26 Apr 23, 07.59am
(3%)
Final Assessment (50%)
Date and Time: Thu, 04 May 2023, 5-7PM
Venue: TBC (but it will be an onsite F2F final assessment)
X% MCQs (tricky); Y% easier essay; Z% differentiator questions