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