IT5003 - Data Structures and Algorithms (Python)

Introduction

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.

Course Registration

This is the going to be the eight time Prof Halim teaches previously 8-weeks → now 12-weeks (+ 1 more week before final assessment on Week 13) 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 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 S1 AY24/25, due to adjustment of lesson format from Week 01 instead of Week 07 after IT5001, it is expected that there will be (much) fewer students in S1.
Prof Halim prepares for a [75-100]-ish class size.

Some other facts:

  1. Prof Halim has implemented flipped classroom (a type of blended learning) techniques, employing machine-teach-(and-auto-test)-students-on-basic-stuffs, along with in-class live discussion of more challenging problems in his IT5003 classes. From AY 2020/21 until the present, he has received teaching feedback ratings from 4.4 (above average) to 4.6 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.486 (very good).
  2. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo that will be used very extensively in this course.
    The primary goal for this S1 AY2024/25 is for Prof Halim to survive teaching three large courses at the same time (IT5003 - 100 pax; CS2040S - 200 pax; CS3230 - 400 pax; totalling up to 700 pax).
    One key way to do that is to align IT5003 as close as possible to its superset course CS2040S.

    Rating
    (out of 5.0)    		 Aug-Nov 24
    (n=??/100)
    ??%    		 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% ▼    		 Mar-May 22
    (n=57/99)
    58% ▼    		 Oct-Dec 21
    (n=83/130)
    63% ▲
    Course feedback (SoC avg lvl 5000 ~4.1) ≥ 4.3 (tgt) 4.3 == 4.3 ▼ 4.5 ▲ (PB) 4.4 == 4.4 ▲ 4.3 ▲
    Course difficulty (SoC avg lvl 5000 ~3.6) ≥ 4.0 (lower a bit) 4.2 ▲ (uh oh) 3.9 == 3.9 == 3.9 ▲ 3.8 ▲ 3.5 ▼ (PB)
    Prof Halim's teaching (SoC avg lvl 5000 ~4.3) ≥ 4.5 (tgt) 4.4 ▲ 4.3 ▼ 4.6 == (PB) 4.6 == (PB) 4.6 ▲ (PB) 4.5 ▲

    Update on 14 Jun 2024
    Prof Halim will start planning TA hiring by early Jul 2024.
    Interested TA applicants need to ensure that you have applied via tssclaim system by 30 Jun 2024.

    Date, Time Live Session (Venue) (#Stu/#Cap) No Tutor
    a/Sat, 1000-1200 Venue TBC (??/25) B1 Prof Halim
    a/Sat, 1000-1200 Venue TBC (??/25) B4 - if needed TBC
    b/Mon, 1400-1600 Venue TBC — for full-time MComp students (??/25) B2 Jeanette
    c/Mon, 1600-1800 Venue TBC — for full-time MComp students (??/25) B3 TBC

    List of TAs for Aug-Nov 2024:

    1. @prof_halim, Associate Professor Steven Halim (IT5003 course lecturer 7x, soon 8x)
    2. @Jeanette, Tan Yu Wei (IT5003 full-time TA from last five semesters)
    3. Third TA?
    4. If need be: the fourth TA?
  3. Have you passed (or exempted from) IT5001 or CS1010 (or its variants)? You have to...

Syllabus

This is what you will learn in IT5003 as taught by Prof Halim, compare it with the superset CS2040S version:

Course Registration Additional FAQ

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.

Q: Will there be a Practical Exam (PE) for your version of IT5003?
A: I want to, but we do not have enough time for that, so no.
Q: I am from IT5001 (the most relevant course before this)/other courses that do not use Python, should I pick up Python on my own before August 2024?
A: Yes, that is a very good idea.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my CS3233 textbook: Competitive Programming book: CP4, Book 1 (get a copy legally from lulu.com (eBook) or lulu.com (physical, need shipping from overseas)) should be a good book to have. The answers for many of my test questions may be inside that book. The problem is... I discuss over ~3800+ problems in that book, near impossible to solve them all in just one semester.
Q: I heard from my friend/senior that your version of IT5003 is a flipped classroom course?
A: You heard that correctly. Get ready :).
Q: What are the potential changes that you will apply to IT5003 in S1 AY 2024/25 compared to your last semester (S2 AY 2023/24) version?
A: Not much, with average teaching feedback rating of ~4.5 so far, there is not much left to change.... However, these are the potential changes:
  1. From S1 AY24/25, our IT5003 (now 2 hours per-week) starts from Week 01 and that opens up the possibility to synchronize lesson plan (a bit) with the 3 hours per-week CS2040S. Prof Halim is planning to make the two courses 'as close' as possible to reduce his own workload, i.e., by synchronizing almost all Wed morning (10am-12nn XYa lecture in CS2040S) and Wed evening (6.30-8.30pm XY lecture in IT5003) to be as identical as possible. CS2040S 'extra' topics will always be scheduled on Thu evening (5-6pm XYb lecture). Thus IT5003 students only don't have those extra components.
  2. Prof Halim will try to make this course has difficulty rating in [4.0-4.1] range instead of 4.2 (uh oh, overshoot...), 3.9, 3.9, 3.9 in his last four iterations..., i.e., he is conciously making the course a bit harder, closer to CS2040S version.
  3. Prof Halim will have to disappear twice: on Week 04 (IOI 2024, Alexandria, Egypt) and on Week 06 (ICPC World Finals 2024, Astana, Kazakhstan). On both weeks, CS2040S+IT5003 recording will be the same (and Prof Halim will show *both* Java and Python versions of the same thing). His tutorial group will likely be covered by TA Jeanette.
  4. All others are planned to be kept roughly constant.

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.

