This course 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 course 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 going to be the fifth time Steven teaches this 8-weeks IT5003 MComp General Track (and a bit of other MComp specializations: Digital FinTech + Biomed) + Graduate Certificates in Computing Foundations (GC-CF) course (in Python). Steven set IT5003 as a 'subset' (obviously, as we only have 8-weeks) of his full 13-weeks CS2040C Undergraduate version of similar course. The previous four iterations were 'reasonably good'. One thing to take note is that Steven's teaching style is flipped classroom that may be quite surprising for some adult learners who are not used to this teaching style in the past.
This time, Steven is preparing for a 120-ish class size with mostly onsite components (more details in the lesson plan below).
Some other facts:
| Rating (out of 5.0) |
Mar-May 23 (n≥58/115) ≥ 50% |
Oct-Dec 22 (n=100/178) 56% ▼ |
Mar-May 22 (n=57/99) 58% ▼ |
Oct-Dec 21 (n=83/130) 63% ▲ |
Oct-Dec 20 (n=5/33) 15% (too small) |
|---|---|---|---|---|---|
| Course feedback (SoC avg ~3.9) | Target ≥ 4.1 (target) | 4.4 == (PB again) | 4.4 ▲ (PB) | 4.3 ▲ | 4.2 |
| Course difficulty (SoC avg ~3.8) | Target ≤ 3.9 (ok, maintain this) | 3.9 ▼ (as per target) | 3.8 ▼ | 3.5 ▼ (PB, too easy) | 4.0 |
| Steven's teaching (SoC avg ~4.2) | Target ≥ 4.3 (target) | 4.6 == (PB again) | 4.6 ▲ (PB) | 4.5 ▲ | 4.4 |
| Date, Time | Live (or E-Learn) Session (Venue) (#Stu/#Cap) | No | Tutor |
|---|---|---|---|
| a/Sat, 1000-1200 | SR@LT19 (27/24) | B1 | @the lecturer |
| b/Sat, 1000-1200 | COM3-SR91 (24/24) | B4 | @hao_yi |
| c/Sat, 1000-1200 | COM2-TR9 (21/24) | B5 | @daryllzy |
| d/Mon, 1400-1600 | COM1-B-112 (PL1) + SR@LT19 — for full-time MComp students (25/24) | B2 | @Jeanette |
| e/Mon, 1600-1800 | COM1-B-112 (PL1) + SR@LT19 — for full-time MComp students (19/24) | B3 | @Yuheng |
List of TAs:
This is what you will learn in IT5003 as taught by Steven:
If you have any important questions regarding this course, email dcssh at nus dot edu dot sg. Relevant answers will be posted here to reach wider audiences.
Note: This course registration section will not be prominent from Week 8 of S1 AY 2022/23 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
| Date | News |
|---|
The S2 AY 2022/23 timetable below is still tentative, especially those that are highlighted with pink color.
| Week | Lecture | Tutorial+Lab Combo | Interesting Problem Set |
|---|---|---|---|
| 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 | |||
|
-03 and -02 |
Not started, but please revise your CS1010/IT5001 (Steven assumes that all? of you have taken or exempted from this course/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 selected optional Online Judge (OJ) Problem Set 0a (PS0a) by yourself (CS1010/IT5001 level): (solving many 'trivial (many one-liner) problems' from this set ---trackable by Steven, indirectly tells Steven about your CS1010/IT5001 rough grade) |
Not Started |
PS0a: Easy Python/coding challenges Out: Wed, 15 Feb 23, 08.00am |
|
-01, Bef Wed, 01 Mar |
Not Started, but Steven sets another easy PS0b... This is a useful practice for those also taking IT5001 (ending soon) |
Not Started |
PS0a: Easy Python/coding challenges Due: Wed, 22 Feb 23, 07.59am (not graded yet) PS0b: Easy Python/coding challenges Out: Wed, 22 Feb 23, 08.00am |
|
07, Session 1 01+04 Mar |
1a. Course Admin, (Re-)Introduction to Python Setting the tone for a flipped classroom but mostly onsite classes VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open) Basic Python review/new feature introduction Reminder: Read summary on algorithm analysis before Lecture 1c COM1-02-06 is booked for Open House on Fri-Sat, 03-04 Mar 23 We do the first recitation and Sat lecture online 1b. Recitation: Basic Python [ONLINE] Extra QnA session on Basic Python, discussion of more/alternative Python features, review PS0a and PS0b: Easy Python/coding challenges tasks 1c. Analysis of Algorithms (slide 6 to 6-11) [ONLINE] Live SpeedTest.py (vs cpp or java) demo (measure runtime, count # of operations, vs asymptotic analysis) Kattis problems discussed today: thanos (Analysis: exponential growth, logarithmic steps) |
T01+L01: it5003lab1.pdf Introduction, Algorithm Analysis, SpeedTest.py mods, PS0a and PS0b review, Hands-on: vaccineefficacy (1D or 2D list/array processing) PS1 Discussion (algorithmic) |
PS0b: Easy Python/coding challenges Due: Wed, 01 Mar 23, 07.59pm (0.5% — to speed up admins) PS1: Basic Python Out: Wed, 01 Mar 23, 08.00pm Easier subtasks showcased live during the first lecture |
|
08, Session 2 08+11 Mar |
Reminder: Read sorting e-Lecture slides before Lecture 2a At least until slide 11-11, preferably more 2a. Sorting (Slide 1 to 11-11) (Re-)Introducing simpler but O(N^2) Sorting Algorithms + O(N log N) Merge Sort SortingDemo.py (O(N^2) versions + O(N log N) Merge Sort) Python list, list.sort(), or sorted(list) Kattis problems discussed today: nothanks (NEW: Python list.sort() or sorted(list) and linear pass), mjehuric (review Bubble sort), height (review Insertion sort) Last flipped classroom reminder: Read most sorting e-Lecture slides before Lecture 2c 2b. Recitation: Analysis of Algorithms and Sorting Extra QnA session on anything about Algorithm Analysis Extra QnA session on anything about sorting, e.g., touching on Counting Sort, or other potential applications of sorting Kattis problems discussed today: sortofsorting (NEW: custom comparator, Python list.sort() is stable) lineup (extra O(N log N) vs O(N) exercise) 2c. Sorting (Slide 11 to 13-2 and 17 to end; but skipping Slide 14 to 16-2) O(N log N) Merge Sort Fast Review Introducing O(N^2) non-randomized Quick Sort Introducing expected O(N log N) Randomized Quick Sort (no analysis) SortingDemo.py (O(N log N) Merge Sort + expected O(N log N) Randomized Quick Sort) Other topics of sorting e-Lecture Sorting Online Quiz (medium) |
T02+L02: it5003lab2.pdf Sorting Application(s), Sorting Algorithms Review via mini experiment, PS1 Quick Debrief, VA OQ demo (sorting), Hands-on: judging (multiset intersection; greedy bipartite matching; modified merge routine (other solution exists)), PS2 Discussion (algorithmic) |
PS1: Basic Python Due: Wed, 08 Mar 23, 07.59am (2.5%) PS2: Sorting Problems Out: Wed, 08 Mar 23, 08.00am |
|
09, Session 3 15+18 Mar |
3a. List ADT: Array vs SLL, Stack & Queue ADT (Slide 1 to 5-6) 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 Introducing Queue ADT Python list as queue (dequeue/pop(0) is slow) SLLDemo.py revisited (custom Queue, fast enqueue+dequeue) 3b. Recitation: List Extra QnA session on anything about List, e.g., a few other ways to implement Linked List, the art to actually avoid using Linked List, etc. Kattis problems discussed today: throwns (NEW: application of Stack ADT; modulo) 3c. DLL and Deque ADT, Queue again (Slide 6 to end) Detour to Doubly Linked List (DLL) and Deque ADT Python deque for Queue ADT (fast) Linked List Online Quiz (medium) |
T03+L03: it5003lab3.pdf SLL/Stack/Queue Review via mini experiment, Additional classic list operations, Python implementations for list, stack, and queue (deque), PS2 Quick Debrief, VA OQ demo (list), Hands-on: integerlists (interesting list problem; pop(0)?, reverse?) PS3 Discussion (algorithmic) |
PS2 Due: Wed, 15 Mar 23, 07.59am (3%) PS3: List Problems Out: Wed, 15 Mar 23, 08.00am |
|
10, Session 4 22+25 Mar |
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3) Introducing PQ ADT Introducing basic Binary Heap structure and operations BinaryHeapDemo.py Python heapq See priority_queue.py at GitHub repo of CPbook website O(N log N) Heapify/Create Heap first O(N log N) Heap sort first 4b. Recitation: Priority Queue Extra QnA session on anything about PQ, e.g., The extra PQ/Binary Heap operations. Mock VA OQ 1 (medium level only) Kattis problems discussed today: rationalsequence3 (combo DS: pq+stack) 4c. Priority Queue (PQ) (to end) O(N) Heapify/Create Heap O(N + K log N) partial sort vs other sorting algorithms Kattis problems discussed today: TBA VisuAlgo Online Quiz 1 (11%) First 3 topics of IT5003: sorting, list, heap (only a bit), with a few new questions 9.30-9.45am, onsite at COM1-0206 (SR1) Bring your own laptop |
T04+L04: it5003lab4.pdf PQ ADT/Binary Heap Review, Max-Min PQ conversion (numbers only), PS3 Quick Debrief, VA OQ demo (heap), Hands-on: TBA PS4 Discussion (algorithmic) |
PS3 Due: Wed, 22 Mar 23, 07.59am (3%) PS4: PQ Problems Out: Wed, 22 Mar 23, 08.00am |
|
11, Session 5 29 Mar+01 Apr |
5a. Table ADT: Hash Table (Slide 1 to 7-11 and 10 to end, but skipping Slide 8 to 9-4) Table ADT Direct Addressing Table (DAT) Basic Hashing Concepts Collission Resolution Techniques: Separate Chaining vs Linear Probing HashTableDemo.py Python set, dict, defaultdict, or Counter See unordered_map_unordered_set.py at GitHub repo of CPbook website Kattis problems discussed today: TBA 5b. Recitation: More PQ + HT A bit more PQ, A review of basic HT concepts (SC, LP), A bit more HT, e.g., QP, DH, etc, PQ plus HT combo, Kattis problems discussed today: TBA 5c. Table ADT part 2: Binary Search Tree (Slide 1 to 11) Presenting alternative Table ADT: BST BSTDemo.py Short exposure about self-balancing trees No built-in library for Python BST Online Quiz (medium) NUS Online Teaching Feedback opens this Fri But this timing is too early for our course... You can wait until our 8th/last week |
T05+L05: it5003lab5.pdf Table ADT Review, Basic Hashing Concepts, Hash Table Issues, Quick BST Review, PS4 Quick Debrief, VA OQ demo (hashtable,bst), Hands-on: TBA PS5 Discussion (algorithmic) |
PS4 Due: Wed, 29 Mar 23, 07.59am (3%) PS5: (Hash) Table Problems Out: Wed, 29 Mar 23, 08.00am |
|
12, Session 6 05+08 Apr |
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 problems discussed today: TBA Thu, 06 Apr 2023 is chosen as NUS well being day S2 AY 2022/23 Then, we have Good Friday PH on Fri, 07 Apr 2023 Thus recitation 6b is cancelled and merged with 7b But Sat, 08 Apr 2023 classes remain as per normal (apology in advance for this, rescheduling lecture 6c and Sat lab sessions at other times are impossible) 6c. Graph Traversal + Simple Applications (Slide 1 to 7-1) Introducing Graph Traversal Algorithms, 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 problems discussed today: TBA |
T06+L06: it5003lab6.pdf Graph DS Review, Create DAG, Graph DS Conversion Exercise, Graph Modeling exercise 1, DFS/BFS Review 1, PS5 Quick Debrief, VA OQ demo (graphds,dfsbfs), Hands-on: TBA PS6 Discussion (algorithmic) |
PS5 Due: Wed, 05 Apr 23, 07.59am (3%) PS6: Graph DS+Traversal Problems Out: Wed, 05 Apr 23, 08.00am |
|
13, Session 7 12+15 Apr |
7a. Graph Traversal continued (Slide 7-2 to 7-11) DFS/BFS Online Quiz (medium), Kattis problems discussed today: TBA 7b. Recitation: (Balanced) BST + Graph 1 Review of BST, plus the non-examinable balanced BST Extra QnA session on anything about graph, Review of Graph DS and Graph Traversal i.e., graph ds (implicit graph), graph traversal (especially cyclic test and toposort), Kattis problems discussed today: TBA COM1-2-SR1 will be prepped for UG final assessment venue by this weekend; therefore for 7b, 8a, and recitation 8b, we will be moved to iCube-Auditorium 7b. Single-Source Shortest Paths (SSSP) Problem (Slide 1 to 2; then BFS: slide 5 to 6-3) Introducing SSSP Problem BFS Review for unweighted cases (you have seen this on Lecture 6b/7a) No built-in Python algorithm, see bfs.py at GitHub repo of CPbook website, Preview of Modified Dijkstra's (to be discussed in more details next Wed), Kattis problems discussed today: TBA |
T07+L07: it5003lab7.pdf DFS/BFS Review 2, SSSP Review 1, Graph Modeling exercise 2, PS6 Quick Debrief, VA OQ demo (dfsbfs), Hands-on: TBA PS7 Discussion (algorithmic) |
PS6 Due: Wed, 12 Apr 23, 07.59am (3%) PS7: Graph Traversal+SSSP Problems Out: Wed, 12 Apr 23, 08.00am |
|
Reading, Session 8 19+22 Apr |
8a. Single-Source Shortest Paths (SSSP) Problem (Modified Dijkstra's: slide 8 to 8-5) Introducing (Modified) Dijkstra's Algorithm Introducing SSSP on DAG (involving toposort/bottom-up DP) No built-in Python algorithm, see dijkstra.py at GitHub repo of CPbook website, SSSP Online Quiz (medium), Kattis problems discussed today: TBA Course wrap up VisuAlgo Online Quiz 2 (12%) All topics of IT5003, with a few new questions We may need to go beyond 8.30pm tonight As we don't have lecture 8.c... Details TBC 8b. e-Recitation: Semester Recap + a bit of NP-completeness Extra QnA session on anything about IT5003 topics Focus on SSSP first, BFS for unweighted graph, Modified Dijkstra's for non-negative weighted graph, effect of negative weights, other special cases of SSSP problems, etc. Showing the limit of computation: Introduction to the theory of NP-completeness Kattis problems discussed today: TBA NUS Online Teaching Feedback closes on Friday of Study Week We have Hari Raya Puasa PH on Sat, 22 Apr 2023 Thus the last Sat lecture 8.c is cancelled And Sat lab groups are encouraged to attend any of the last Mon session on Mon, 24 Apr 2023 (recorded) |
Lab08 is only for Mon, 24 Apr 2023 T08+L08: it5003lab8.pdf SSSP Review 2, Graph Modeling exercise 3, Hands-on: Just do PS8 in-class until end. (there may be extras for those who have completed PS8) Lab participation marks given (3%) |
PS7 Due: Wed, 19 Apr 23, 07.59am (3%) PS8: Weighted SSSP Problems Out: Wed, 19 Apr 23, 08.00am |
|
"Study Window", 26 Apr-03 May 2023 Final Assessment Consultations (per request) Final Assessment Past Papers: AY 2020/21: S1-final.pdf, S2 (A/P Soo Yuen Jien, N/A), AY 2021/22: S1-final.pdf, S2-final.pdf. AY 2022/23: S1-final.pdf (most recent past paper); S2-final.pdf (obviously N/A yet). |
PS8 Due: Wed, 26 Apr 23, 07.59am (3%) |
||
|
Final Assessment (50%) Date and Time: Thu, 04 May 2023, 5-7PM Venue: TBC (but it will be an onsite F2F final assessment) X% MCQs (tricky); Y% easier essay; Z% differentiator questions |
|||