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 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 seventh time Prof Halim teaches this 8-weeks (+ 1.5 weeks more before final assessment) IT5003 course for MComp General Track — the main group of students — (plus a bit of other MComp specializations: Digital Financial Technology + Biomedical Informatics) and also a few (usually around 30-ish) Graduate Certificates in Computing Foundations (GC-CF). Prof Halim sets IT5003 (in Python) as a 'subset' (obviously, as we only have 8-weeks) of his full 13-weeks CS2040S Undergraduate version of similar course. The previous iterations were already (very) good. One thing to take note is that Prof Halim'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.
For S2 AY23/24, Prof Halim has prepared for a [126-150]-ish class size with all onsite components.
As of 05 Apr 2024, the fifth week of the class, the class roster is 123, slightly lower than predicted.
Some other facts:
Rating (out of 5.0) |
Mar-May 24 (n=??/123) ≥ 50%? |
Oct-Dec 23 (n=82/200) 41% ▼ |
Mar-May 23 (n=61/115) 53% ▼ |
Oct-Dec 22 (n=100/178) 56% ▼ |
Mar-May 22 (n=57/99) 58% ▼ |
Oct-Dec 21 (n=83/130) 63% ▲ |
---|---|---|---|---|---|---|
Course feedback (SoC avg lvl 5000 ~4.1) | ≥ 4.3 (target) | 4.3 ▼ | 4.5 ▲ (PB) | 4.4 == | 4.4 ▲ | 4.3 ▲ |
Course difficulty (SoC avg lvl 5000 ~3.6) | ≤ 3.8 (lower a bit) | 3.9 == | 3.9 == | 3.9 == | 3.8 ▼ | 3.5 ▼ (PB) |
Prof Halim's teaching (SoC avg lvl 5000 ~4.3) | ≥ 4.5 (target) | 4.3 ▼ | 4.6 == (PB) | 4.6 == (PB) | 4.6 ▲ (PB) | 4.5 ▲ |
Date, Time | Live Session (Venue) (#Stu/#Cap) | No | Tutor |
---|---|---|---|
a/Sat, 1010-1210 | COM1-01-20 (PL6) (24/23) | B1 | Prof Halim |
a/Sat, 1000-1200 | COM4-WSLab1 (19/23) | B4 | Ritul |
a/Sat, 1000-1200 | COM4-WSLab2 (19/23) | B5 | Wen Jun |
a/Sat, 1000-1200 | COM4-WSLab3 (18/23) | B6 | Dominic |
b/Mon, 1400-1600 | COM1-B1-12 (PL1) — for full-time MComp students (24/23) | B2 | Jeanette |
c/Mon, 1600-1800 | COM1-B1-12 (PL1) — for full-time MComp students (19/23) | B3 | Chia Geng |
List of TAs for Mar-May 2024:
This is what you will learn in IT5003 as taught by Prof Halim:
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 7 of S2 AY 2023/24 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
Date | News |
---|
The S2 AY 2023/24 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 | |||
-02 |
Not started, but please revise your CS1010/IT5001 Prof Halim assumes that all of you have taken or exempted from this course/its variants, i.e., you can code in Python 3 Register at Kattis (use full name as in Matric card), read Kattis knowledge base if you are new with this judge, and solve the selected optional Online Judge (OJ) Problem Set 0 (PS0) by yourself (CS1010/IT5001 level): (solving many 'trivial (many one-liner) problems' from this set ---trackable by Prof Halim, indirectly tells him about your CS1010/IT5001 rough grade) |
Not Started |
PS0: Easy Python/coding challenges Out: Wed, 21 Feb 24, 08.00am (already graded) |
-01, Bef Wed, 06 Mar |
Not Started, continue doing PS0 if you have not solved at least 3... This is a useful practice for those also taking IT5001 (ending soon) |
Not Started |
PS0: Easy Python/coding challenges (already graded) |
07, Session 1 06+09 Mar |
1a. Course Admin, (Re-)Introduction to Python Setting the tone for a flipped classroom but all ONSITE course VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open) Basic Python review/new feature introduction VisuAlgo Online Quiz 0 (1% — to speed up admins) There will be just 1 very trivial fill-in-the-blank question We do this between 6.45-7.15pm during Lecture 1a Bring your own laptop r1. Recitation: Basic Python Extra QnA session on Basic Python, discussion of more/alternative Python features, review PS0: Easy Python/coding challenges tasks Kattis problems discussed today: sifferprodukt (review simple function) coffeecupcombo (review 1D array/list) babypanda (backwards solve; binary number) basicprogramming1 (somewhat IT5001 review) Reminder: Read summary on algorithm analysis before Lecture 1c 1b. Analysis of Algorithms (slide 6 to 6-11) 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) Reminder: Read sorting e-Lecture slides before Lecture 2a At least until slide 11-11, preferably more Sat, 09 Mar 2024 PM is IT5001 final assessment time for many IT5003 students. All the best. |
T01+L01: it5003lab1.pdf Introduction, Algorithm Analysis, SpeedTest.py mods, PS0 review, Hands-on: vaccineefficacy (1D or 2D list/array processing) PS1 Discussion (algorithmic) |
PS1: Basic Python Out: Wed, 06 Mar 24, 08.00am PS0: Easy Python/coding challenges Due: Wed, 06 Mar 24, 07.59pm (solve any 3 → 1% — to speed up registration admins) |
08, Session 2 13+16 Mar |
2a. Sorting (Slide 1 to 11-11) Start with a simple problem involving sorting (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), sortofsorting (NEW: custom comparator, Python list.sort() is stable) r2. 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: magicsequence (up to counting sort; not the full solution) Last flipped classroom reminder: Read most sorting e-Lecture slides before Lecture 2c 2b. 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) Sat, 16 Mar 2024 is also SGP NOI 2024 Onsite Final We had to release our Sat lab bookings B4/B5/B6/B1 went to COM1-02-16/14/SR5/SR@LT19, respectively PS: Prof Halim was very distracted during this morning... (Jeanette has covered this session) |
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, 13 Mar 24, 07.59am (1%) PS2: Sorting Problems Out: Wed, 13 Mar 24, 08.00am |
09, Session 3 20+23 Mar |
3a. List ADT: Array vs SLL, Stack & Queue ADT (Slide 1 to 5-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 Introducing Queue ADT Python list as queue (dequeue/pop(0) is slow) SLLDemo.py revisited (custom Queue, fast enqueue+dequeue) r3. Recitation: List Extra QnA session on anything about List, e.g., a few other ways to implement Linked List, Kattis problems discussed today: throwns (NEW: application of Stack ADT; modulo) 3b. 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, 20 Mar 24, 07.59am (2%) PS3: List Problems Out: Wed, 20 Mar 24, 08.00am |
10, Session 4 27 Mar only |
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to end) Introducing PQ ADT (fast) Introducing basic Binary Heap structure and operations (fast) BinaryHeapDemo.cpp | py | java Python heapq See priority_queue.py at GitHub repo of CPbook website Max-Min PQ conversion (numbers only) O(N log N) Heapify/Create Heap + O(N log N) Heap sort (fast) O(N) Heapify/Create Heap O(N + K log N) partial sort vs other sorting algorithms Shelved to r5: VisuAlgo Online Quiz 1 (10%) First 2 topics of IT5003: sorting and list only, with a few new questions total 10 hard+2 new questions 8.15-8.30pm, onsite Bring your own laptop Thu, 28 Mar 2024 is chosen as NUS well-being day S2 AY 2023/24 This is just before Fri, 29 Mar 2024 Good Friday PH Thus, recitation r4 is cancelled Also, we do not have a session on Sat, 30 Mar 2024 (hence, the maximized Wed, 27 Mar 2024 session) Prof Halim was in Jakarta this weekend Also, NUS Online Teaching Feedback opens this Fri But this timing is too early for our course... You can wait until our 8th/last week |
T04+L04: it5003lab4.pdf PQ ADT/Binary Heap Review, PS3 Quick Debrief, VA OQ demo (heap), Hands-on: knigsoftheforest (careful max-PQ simulation), PS4 Discussion (algorithmic) PS: This lab4 is only live for Monday groups Saturday groups will watch the recording For Saturday groups, review one of Monday group recording |
PS3 Due: Wed, 27 Mar 24, 07.59am (2%) PS4: PQ Problems Out: Wed, 27 Mar 24, 08.00am |
11, Session 5 03+06 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: Linear Probing vs Separate Chaining HashTableDemo.cpp | py | java (all use SC) Python set, dict, defaultdict, or Counter See unordered_map_unordered_set.cpp | py | java at GitHub repo of CPbook website Kattis problems discussed today: grandpabernie (Python defaultdict/hashtable example) r5. Recitation: More PQ + HT A review of basic HT concepts (SC, LP), A bit more HT, e.g., QP, DH, etc, PQ plus HT combo, Mock VA OQ 2 (medium level only, without bst yet), Kattis problems discussed today: variabelnamn (Python set/dict/DAT example) 5b. Table ADT part 2: Binary Search Tree (Slide 1 to 11) Presenting alternative Table ADT: BST BSTDemo.cpp | py | java Short exposure about self-balancing trees No built-in library for Python BST Online Quiz (medium) |
T05+L05: it5003lab5.pdf One more Binary Heap question, Table ADT Review, Basic Hashing Concepts, Hash Table Issues, Quick BST Review, PS4 Quick Debrief, VA OQ demo (hashtable,bst), Hands-on: shoppinglist (set intersectionS; easy with Python; or using Counter), PS5 Discussion (algorithmic) |
PS4 Due: Wed, 03 Apr 24, 07.59am (2%) PS5: (Hash) Table Problems Out: Wed, 03 Apr 24, 08.00am |
12, Session 6 13 Apr only |
Wed, 10 Apr 2024 is Hari Raya Puasa PH Thus, L6a is cancelled But Prof Halim needs to use r6 (recorded) and 6b to catch up r6. Recitation: HT+BST+balanced BST Review of HT Review of BST, plus balanced BST (can quote 'assume BST is balanced' in final) Prof Halim will use the 2nd half of r6 to do 6a Start of 6a. Graph DS lecture (recorded) Introducing Graph Theory and special graphs Introducing Graph Data Structures (fast) 6b. Graph DS Applications (read ALL slides) Fast recap of what was mentioned during r6 No built-in C++ STL container | Python standard library | Java API, See graph_ds.cpp | py | java at GitHub repo of CPbook website, VisuAlgo Online Quiz 2 (10%) Next 3 topics of IT5003: heap, hashtable, bst only, [ total 9.30-9.45am, onsite Bring your own laptop Prof Halim attended the re-scheduled ICPC World Finals 22+23 at Luxor, Egypt (that has been postponed for 1.5+0.5 year(s), respectively) He has recorded 7a this evening Before he flew to Egypt on Sat, 13 Apr night [RECORDING] 7a. Graph Traversal (Slide 1 to 7-11) Introducing Graph Traversal Algorithm: DFS No built-in C++ STL algorithm | Python standard library | Java API, See dfs_cc.cpp | py | java, Continuing with BFS See UVa00469.cpp | py | java, and bfs.cpp | bfs.py | java at GitHub repo of CPbook website, DFS/BFS Online Quiz (medium), Kattis problems discussed today: wheresmyinternet (reachability test; DFS+BFS) reachableroads (DFS/BFS, count #CC) amoebas (modified DFS called 'floodfill'/finding CC variant, implicit 2d grid graph) |
T06+L06: it5003lab6.pdf Graph DS Review, Graph DS Conversion Exercise, Graph Modeling exercise 1, PS5 Quick Debrief, VA OQ demo (graphds), Hands-on: popularitycontest (simple graph DS or just count degree of vertices), PS6 Discussion (algorithmic) |
PS5 Due: Wed, 10 Apr 24, 07.59am (2%) PS6: Graph DS+Traversal 1 Out: Wed, 10 Apr 24, 08.00am |
13, Session 7 17+20 Apr |
[RECORDING] 7a. Graph Traversal (Slide 1 to 7-11) See the recording No live class at LT8 [Online+Live from Luxor] 7b first then short r7 We did this live (using Zoom) from Luxor, but I started with 7b first before short r7, [RECORDING] 7b. Single-Source Shortest Paths (SSSP) Problem (Slide 1 to 2; then BFS: slide 5 to 6-3) Introducing the SSSP Problem BFS Review for unweighted cases (you have seen this on Lecture 6b/7a) Preview of Modified Dijkstra's (to be discussed in more details next Wed), Kattis problems discussed today: horror (implicit graph, unweighted SSSP, BFS) oceancurrents (the special case first; from past paper) Prof Halim was stuck at Cairo when DXB Airport closed for inbound flights (that flooding case) He and NUS teams eventually detoured Cairo-Jakarta-Singapore and arrived half day later (Sun, 21 Apr) Jeanette has covered his B1 lab again |
T07+L07: it5003lab7.pdf DFS Review, BFS/unweighted SSSP Review, Graph Modeling exercise 2, PS6 Quick Debrief, VA OQ demo (dfsbfs), Hands-on: builddeps (AL of strings; toposort variant), PS7 Discussion (algorithmic) |
PS6 Due: Wed, 17 Apr 24, 07.59am (2%) PS7: Graph DS+Traversal 2 Out: Wed, 17 Apr 24, 08.00am |
Reading, Session 8 24+27 Apr |
All sessions on reading week will be at COM1-02-SR1 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) + on Tree (DFS/BFS) See dijkstra.cpp | py | java at GitHub repo of CPbook website SSSP Online Quiz (medium), Kattis problems discussed today: shortestpath1 (that (Modified) Dijkstra's implementation is easy) crosscountry (another easy weighted SSSP problem on complete weighted graph) Last few words (need to extend a bit to 8.45pm for this) r8. Recitation: SSSP Extra QnA session on anything about IT5003 topics but focusing more on graph-related questions from past papers NUS Online Teaching Feedback closes on Friday of Study Week 8b. [Optional] NP-complete (but compulsory VA OQ 3) Showing the limit of computation: Introduction to the theory of NP-completeness First 25 minutes only VisuAlgo Online Quiz 3 (10%) Next 3 topics of IT5003: graphds, dfsbfs, sssp only, [graphds: all questions currently in the hard mode are examinable], [dfsbfs: SCC, cut-vertex, etc questions are removed], [sssp: Bellman-Ford and negative weight questions are removed], total 10 hard+2 new questions 9.30-9.45am, onsite Bring your own laptop |
T08+L08: it5003lab8.pdf SSSP Review 2 (weighted), Graph Modeling exercise 3 (from past papers), Hands-on: Just do PS8 in-class until end. or Hands-on: TBA (for those who have completed PS8) Lab participation marks given (3%) |
PS7 Due: Wed, 22 Nov 23, 07.59am (2%) PS8: Weighted SSSP Problems Out: Wed, 22 Nov 23, 08.00am |
"Study Window", 30 Apr-08 May 2024 Final Assessment Discussions at Class Discord Final Assessment Past Papers (recent 3 AYs only): AY 2021/22: S1-final.pdf, S2-final.pdf, AY 2022/23: S1-final.pdf, S2-final.pdf, AY 2023/24: S1-final.pdf, S2-final.pdf (will be our paper; should be another step easier than last semester as Prof Halim reduces graph questions this time). |
PS8 Due: Wed, 01 May 24, 07.59am (2%) |
||
Make-up slot for VA OQ 1 (1 pax), OQ 2 (6 pax), and OQ 3 (≥ 3 pax) Date and Time: Thu, 09 May 2024, 3.30-4.00pm Venue: TBA Final Assessment (50%) Date and Time: Thu, 09 May 2024, 5-7pm Venue: MPSH6 Open book but *not* Open Laptop (prepare accordingly) Non-programmable calculator is allowed (as with Online Quiz), but won't be that useful 40 → 50% MCQs (but extremely tricky); I use my own OCR form (the MCQs are there to speed up grading as Prof Halim (solo grader: 1 versus 123) has to submit marks by 2 → 4 short questions (20 → 30% --- do not lose too many marks here), and 2 → 1 essay (20%, as this semester, we lost too many valuable contact hours on r4, 4b, 6a, 7a, r7, 7b) |