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 sixth 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 + Biomed) 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.
This time, Prof Halim is preparing for a [161-200]-ish class size with all onsite components (more details in the lesson plan below). Update as of 15 Aug: There are 214 students...
Some other facts:
Rating (out of 5.0) |
Oct-Dec 23 (n=1??/224) ≥ 50% |
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% ▲ |
Oct-Dec 20 (n=5/33) 15% (too small) |
---|---|---|---|---|---|---|
Course feedback (SoC avg ~3.8) | ≥ 4.3 (target) | 4.5 ▲ (PB) | 4.4 == | 4.4 ▲ | 4.3 ▲ | 4.2 |
Course difficulty (SoC avg ~3.8) | ≤ 3.9 (maintain) | 3.9 == | 3.9 == | 3.8 ▼ | 3.5 ▼ (PB) | 4.0 |
Prof Halim's teaching (SoC avg ~4.1) | ≥ 4.3 (target) | 4.6 == (PB) | 4.6 == (PB) | 4.6 ▲ (PB) | 4.5 ▲ | 4.4 |
Update on 27 Sep 2023:
Almost all students have a lab group by now.
Date, Time | Live Session (Venue) (#Stu/#Cap) | No | Tutor |
---|---|---|---|
a/Sat, 1000-1200 | COM1-B1-12 (PL1) (29/35) | B5 | Prof Halim |
a/Sat, 1000-1200 | COM1-B1-10 (PL5) (23/23) | B6 | Hao Yi |
a/Sat, 1000-1200 | COM1-01-20 (PL6) (31/31) | B7 | Chia Geng |
a/Sat, 1000-1200 | COM1-01-13 (ESLab2) (23/24) | B8 | Devansh |
b/Mon, 1400-1600 | COM1-B1-09 (PL2) — for full-time MComp students (30/35) | B1 | Jeanette |
b/Mon, 1400-1600 | COM1-B1-10 (PL5) — for full-time MComp students (22/23) | B2 | Lian Ziyue |
c/Mon, 1600-1800 | COM1-B1-09 (PL2) — for full-time MComp students (29/35) | B3 | Ren Weilin |
c/Mon, 1600-1800 | COM1-B1-10 (PL5) — for full-time MComp students (20/23) | B4 | Ryan Tan |
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 S1 AY 2023/24 timetable below is still tentative, especially those that are highlighted with pink color.
IT5003 classes comprises of Lecture, Tutorial+Lab Combo, and Weekly Problem Sets.
For Lectures (discussion of VA e-Lecture Slides, Q&A sessions, and live problem-solving segment), we have:
Lectures start from Wk07 (attendance is compulsory for those using SSG/SkillsFuture Credit).
Sat Sessions start from Wk07 (and ending on Sat, 25 Nov 2023 — the only clash with NUS first exam day) whereas Mon Sessions start from Wk08 (and ending on Mon, 27 Nov 2023 — the only clash with NUS first exam week).
For Weekly Problem Sets, you can do it at home.
One set of two 'simple' problems per week from Wk07.
It is expected that students spend around ~5 hours to complete one set each week.
The problems will be discussed in algorithmic (high-level) during each Lab session.
You can use ChatGPT (or alternative) tool as long as you eventually code the solution yourself (this part is for your own good).
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 Python 3 specific instructions @ Kattis, 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, 20 Sep 23, 08.00am |
-01, Bef Wed, 04 Oct |
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 ( extended to two weeks |
07, Session 1 04+07 Oct |
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 r1. Recitation: Basic Python Extra QnA session on Basic Python, discussion of more/alternative Python features, review PS0: Easy Python/coding challenges tasks 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: TBA Reminder: Read sorting e-Lecture slides before Lecture 2a At least until slide 11-11, preferably more Sat, 07 Oct 2023 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: TBA, PS1 Discussion (algorithmic) |
PS0: Easy Python/coding challenges Due: Wed, 04 Oct 23, 07.59pm (solve any 3 → 1% — to speed up registration admins) PS1: Basic Python Out: Wed, 04 Oct 23, 08.00pm Easier subtasks showcased live during the first lecture |
08, Session 2 11+14 Oct |
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: TBA 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: TBA 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) |
T02+L02: it5003lab2.pdf Sorting Application(s), Sorting Algorithms Review via mini experiment, PS1 Quick Debrief, VA OQ demo (sorting), Hands-on: TBA, PS2 Discussion (algorithmic) |
PS1: Basic Python Due: Wed, 11 Oct 23, 07.59am (1.5%) PS2: Sorting Problems Out: Wed, 11 Oct 23, 08.00am |
09, Session 3 18+21 Oct |
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) r3. 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, (e.g., the clever way to use two Python lists as queue), etc. Mock VA OQ 1 (medium level only), Kattis problems discussed today: TBA 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: TBA, PS3 Discussion (algorithmic) |
PS2 Due: Wed, 18 Oct 23, 07.59am (2.5%) PS3: List Problems Out: Wed, 18 Oct 23, 08.00am |
10, Session 4 25+28 Oct |
4a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3) Introducing PQ ADT Introducing basic Binary Heap structure and operations BinaryHeapDemo.cpp | py | java 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 VisuAlgo Online Quiz 1 (9%) First 2 topics of IT5003: sorting and list only, with a few new questions 8.10-8.20pm, onsite Bring your own laptop r4. Recitation: Priority Queue Extra QnA session on anything about PQ, e.g., The extra PQ/Binary Heap operations. Kattis problems discussed today: TBA, 4b. Priority Queue (PQ) (to end) O(N) Heapify/Create Heap O(N + K log N) partial sort vs other sorting algorithms Short remarks on past paper question involving greedy with PQ 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, Max-Min PQ conversion (numbers only), PS3 Quick Debrief, VA OQ demo (heap), Hands-on: TBA, PS4 Discussion (algorithmic) |
PS3 Due: Wed, 25 Oct 23, 07.59am (2.5%) PS4: PQ Problems Out: Wed, 25 Oct 23, 08.00am |
11, Session 5 01+04 Nov |
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: TBA r5. 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, Mock VA OQ 2 (medium level only, without bst yet), Kattis problems discussed today: TBA, 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 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, 01 Nov 23, 07.59am (2.5%) PS5: (Hash) Table Problems Out: Wed, 01 Nov 23, 08.00am |
12, Session 6 08+11 Nov |
6a. Graph DS + Applications (read ALL slides), plus 6b. Graph Traversal + Simple Applications (Slide 1 to 7-1) FAST: Introducing Graph Theory FAST: Introducing Graph Data Structures No built-in C++ STL container | Python standard library | Java API, See graph_ds.cpp | py | java at GitHub repo of CPbook website, Graph DS Online Quiz (medium), Introducing Graph Traversal Algorithms, No built-in C++ STL algorithm | Python standard library | Java API, See dfs_cc.cpp | py | java, UVa00469.cpp | py | java, and bfs.cpp | bfs.py | java at GitHub repo of CPbook website, Kattis problems discussed today: TBA VisuAlgo Online Quiz 2 (9%) First 5 topics of IT5003: sorting, list, heap, hashtable, bst only, [hashtable: QP/DH and bst: AVL tree questions are removed], with a few new questions 8.35-8.45pm, onsite (we need extra time due to the long weekend) Bring your own laptop Fri, 10 Nov 2023 is chosen as NUS well-being day S1 AY 2023/24 Thus, recitation r6 is cancelled Also, we are not allowed to have a session on Sat, 11 Nov 2023 (hence, the long(er) Wed, 08 Nov 2023 session) Prof Halim will depart to Sharm el-Sheikh, Egypt, on Sat, 11 Nov 2023 night |
T06+L06: it5003lab6.pdf is cancelled Sat, 11 Nov 2023 is part of NUS long weekend Sun, 12 Nov 2023 is Deepavali PH Thus, Mon, 13 Nov 2023 is also a PH Discussion of the easy PS6 via Class Discord |
PS5 Due: Wed, 08 Nov 23, 07.59am (2.5%) PS6: Graph DS+Traversal Problems Out: Wed, 08 Nov 23, 08.00am |
13, Session 7 15+18 Nov |
Prof Halim will be in Sharm el-Sheikh, Egypt, for combo ICPC World Finals 2022+2023 (12-17 Nov 2023) Prof Halim plans to record only the Wed session for this week... Prof Halim's current return flight will arrive on Fri, 17 Nov, 8.30am on time for r7 and 7b. 7a. Graph Traversal continued (Slide 7-2 to 7-11) THIS ONE IS 100% RECORDED. Recap of session 6b. DFS/BFS Online Quiz (medium), Kattis problems discussed today: TBA r7. Recitation: (Balanced) BST + Graph 1 [ONSITE] 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 Our venue may be prepped for UG final assessment venue If that happens (again), we will plan around it... 7b. Single-Source Shortest Paths (SSSP) Problem (Slide 1 to 2; then BFS: slide 5 to 6-3) [ONSITE] Introducing 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: TBA |
T07+L07: it5003lab7.pdf Graph DS Fast Review, Graph DS Conversion Exercise, DFS/BFS Review, SSSP Review 1 (unweighted/BFS), Graph Modeling exercise, PS5+6 Quick Debrief, VA OQ demo (graphds,dfsbfs), Hands-on: TBA, PS7 Discussion (algorithmic) |
PS6 Due: Wed, 15 Nov 23, 07.59am (2.5%) PS7: Graph Traversal+SSSP Problems Out: Wed, 15 Nov 23, 08.00am |
Reading, Session 8 22+25 Nov |
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) See dijkstra.cpp | py | java at GitHub repo of CPbook website SSSP Online Quiz (medium), Kattis problems discussed today: TBA r8. Recitation: SSSP Extra QnA session on anything about IT5003 topics using past paper(s) as the backdrop NUS Online Teaching Feedback closes on Friday of Study Week 8b. Course wrap up Showing the limit of computation: Introduction to the theory of NP-completeness Last few words VisuAlgo Online Quiz 3 (9%) All topics of IT5003 (including /sssp), with a few new questions [hashtable: QP/DH, bst: AVL tree, sssp: Bellman-Ford questions are removed], with a few new questions 9.30-9.40am, onsite Bring your own laptop |
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, 22 Nov 23, 07.59am (2.5%) PS8: Weighted SSSP Problems Out: Wed, 22 Nov 23, 08.00am |
"Study Window", 28 Nov-06 Dec 2023 Final Assessment Discussions at Class Discord Final Assessment Past Papers (recent 3 AYs only): 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, S2-final.pdf, AY 2023/24: S1-final.pdf (will be our paper; will be easier than last semester; I promise). |
PS8 Due: Wed, 29 Nov 23, 07.59am (2.5%) |
||
Final Assessment (50%) Date and Time: Thu, 07 Dec 2023, 5-7PM Venue: TBA 45% MCQs (very tricky); 25% easy short questions; 30% differentiator questions |