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, heap, hash tables, 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.
We use very basic object-oriented programming concepts in various data structures implementations, e.g., Stack class inherits LinkedList class.
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.
* Since S1 AY 2024/25, IT5003 is now a full 12-weeks course (6-weeks in the first half + recess (to catch up) + 6-weeks in the second half) instead of the true accelerated 8-weeks (week 7-reading week) after students finish IT5001.
This is the going to be the ninth time Prof Halim teaches this 12-weeks IT5003 course for MComp General Track (GT) — the main group of students — (plus a bit of other MSc degree specializations: Digital Financial Technology (DFT) + Biomedical Informatics (BMI) + NEW: Industry 4.0) and also a few (usually around [20..30]-ish) Graduate Certificates in Computing Foundations (GC-CF). Prof Halim sets IT5003 (in Python) as a 'subset' (obviously, as we only have 12-weeks of 2 hours/week) of his full 13-weeks of 3 hours/week 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 AY 2024/25, Prof Halim expects up to ~200+ IT5001 S1 AY 2024/25 students to join IT5003 in S2 AY 2024/25.
(Last) update on 24 Jan 25: We now have N=146 students today.
Some other facts:
| Rating (out of 5.0) |
Jan-May 25 (n≥29/146) ≥20% |
Aug-Nov 24 (n=19/33) 58% ▲ |
Mar-May 24 (n=66/122) 54% ▲ |
Oct-Dec 23 (n=82/200) 41% ▼ |
Mar-May 23 (n=61/115) 53% ▼ |
Oct-Dec 22 (n=100/178) 56% ▼ |
|---|---|---|---|---|---|---|
| Course feedback (SoC avg lvl 5000 ~4.1) | [4.3..4.4] (tgt) | 4.3 == | 4.3 == | 4.3 ▼ | 4.5 ▲ (PB) | 4.4 == |
| Course difficulty (SoC avg lvl 5000 ~3.6) | [4.0..4.1] (tgt) | 4.2 == (uh oh) | 4.2 ▲ (uh oh) | 3.9 == | 3.9 == | 3.9 ▲ |
| Prof Halim's teaching (SoC avg lvl 5000 ~4.3) | [4.4..4.5] (tgt) | 4.6 ▲ | 4.4 ▲ | 4.3 ▼ | 4.6 == (PB) | 4.6 == (PB) |
| Date, Time | Live Session (Venue) (#Stu/#Cap) | No | TA |
|---|---|---|---|
| a/Sat, 1000-1200 | COM1-0120 (PL6) — for part-time students (14/20) | B1A | @.myrcella. |
| a/Sat, 1000-1200 | COM4-02-03 (WSLab1) — for part-time + outbidded full-time students (9+(1)=10/20) | B1B | @saddle196883 |
| a/Sat, 1000-1200 | COM4-02-05 (WSLab2) — for part-time + outbidded full-time students (10/20) | B1C | @wenjun8942 |
| a/Sat, 1000-1200 | COM4-02-04 (WSLab3) — for part-time students (17/20) | B1D | @prof_halim |
| b/Mon, 1400-1600 | COM1-B112 (PL1) — for full-time students (23/23) | B2A | @loveandbejoyful |
| b/Mon, 1400-1600 | COM1-B109 (PL2) — for full-time students (25/25) | B2B | @pallon_fm |
| b/Mon, 1600-1800 | COM1-B112 (PL1) — for full-time students (24/24) | B3A | @loveandbejoyful |
| b/Mon, 1600-1800 | COM1-0120 (PL6) — for full-time students (23/23) | B3B | @hao_yi |
List of TAs for Jan-May 2025:
This is what students learn in IT5003 as taught by Prof Halim, compare it with the superset CS2040S version:
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 1 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
| Date | News |
|---|
The S2 AY 2024/25 timetable below is still tentative, especially those that are highlighted with pink color.
| Week | Tutorial+Lab Combo | Lecture | 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 | |||
|
-01, 30 Dec-03 Jan |
Has Not Started |
Has Not Started, but please revise your CS1101S/IT5001/equivalent Prof Halim assumes that all of you have taken or exempted from this course/its variants Register at Kattis (use full name as in Matric card), read Python specific instructions @ Kattis, pick up basic Python by yourself, and solve the selected Online Judge (OJ) Problem Set 0 (PS0) by yourself (CS1101S/IT5001/equivalent level) (solving many 'trivial problems' from this set ---trackable by Prof Halim, indirectly tells him about your CS1101S/IT5001/equivalent rough grade) |
PS0: Easy Coding Challenges (02-15 Jan) Already graded to speed up registration admins Solve any 3 out of 10 trivial tasks for 1% |
|
00, 06-10 Jan |
Has Not Started |
Has Not Started Continue attempting PS0 (hints in class Discord) |
PS0, continued Remember, solve any 3 for 1% |
|
01, 13-17 Jan |
Has Not Started |
01a. Course Admin, (Re-)Introduction to Python Setting the tone for a flipped classroom course VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open) Basic Python review/new feature introduction Kattis problem(s) discussed today: A few PS0 tasks (just for warm-up) In the middle of 01a: VisuAlgo Online Quiz 0 (1%) There will be 1 trivial question during the first lecture Bring your own laptop This one is put here to speed-up admins (don't skip the first lecture) Reminder: Read simple algorithms on unsorted array (Slide 1 to 6-1) before the next lecture Reminder: Read sorting intro, algorithm analysis, and O(N^2) sorting algorithms (Slide 1 to 9-3) before the next lecture |
PS0 (1%) Due: Wed, 15 Jan 25, 07.59pm PS1: Basic Programming Out: Wed, 15 Jan 25, 08.00pm Mentioned at the end of the first lecture IT5003 students do problem A+B problem C is optional (extra challenge) |
|
02, 20-24 Jan |
Saturday sessions start from this Week 02 see T01+L01: tut01.pdf below |
02a. Analysis of Algorithms (Slide 1 to 9-3) Live SpeedTest.cpp | py | java demo (measure runtime, count # of operations, vs asymptotic analysis) Fast review of O(N^2) sorting algorithms Kattis problem(s) discussed today: thanos (analysis: exponential growth, logarithmic steps) mjehuric (bubble sort simulation) height (insertion sort simulation) nothanks (sorting library and linear pass) At the end of 02a: VisuAlgo Online Quiz 0 (make-up) (1%) There will be another 1 trivial question (not the same as last week) Bring your own laptop Only for those who really absent for the first lecture (for legit reasons) Last flipped classroom reminder: Read all sorting e-Lecture slides before next lecture |
We defer PS1 end time to before CNY 2025, and PS2 start time to after CNY 2025 |
|
03, 27-31 Jan |
T01+L01: tut01.pdf Introduction, OOP review (List ADT, ListArrayTest.py | java) Algorithm Analysis, Hands-on, a basic List ADT task, PS1 Debrief (short), PS2 Discussion (algorithmic) |
No class due to Chinese New Year 2025 CNY Eve: 28 Jan 2025 PM (Tue) Day 1: 29 Jan 2025 (Wed) Day 2: 30 Jan 2025 (Thu) |
PS1 (2%) Due: Mon, 27 Jan 25, 11.59pm (a few hours after the first Mon tut01) PS2: Sorting-related Problems Out: Sat, 01 Feb 25, 08.00am (after CNY) |
|
Live preview of one of (Randomized) Quick Sort Click "Play (▷)" |
|||
|
04, 03-07 Feb |
No lab/tut this week Due to CNY 2025 (no new lecture topic on Wed, 29 Jan) |
03a. Sorting (Slide 10 to 13-2) O(N log N) Merge Sort algorithm (Java Collections.sort; Python list.sort) Expected O(N log N) (Rand) Quick Sort algorithm (C++ sort; Java Arrays.sort (primitives)) See the details at SortingDemo.cpp | py | java Python list, list.sort(), or sorted(list) Sorting Online Quiz (medium) Kattis problem(s) discussed today: sortofsorting (custom comparator, stable sorting library) |
PS2, continued |
|
05, 10-14 Feb |
T02+L02: tut02.pdf Sorting Application(s), Sorting, mini experiment, QuickSelect, ADT/List ADT, VA OQ demo (sorting), Hands-on, sorting applications, PS2 Discussion (algorithmic) |
04a. List ADT: SLL/Stack/Queue/DLL/Deque (all slides) Introducing List ADT, (resizeable) array versus SLLDemo.cpp | py | java implementation Introducing Stack ADT and MyStack implementation (extension of SLLDemo) Stack, but using (resize-able) Array implementation, i.e., Python list as stack Introducing Queue ADT and MyQueue implementation (another extension of SLLDemo) DLL and Deque ADT (Fixed-size) Python list as queue, circular list, versus Python deque as queue Linked List Online Quiz (medium) A few other LL technicalities Kattis problem(s) discussed today: delimitersoup (classic bracket matching variant; use a stack/LIFO) |
PS2 (2%) Due: Sat, 15 Feb 25, 07.59am PS3: List+PQ Problems Out: Sat, 15 Feb 25, 08.00am |
|
Live preview of one of Binary Heap operation: Heap Sort (in-place) Click "Play (▷)" |
|||
|
06, 17-21 Feb |
T03+L03: tut03.pdf Linked List, mini experiment, Applications: Reversing/Sorting a List, Application: Stack-related, PS2 Debrief (short), Python list/deque, VA OQ demo (list), Hands-on, a list application, PS3 Discussion (algorithmic) PS: Sat sessions run tut04.pdf on Sat, 22 Feb 25 B1A (PL6) temporarily moves to SR@LT19 (clash with SGP NOI 2025 Prelim) |
05a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-2) Introducing PQ ADT Introducing basic Binary Heap structure and its Insert+ExtractMax operations Discussing CreateHeap (two versions) and HeapSort operations BinaryHeapDemo.cpp | py | java Python heapq; see priority_queue.cpp | py | java at GitHub repo of CPbook website Last 20m of 05a: VisuAlgo Online Quiz 1 (11%) Bring your own laptop that can run at least 20 minutes on battery power. (we do not provide any spare laptop). Material: /array (1Q + 3 'new'), /sorting (4 Qs), /list (4 Qs), and 4 'new' questions especially on asymptotics. |
PS3, continued |
|
Recess Week, 22 Feb-02 Mar 2025 You can take a break this week :) Prof Halim and his (international) organizing (host/judge/technical) team organized the second ICPC Asia Pacific Championship, 27 Feb-02 Mar 2025 It went well and NUS team Jägermeister clinched 2nd place (gold medal) |
|||
|
07, 03-08 Mar |
T04+L04: tut04.pdf Binary Heap, Max-Min conversion, Additional ADT PQ Operations, Python heapq, VA OQ demo (heap), Hands-on, a simple problem involving PQ, PS3 last Discussion (algorithmic) |
06a. Table ADT part 1: Hash Table (slide 1 to 10-5) Table ADT and DAT Basic Hashing Concepts Easiest Collision Resolution Technique: CA (SC) Another Collision Resolution Technique: OA (LP) More Collision Resolution Techniques: OA (QP and DH) Comparing CA: SC with OA: DH Other technicalities of Hash Table Hash Table Online Quiz (easy; a bit too tedious on medium/hard settings) |
PS3 (2%) Due: Mon, 03 Mar 25, 11.59pm (a few hours after Mon tut04) PS4: Hash Table Problems Out: Tue, 04 Mar 25, 08.00am |
|
08, 10-14 Mar |
T05+L05: tut05.pdf Table ADT 1 - unordered, Basic hashing concepts, Hash Table issues, Python set, dict, defaultdict, Counter PS3 Debrief (short), VA OQ demo (hashtable), Hands-on, a hash table application, PS4 Discussion (algorithmic) |
07a. Table ADT part 2: BST (Slide 1 to 12-1) BST concepts and the various BST operations The multiset idea BST (only) Online Quiz (medium) BSTDemo.cpp | py | java Randomly built BST and a preview of balanced BST, e.g., AVL Tree |
PS4 (2%) Due: Sat, 15 Mar 25, 07.59am PS5: Graph DS + Traversal Problems Out: Sat, 15 Mar 25, 08.00am |
|
09, 17-21 Mar |
T06+L06: tut06.pdf Table ADT 2 - ordered, (balanced) BST advanced stuffs: multiset, select/rank, PQ ADT alternative implementation, Comparison with Table ADT 1: unordered vs ordered, The issue of no equivalent Python standard library, PS4 Debrief (short), VA OQ demo (bst) Hands-on, a combo DS task, PS5 Discussion (problemset preview only) |
08a. Graph DS (all slides) + DFS Traversal (Slide 1 to 5-8) Implementations of graph DS and its applications Graph DS Online Quiz (medium), No built-in C++ STL container | Python standard library | Java API, See graph_ds.cpp | py | java at GitHub repo of CPbook website, Early discussion of the basic forms of Graph Traversal algorithms: DFS first See dfs_cc.cpp | py | java Last 20m of 08a: VisuAlgo Online Quiz 2 (11%) Material: /heap (4 Qs), /hashtable (4 Qs), /bst (4 Qs) and 4 'new' questions. |
PS5, continued |
|
10, 24-28 Mar |
T07+L07: tut07.pdf Graph DS Review, Some Graph Properties Discussion, Graph DS Conversion Exercise, DFS Review, Custom graph DS implementation review, VA OQ demo (graphds,dfsbfs), Hands-on, a simple Graph DS task, PS5 Discussion (algorithmic) PS: Sat sessions run tut07.pdf on Sat, 22 Mar 25 at different venues (clash with SGP NOI 2025 Final) B1A moves from PL6 to SR@LT19 B1B+first half of B1D moves from WSLab1 to SR7 B1C+second half of B1D moves from WSLab2 to SR8 Prof Halim is NOT running B1D for T07+L07 |
09a. Graph Traversal Applications (Slide 6 to 9) Review DFS and introducing BFS Focus on a few more basic DFS/BFS applications For S2 AY 2024/25, we discuss slide 8!! (we skip slide 10-12, out of CS2040/C/S and IT5003 scope) DFS/BFS Online Quiz (medium) No built-in C++ STL algorithm | Python standard library | Java API, See UVa00469.cpp | py | java, and bfs.cpp | bfs.py | java at GitHub repo of CPbook website, Kattis problem(s) discussed today: reachableroads (AL; count #CC; DFS vs BFS way) builddeps (AL of Strings + postorder DFS toposort demo) NUS Online Teaching Feedback opens this Fri But this timing is too early for our course... You can wait until you have completed the course NUS Well-Being Day is Fri, 28 Mar 2025 |
PS5 (2%) Due: Thu, 27 Mar 25, 11.59pm Before Well-Being Day |
|
11, 31 Mar-04 Apr |
As Sat, 29 Mar 2025 is part of NUS long well-being weekend and Mon, 31 Mar 2025 is Hari Raya Puasa PH We move our last two downwards |
10a. SSSP Problem (all slides) Review of basic SSSP problem Preview of O(VE) / O(kE) Bellman-Ford algorithm QnA on BFS algorithm for unweighted SSSP QnA on Dijkstra's algorithm (original Dijkstra's first; but focus on modified Dijkstra's for IT5003) See dijkstra.cpp | py | java at GitHub repo of CPbook website Quick discussion of SSSP on Tree and on DAG SSSP Online Quiz (medium) Kattis problem(s) discussed today: modulosolitaire (SSSP; directed unweighted implicit graph; BFS) shortestpath1 (basic Dijkstra's; focus on easy lazy-minPQ implementation) |
PS6: Graph(-Related) Problems Out: Tue, 01 Apr 25, 08.00am After Well-Being+Hari Raya PH weekend |
|
12, 07-11 Apr |
T08+L08: tut08.pdf BFS Review DFS/BFS advanced stuffs: Cycle Detection, Toposort++, Floodfill/CC, Bipartite Graph Checker Modeling exercise, PS5 Debrief (short), VA OQ demo (dfsbfs), Hands-on, a Graph Traversal task, PS6 Discussion (algorithmic) |
11a. SSSP, NP-completeness, and Course Wrap-Up QnA on a few other special cases of SSSP problem Showing the limit of computation: Introduction to the theory of NP-completeness Course wrap-up Last 20m of 12a: VisuAlgo Online Quiz 3 (11%) Material: /graphds (4 Qs), /dfsbfs (4 Qs), /sssp (4 Qs), and 4 'new' questions. |
PS6, continued |
|
13, 14-18 Apr |
T09+L09: tut09.pdf BFS/Dijkstra's review Modeling exercises (continued), VA OQ demo (sssp), Hands-on, an SSSP task, PS6 Discussion (algorithmic) Tut+Lab participation marks given (3%) |
No more lecture Make-up slot for VA OQ 1 (6 pax ), OQ 2 (6 pax), and OQ 3 (1 pax) Date and Time: Wed, 16 Apr 2025, 6.30-6.50pm and then 6.55-7.15pm, for make-up OQ1 and OQ2 (has 1 overlap) But also 6.30-6.50pm (same as make-up OQ1 time, as there is no overlap) Venue: At our own LT8 |
PS6 (2%) Due: Sat, 19 Apr 25, 07.59am |
|
Study Week, 19-25 Apr 2054 Final Assessment Discussions at Class Discord Final Assessment Past Papers (recent 3 AYs only): AY 2022/23: S1-final.pdf, S2-final.pdf, AY 2023/24: S1-final.pdf, S2-final.pdf, AY 2024/25: S1-final.pdf, S2-final.pdf (to be our paper). |
|||
|
Final Assessment (50%) Date and Time: Tue, 29 Apr 2025, 5-7pm (back to exam period) Venue: MPSH4 Open book Non-programmable calculator is allowed (as with Online Quiz), but won't be that useful 10% MCQs (very tricky); I use my own OCR form, and 6 essay questions, the harder ones (6x15 = 90%) |
|||