News

Date News

Lesson Plan

The 4 units IT5003 syllabus will be delivered over 12 weeks, with Week 13 reserved for final assessment.
This course is approximately 24/39 ~= 62% of the content of CS2040S.
The weekly lesson plan of Week X is typically as follows (2+(1+1)+(2+1)+3 = 10 hours/week):

  1. Give yourself about 2-hours/week to self-study as much as you can from various online Python references (follow up from IT5001) and VisuAlgo about the designated topic and attempt the e-Lecture/Online Quiz questions first (flipped classroom),
  2. On Tutorial+Lab day, attempt and then actively participate on 1-hour/week (effective 45 minutes) tutorial slot of past week X-1 topic to improve student's understanding of IT5003 material, short break, then for the second half, students will practice solve a "simple" problem (guided by TA) during the next 1-hour/week (effective 45 minutes) lab session of past week X-1 topic to improve student's coding skills. Currently, we have the following options starting from Wk03:
    1. Saturdays (2 sessions) - start from Week 02 and also end on Week 12 (except Recess Week — cancelled and Week 11 — shifted to Week 12),
    2. Mondays (2 sessions) - start from Week 03 and end on Week 12 (except Week 07 — cancelled),
  3. There is only one lecture session weekly starting from Wk01:
    1. 2-hour/week (effective 105m) in-class lecture 1 on Wed, 6.30-8.30pm @ LT8 (start on time at 6.30pm and end by around 8.15pm - no other class after us), we will roughly do: 5m (buffer) + 5m (admins) + 40m (fast in class review of the more difficult parts of the designated VisuAlgo e-Lecture topics) + 7m (break) + 35m (application 1 - solving at least 1 Online Judge problem live) + 13m (buffer). Note that attendance is compulsory for those using SkillsFuture Singapore (SSG) funding. PS: SSG-funded students have to declare their lecture attendances via this method),
    2. Unlike CS2040S, we do not have additional 1-hour/week lecture, (no more, as we move from fast-paced 8x3 = 24 to a more manageable pace 12x2 = 24 format)
    3. (Optional Onsite) Recitation: every Fri 2-4pm (2h) (should be N/A this semester due to the expected smaller class size in S1 AY 2024/25, TBC)
  4. Attempt a ~two-weeks Problem Set (PS) @ home, approximately 3 hours of work per week on average or (~6++ hours/set), starting from Wk01. The problems will be discussed in algorithmic (high-level) during each Tut+Lab session. You can use ChatGPT (or alternative) tool if you have spent more than 2 hours any PS task without external help (other human or AI, which means in the 2 hours final assessment, you cannot solve this yet), and as long as you eventually (re-)code the solution yourself (this part is for your own good), Plagiarism checker is built-in inside Kattis and extremely similar code can be easily identified,
  5. TOTALLY OPTIONAL: (Re-)solve some Kattis demo problems (or more) that are related to IT5003 using Prof Halim's Methods to Solve page. WARNING: Doing this will significantly increases your study time per week for this course.

