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 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.

Syllabus

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.

News

Date News

Lesson Plan

Week Lecture,
2+1h/session
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),
2h/session
(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
-01,
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
08,
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)
SpeedTest.py
(Kattis) problems discussed:
thanos (Analysis: exponential growth, logarithmic steps),
Lab1
Introduction,
Algorithm Analysis,
SpeedTest.py mods,
Warm-up review + analysis,
Hands-on: upsanddownsofinvesting
(1D list/array processing)
Optional Warm-up, continued
not graded
09,
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
SortingDemo.py (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
SortingDemo.py (O(N log N) Merge Sort)
Other topics of sorting e-Lecture
Sorting Online Quiz (medium)
Lab2
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
10,
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,
SLLDemo.py (custom SLL and Stack)
Python list as stack,
Kattis problems discussed in this session:
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
Python list as queue (slow)
SLLDemo.py revisited (custom Queue, can be made fast)
Python deque for Queue ADT (fast)
Linked List Online Quiz (medium)
Kattis problems discussed:
server (NEW: application of Queue ADT)
Lab3
SLL/Stack/Queue Review via mini experiment,
Python implementations for list, stack, and queue,
PS1 Quick Debrief,
VA OQ demo (sorting),
Hands-on: integerlists
(interesting list problem; pop(0)?, reverse?),
PS2 Discussion (algorithmic)
PS1
Due: Mon, 19 Oct 20, 07.59am
(4%)

PS2: List Problems
Out: Mon, 19 Oct 20, 08.00am
11,
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
BinaryHeapDemo.py
Python heapq
See priority_queue.py at GitHub repo of CPbook website
Kattis problems discussed in this session:
numbertree (for a short wow moment)


4b. Priority Queue (PQ) (Slide 7 to end,
but skipping Slide 7-3 to 7-5)
Binary Heap Online Quiz (medium)
PS3 hints
Lab4
PQ ADT Review,
Binary Heap Review,
Max-Min conversion,
PS2 Quick Debrief,
VA OQ demo (list,heap),
Hands-on: stockprices
(both min and max PQ in action),
PS3 Discussion (algorithmic)
PS2
Due: Mon, 26 Oct 20, 07.59am
(4%)

PS3: PQ Problems
Out: Mon, 26 Oct 20, 08.00am
12,
Session 5
02+07 Nov
5a. Table ADT: Hash Table (Slide 1 to 6, then Slide 10 to end,
but skipping Slide 7 to 9-4)
Table ADT
Direct Addressing Table (DAT)
Basic Hashing Concepts
Collission Resolution Techniques: Closed Addressing (Separate Chaining)
HashTableDemo.py
Python set and Python dict
See unordered_map_unordered_set.py at GitHub repo of CPbook website
Hash Table Online Quiz (medium)
Kattis problems discussed in this session:
competitivearcadebasketball (basic table ADT task)

5b. Table ADT part 2: Binary Search Tree (Slide 1 to 11 only)
Presenting alternative Table ADT: BST
Short exposure about self-balancing trees
No built-in library for Python
BST Online Quiz (medium)
Lab5
Table ADT Review,
Basic Hashing Concepts,
Hash Table Issues,
Quick BST Review,
PS3 Quick Debrief,
VA OQ demo (hashtable,bst),
Hands-on: shiritori
(Hash Table Application 1),
Hands-on: whatdoesthefoxsay
(Hash Table Application 2),
PS4 Discussion (algorithmic)
PS3
Due: Mon, 02 Nov 20, 07.59am
(4%)

PS4: (Hash) Table Problems
Out: Mon, 02 Nov 20, 08.00am
13,
Session 6
09 Nov
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 problem discussed in this session:
flyingsafely (for a 30s jaw-dropping moment)
dominoes2 (preview of DFS)

Deepavali is on Sat, 14 Nov 2020
IT5003 Saturday classes (Lecture + Lab) are cancelled.
There is no replacement session.
Instead, Steven will record 'extras' at the back of 09 Nov session.
No class
Deepavali Public Holiday
PS4
Due: Mon, 09 Nov 20, 07.59am
(4%)

PS5: Graph DS Problems
Out: Mon, 09 Nov 20, 08.00am
Reading,
Session 7
16+21 Nov
7a. Graph Traversal + Simple Applications (Slide 1 to 6-4)
Introducing Graph Traversal Algorithms,
Convert Graph to Tree Quiz,
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 problem discussed in this session:
dominoes2 (recode to BFS)
wheresmyinternet (reachability test from vertex 1; DFS/BFS)
reachableroads (DFS/BFS, count #CC, like /flyingsafely)

7b. Graph Traversal continued (parts of slide 7 only)
DFS/BFS Online Quiz (medium),
Kattis problem discussed in this session:
amoebas (modified DFS called 'floodfill'/finding CC variant, implicit 2d grid graph)
brexit (EXTRA: kind of topological sorting; modified BFS/Kahn's algorithm)
Lab6
Graph DS Review + Create DAG,
Graph Modeling exercise 1,
DFS/BFS Review esp Toposort,
PS4+5 Quick Debrief,
VA OQ demo (graphds,dfsbfs),
Hands-on: builddeps
(Hash Table Application 1),
PS6 Discussion (algorithmic)
PS5
Due: Mon, 16 Nov 20, 07.59am
(4%)

PS6: Graph Traversal Problems
Out: Mon, 16 Nov 20, 08.00am
UG Exam Week,
Session 8
23+28 Nov
8a. Single-Source Shortest Paths (SSSP) Problem (Slide 1 to 2)
(BFS: slide 5 to 6-3 and Modified Dijkstra's: slide 8 to 8-5)
Introducing SSSP Problem
BFS Review for unweighted cases (you have seen this on Session 7)
Introducing (Modified) Dijkstra's Algorithm
No built-in Python algorithm,
[Review]: See bfs.py at GitHub repo of CPbook website,
See dijkstra.py at GitHub repo of CPbook website,
SSSP Online Quiz (medium),
Kattis problem discussed in this session:
horror (BFS demo; implicit graph)
shortestpath1 (that Dijkstra's implementation is easy)

8b. Course wrap up, plus
showing the limit of computation:
Introduction to the theory of NP-completeness
We will end by 9.50am,
then do 25m VA OQ first
Before we do the last Lab7

VisuAlgo Online Quiz (22%)
(URL: https://visualgo.net/training, click 'IT5003 Quiz')
Time: 25m inside 9.55-10.20am,
20 random hard (may luck be with you) questions
All topics in IT5003, EXCEPT:
Hash Table (mostly OA), AVL Tree (not covered),
SSSP (too late and we skipped many variants)
Just ONE run to simplify e-proctoring
See LumiNUS files for the details announced during
Mon 23 Nov 2020 e-lecture
[Start at 10.30am, 1.5h only]

Lab7
SSSP Review,
Two SSSP Applications,
PS6 Quick Debrief,
Skipped: VA OQ demo (sssp),
Simple SSSP questions in final instead,
Hands-on: Do PS7 in-class until end.
(there may be extras for those who have completed PS7)
PS6
Due: Mon, 23 Nov 20, 07.59am
(4%)

PS7: SSSP Problems
Out: Mon, 23 Nov 20, 08.00am

PS7
Due: Sat, 28 Nov 20, 11.59am
(4%)
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