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:
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
SLLDemo.py 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)
Lab3
SLL/Stack/Queue Review via mini experiment,
Python implementations for list, stack, and queue,
PS1 Quick Debrief,
VA OQ demo (sorting),
Hands-on,
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

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)

Lab4
PQ ADT Review,
Binary Heap Review,
Max-Min conversion,
PS2 Quick Debrief,
VA OQ demo (list,heap),
Hands-on
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, skip 7-8-9, then 10-end)
Table ADT and DAT
Basic Hashing Concepts
Collission Resolution Techniques: Closed Addressing (Separate Chaining)
HashTableDemo.py
Hash Table Online Quiz (medium)
See unordered_map_unordered_set.py 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),
Lab5.pdf
Basic Hashing Concepts,
Hash Table Issues,
PS3 Quick Debrief,
VA OQ demo (hashtable,bst),
Hands-on,
PS4 Discussion (algorithmic)
PS3
Due: Mon, 02 Nov 20, 07.59am
(4%)

PS4: A (Hash) Table Problem
Out: Mon, 02 Nov 20, 08.00am
13,
Session 6
09 Nov
6a. Graph DS + Applications
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:
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
PS4
Due: Mon, 09 Nov 20, 07.59am
(4%)

PS5: Very Simple Graph Problem
Out: Mon, 09 Nov 20, 08.00am
Reading,
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 dfs_cc.py and UVa00469.py 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 bfs.py at GitHub repo of CPbook website,
DFS/BFS Online Quiz (medium),
Kattis problems discussed:
brexit (kind of topological sorting; modified BFS/Kahn's algorithm)
Lab6.pdf
Graph DS Review,
Graph Modeling exercise 1,
DFS/BFS Review,
PS5 Debrief,
VA OQ demo (graphds,dfsbfs),
Hands-on,
PS6 Discussion (algorithmic)
PS5
Due: Mon, 16 Nov 20, 07.59am
(4%)

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 dijkstra.py 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
Lab7.pdf
VA OQ demo (dfsbfs,sssp),
Hands-on: Do PS7 in-class,
VisuAlgo Online Quiz
(22%)
PS6
Due: Mon, 23 Nov 20, 07.59am
(4%)

PS7: An SSSP Problem
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