Then, repeat this throughout the semester :).

The S1 AY 2024/25 timetable below is still tentative, especially those that are highlighted with pink color. The Wed evening of IT5003 will be as close as possible with Wed morning of CS2040S.

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,
29 Jul-02 Aug 		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
(01-14 Aug)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
00,
05-09 Aug
 Has Not Started Has Not Started
Continue attempting PS0 (hints in class Discord)
Singapore National Day on Fri, 09 August 2024 		PS0, continued
Remember, solve any 3 for 1%
01,
12-16 Aug 		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 X-Y) 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, 14 Aug 24, 07.59pm
PS1: Basic Programming
Out: Wed, 14 Aug 24, 08.00pm
Mentioned at the end of the first lecture
IT5003 students do problem A+B
02,
19-23 Aug 		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)
Last flipped classroom reminder:
Read all sorting e-Lecture slides before next lecture
 PS1 (2%)
Due: Sat, 24 Aug 24, 07.59am
PS2: Sorting-related Problems
Out: Sat, 24 Aug 24, 08.00am
03,
26-30 Aug 		T01+L01: tut01.pdf
Introduction,
OOP review (List ADT, ListArray.py | java)
Algorithm Analysis,
Hands-on, a basic List ADT task,
PS1 Debrief (short),
PS2 Discussion (algorithmic)
 		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)
Prof Halim will depart to Alexandria, Egypt 		PS2, continued
04,
02-06 Sep 		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)
 		Prof Halim will be in Alexandria, Egypt,
for IOI 2024 (01-08 Sep 2024)
04a+04b lectures will be recorded.
The content will be 100% the same as CS2040S version.
04ab. 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:
circuitmath (classic postfix evalution; use a stack/LIFO)
delimitersoup (classic bracket matching variant; use a stack/LIFO)
 		PS2 (2%)
Due: Sat, 07 Sep 24, 07.59am
PS3: List+PQ Problems
Out: Sat, 07 Sep 24, 08.00am
05,
09-13 Sep 		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)
 		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 (4 Qs), /sorting (4 Qs), /list (4 Qs),
and 4 'new' questions.
Prof Halim will depart to Astana, Kazakhstan 		PS3, continued
06,
16-20 Sep 		T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
Python heapq,
VA OQ demo (heap),
Hands-on, a simple greedy problem involving PQ,
PS3 last Discussion (algorithmic)
 		Prof Halim will be in Astana, Kazakhstan,
for ICPC World Finals 2024 (15-20 Sep 2024)
06a+06b lectures will be recorded.
The content will be 100% the same as CS2040S version.
06ab. Table ADT part 1: Hash Table (all slides)
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
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
Hash Table Online Quiz (easy; a bit too tedious on medium/hard settings)
Kattis problem(s) discussed today:
proofs (a simple table ADT task)
 		PS3 (2%)
Due: Sat, 21 Sep 24, 07.59am
PS4: Hash Table Problems
Out: Sat, 21 Sep 24, 08.00am
Recess Week, 21-29 Sep 2024
You can take a break this week :)
07,
30 Sep-04 Oct 		T05 is cancelled for IT5003
As we do not have midterm test 		First half review, especially 04ab + 06ab recordings
Followed by CS2040S Midterm Quiz live discussion
 PS4, continued
