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