IT5003 - Data Structures and Algorithms (Python)


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 module 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 first time Steven teaches this 8-weeks IT5003 GC-CF module (in Python), but current students can view his 13-weeks CS2040C UG version for a quick review of what Steven's teaching style looks like.


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

Note: This course registration section will not be prominent from Week 8 of S1 AY20/21 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.


Date News

Lesson Plan

Week Lecture,
Every Mon 6.30-8.30pm and
Every Sat 9-10am
All online, from Wk08
(VA e-Lecture Slides, plus
Zoom Q&A sessions)
Lab (a bit of Tutorial),
(online sessions
live synchronous),
From Wk08
Interesting Problem Set
@ Home
Every Week
~5 hours/set
From Wk08
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
Bef Mon,
05 Oct
Not started, but please revise your CS1010/IT5001
(Steven assumes that all? of you have taken
or exempted from this module/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 optional Kattis Online Judge problems
by yourself (CS1010/IT5001 level):
Not Started Easy Python challenges:
Optional Warm-up
(10++ 'easy' problems in Kattis)
not graded
Solving a few
indirectly tells Steven
about your CS1010/IT5001 rough grade
Session 1
05+10 Oct
1a. Course Admin, (Re-)Introduction to Python
Setting the tone for a flipped classroom plus 100% ONLINE module
VisuAlgo + this Private LumiNUS + Kattis (NUS) + Kattis (open)
Basic Python review/new feature introduction
Kattis problems discussed:
compass (revise I/O, control flow: repetition (or O(1) formula), selection)
wertyu (revise basic string processing problem; mapping technique, string)

Reminder: Read short lecture note on algorithm analysis
before Lecture 1b

1b. Analysis of Algorithms (slide 6 to 6-11)
(old CS1020/E lecture note on this topic will be digitised later)
(Kattis) problems discussed:
thanos (Analysis: exponential growth, logarithmic steps),
Algorithm Analysis, mods,
Warm-up review + analysis,
Hands-on: upsanddownsofinvesting
(1D list/array processing)
Optional Warm-up, continued
not graded
Session 2
12+17 Oct
Reminder: Read sorting e-Lecture slides before Lecture 2a
At least until slide 9-3, preferably more

2a. Sorting (Slide 1 to 9-3)
(Re-)Introducing simpler but O(N^2) Sorting Algorithms (O(N^2) versions)
Python list, list.sort(), or sorted(list)
Kattis problems discussed in this session:
lineup (Python list.sort(), reverse list, or linear pass),
mjehuric (review Bubble sort),
height (review Insertion sort),
sortofsorting (NEW: custom comparator, Python list.sort() is stable)

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

2b. Sorting (Slide 10 to 11-10 and Slide 17-end;
but skipping Slide 12 to 16-1)
Introducing O(N log N) Merge Sort (O(N log N) Merge Sort)
Other topics of sorting e-Lecture
Sorting Online Quiz (medium)
Sorting Application(s),
Sorting Algorithms Review via mini experiment,
Hands-on: judging
(set intersection; modified merge),
PS1 A+B Discussion (algorithmic)
Optional Warm-up
"Due": Mon, 12 Oct 20, 07.59am
not graded

PS1: Basic+Sorting
Out: Mon, 12 Oct 20, 08.00am
Session 3
19+24 Oct
3a. List ADT: Array vs (Singly) LL, Stack ADT (Slide 1 to 4-7)
Introducing List ADT
Python list (actually not a linked list) for List ADT,
Introducing (some of) SLL operations,
Introducing Stack ADT, (custom SLL and Stack)
Python list as stack,
Kattis problems discussed:
delimitersoup (NEW: application of Stack ADT)

3b. Queue ADT (Slide 5 to 5-6 and Slide 8-end;
but skipping Slide 6 to 7-1)
Introducing Queue ADT revisited (custom Queue, not fast)
Python list as queue (slow) vs Python deque (faster)
Linked List Online Quiz (medium)
Kattis problems discussed:
server (NEW: application of Queue ADT)
SLL/Stack/Queue Review via mini experiment,
Python implementations for list, stack, and queue,
PS1 Quick Debrief,
VA OQ demo (sorting),
PS2 Discussion (algorithmic)
Due: Mon, 19 Oct 20, 07.59am

PS2: List Problems
Out: Mon, 19 Oct 20, 08.00am
Session 4
26+31 Oct
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 6)
Introducing PQ ADT
Introducing basic Binary Heap structure and operations
Python heapq
See at GitHub repo of CPbook website