08,
07-11 Oct 		T06+L06: tut06.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)
 		08a. 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, 12 Oct 24, 07.59am
PS5: Combo DS Problems
Out: Sat, 12 Oct 24, 08.00am
09,
14-18 Oct 		T07+L07: tut07.pdf
Table ADT 2 - ordered,
(balanced) BST advanced stuffs: Select and 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 (algorithmic)
 		09a. 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 + one application (count #CC)
See dfs_cc.cpp | py | java
Kattis problem(s) discussed today:
reachableroads (AL; count #CC; DFS introduction)
Last 20m of 09a: VisuAlgo Online Quiz 2 (11%)
Material: /heap (4 Qs), /hashtable (4 Qs), /bst (4 Qs),
and 4 'new' questions.
 		PS5, continued
10,
21-25 Oct 		T08+L08: tut08.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)
 		10a. Graph Traversal Applications (Slide 6 to 7-11)
Review DFS and introducing BFS
Focus on a few more basic DFS/BFS applications
(we skip slide 8-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:
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
 PS5 (2%)
Due: Sat, 26 Oct 24, 07.59am
PS6: Graph Problems
Out: Sat, 26 Oct 24, 08.00am
11,
28 Oct-01 Nov 		T09+L09: tut09.pdf
BFS Review
DFS/BFS advanced stuffs:
Cycle Detection, Toposort++, Floodfill/CC,
Modeling exercise (time permitting),
PS5 Debrief (short),
VA OQ demo (dfsbfs,sssp),
Hands-on, a Graph Traversal task,
PS6 Discussion (algorithmic)
 		11a. SSSP Problem (Slide 1 to 7-5)
Review of basic SSSP problem
Preview of O(VE) / O(kE) Bellman-Ford algorithm
QnA on BFS algorithm for unweighted SSSP
SSSP Online Quiz (medium)
QnA on Dijkstra's algorithm (modified Dijkstra's first)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
modulosolitaire (SSSP; unweighted graph; BFS; implicit graph)
shortestpath1 (basic Dijkstra's)
Thu, 31 Oct 2024 is Deepavali PH

Additionally, Fri, 01 Nov 2024 is chosen as
NUS well-being day S1 AY 2024/25
Enjoy our short break here
 		PS6, continued
12,
04-08 Nov 		As Sat, 02 Nov 2024 is part of
NUS long well-being weekend
Sat sessions will do last T10+L10
on Sat, 09 Nov 2024 instead
T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (dfsbfs,sssp),
Hands-on, an SSSP task,
PS6 Discussion (algorithmic)
Tut+Lab participation marks given (3%) 		12a. SSSP, NP-completeness, and Course Wrap-Up
QnA on 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 (2%)
Due: Sat, 09 Nov 24, 07.59am
13,
11-15 Nov 		"Study Window", 06-12 Nov 2024

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 (will be our paper).

Make-up slot for VA OQ 1 (? pax), OQ 2 (? pax), and OQ 3 (? pax)
Date and Time: Wed, 13 Nov 2024, 5.00-5.30pm
Venue: TBA

Final Assessment (50%)
Date and Time: Wed, 13 May 2024, 6.30-8.30pm
Venue: TBA
Open book
Non-programmable calculator is allowed (as with Online Quiz), but won't be that useful
50% MCQs (extremely tricky); I use my own OCR form
(the MCQs are there to speed up grading as Prof Halim (solo grader: 1 versus 100) has two other papers (CS3230: 540 pax, CS2040S: 200 pax)
4 → 3 short questions (30% --- do not lose too many marks here), and
1 → 2 essays (20%)
Study Week, 16-22 Nov 2024 and Examination Period, 23 Nov-07 Dec 2024
Nothing for IT5003 (our final assessment is on Week 13)
You can prepare for your other final assessment (if any)
NUS Online Teaching Feedback System closes on Friday of Study Week