4b. Priority Queue (PQ) (Slide 7 to end,
but skipping Slide 7-2 to 7-5)
Binary Heap Online Quiz (medium)
Kattis problems discussed:
numbertree (for a short wow moment)

PQ ADT Review,
Binary Heap Review,
Max-Min conversion,
PS2 Quick Debrief,
VA OQ demo (list,heap),
PS3 Discussion (algorithmic)
Due: Mon, 26 Oct 20, 07.59am

PS3: PQ Problems
Out: Mon, 26 Oct 20, 08.00am
Session 5
02+07 Nov
5a. Table ADT: Hash Table (slide 1 to 6, skip 7-8-9, then 10-end)
Table ADT and DAT
Basic Hashing Concepts
Collission Resolution Techniques: Closed Addressing (Separate Chaining)
Hash Table Online Quiz (medium)
See at GitHub repo of CPbook website
Kattis problems discussed:
competitivearcadebasketball (basic table ADT task)

5b. Table ADT part 2: Binary Search Tree (until slide 11)
Presenting alternative Table ADT: BST
Short exposure about self-balancing trees
No built-in library for Python
BST Online Quiz (medium),
Basic Hashing Concepts,
Hash Table Issues,
PS3 Quick Debrief,
VA OQ demo (hashtable,bst),
PS4 Discussion (algorithmic)
Due: Mon, 02 Nov 20, 07.59am

PS4: A (Hash) Table Problem
Out: Mon, 02 Nov 20, 08.00am
Session 6
09 Nov
6a. Graph DS + Applications
Introducing Graph Theory
Introducing Graph Data Structures
No built-in Python library,
See at GitHub repo of CPbook website,
Graph DS Online Quiz (medium),
Kattis problem discussed:
flyingsafely (for a 30s jaw-dropping moment)

Deepavali is on Sat, 14 Nov 2020
IT5003 Saturday classes (Lecture + Lab) are cancelled.
Replacement session TBA.
No class
Deepavali Public Holiday
Due: Mon, 09 Nov 20, 07.59am

PS5: Very Simple Graph Problem
Out: Mon, 09 Nov 20, 08.00am
Session 7
16+21 Nov
7a. Graph Traversal + Simple Applications (until slide 5-8)
Introducing Graph Traversal Algorithms,
Convert Graph to Tree Quiz,
No built-in Python algorithm,
See and at GitHub repo of CPbook website,
Kattis problem discussed:
reachableroads (DFS (BFS) introduction, count #CC)

7b. Graph Traversal continued (slide 6 + parts of slide 7 only)
See at GitHub repo of CPbook website,
DFS/BFS Online Quiz (medium),
Kattis problems discussed:
brexit (kind of topological sorting; modified BFS/Kahn's algorithm)
Graph DS Review,
Graph Modeling exercise 1,
DFS/BFS Review,
PS5 Debrief,
VA OQ demo (graphds,dfsbfs),
PS6 Discussion (algorithmic)
Due: Mon, 16 Nov 20, 07.59am

PS6: A Graph Traversal Problem
Out: Mon, 16 Nov 20, 08.00am
UG Exam Week,
Session 8
23+28 Nov
8a. Single-Source Shortest Paths (SSSP) Problem: BFS and Dijkstra's
Introducing SSSP Problem
BFS Review for unweighted cases
Introducing (Modified) Dijkstra's Algorithm
No built-in Python algorithm,
See at GitHub repo of CPbook website,
SSSP Online Quiz (medium),
Kattis problem discussed:
horror (BFS demo; implicit graph)
shortestpath1 (that Dijkstra's implementation is easy)

08b. Limit of Computation:
Introduction to the theory of NP-completeness
VA OQ demo (dfsbfs,sssp),
Hands-on: Do PS7 in-class,
VisuAlgo Online Quiz
Due: Mon, 23 Nov 20, 07.59am

PS7: An SSSP Problem
Out: Mon, 23 Nov 20, 08.00am

Due: Sat, 28 Nov 20, 11.59am
Study Week, 29 Nov-04 Dec 2020

Final Assessment Consultations (per request)
Final Assessment (50%)
Date and Time: Sat, 05 Dec 2020, 9-11AM (TBC)
Venue: e-Exam (TBC)
Likely MCQ/short answers @ Luminus Quiz + Zoom e-proctoring
All other details TBC