CS2040S - Data Structures and Algorithms (Java)

Introduction

This course introduces students to the design and implementation of fundamental data structures and algorithms. The course covers basic data structures (linked lists, stacks, queues, binary heaps, hash tables, trees, and graphs), searching and sorting algorithms, and basic analysis of algorithms.

The programming language used for this course is Java.

We use very basic object-oriented programming concepts in various data structures implementations, e.g., Stack class inherits LinkedList class (more details of OOP are in CS2030).

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

For AY 2025/26, Prof Halim teaches CS2040S (CS students) in S1 (since S1 AY 2023/24);
but also returning to teach CS2040C (CEG, InfoSecurity, exchange students) in S2 (last was S1 AY 2022/23).

Some 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 CS2040/C/S classes. From AY 2017/18 until the present, he has received teaching feedback ratings from 4.2 (average) to 4.8 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.458 (good).
  2. Apart from teaching CS2040/C/S on multiple occassions from 2017 to the present, Prof Halim has also taught similar courses that are variants of the current version of CS2040/C/S, namely CS2020 once (2011), CS2010 six times (2011-2016), CS1020E once (2016), and IT5003 nine times (2020-present).
  3. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo, a tool that is extensively utilized in this course.
    The primary goal for this S1 AY 2025/26 is to integrate as many key/recurring/most liked/popular LeetCode tasks in this course, as LeetCode is currently one of the most popular coding interview website out there for now (in AY 2025/26).
    The secondary goal is to reduce the 'perceived course difficulty' by a bit to around [4.0..4.1] by removing the Practical Exam (Prof Halim's favorite) component.

    Rating
    (out of 5.0)    		 Aug-Nov 25
    (n=???/[150-180])
    ≥ 50    		 Aug-Nov 24
    (n=128/161)
    80% ▲    		 Aug-Nov 23
    (n=90/128)
    70% ▼    		 Aug-Nov 22 (CS2040C)
    (n=162/206)
    79%
    Course feedback (SoC avg lvl 2000 ~3.9) [4.1..4.2] (tgt) 4.2 == 4.2 == 4.2
    Course difficulty (SoC avg lvl 2000 ~3.8) [4.0..4.1] (tgt) 4.2 ▼ (almost 4.1) 4.3 == 4.3
    Prof Halim's teaching (SoC avg lvl 2000 ~4.2) [4.3..4.4] (tgt) 4.5 (PB for 2040S) ▲ 4.4 ▼ 4.5

    TAs:

    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    1/Mon, 1000-1200 Lab (??/20) 01 TBA
    1/Mon, 1000-1200 Lab (??/20) 02 TBA
    1/Mon, 1200-1400 Lab (??/20) 03 TBA
    1/Mon, 1200-1400 Lab (??/20) 04 TBA
    1/Mon, 1400-1600 Lab (??/20) 05 TBA
    1/Mon, 1400-1600 Lab (??/20) 06 TBA
    1/Mon, 1600-1800 Lab (??/20) 07 TBA
    1/Mon, 1600-1800 Lab (??/20) 08 TBA
    5/Fri, 2100-2300 Zoom Recurring Link TBA (free and easy) - various TAs

    List of TAs (ordered using Lab Group Number):

    1. Eldric Liew Chun Tze, full-time TA, but half load (just one lab group), maybe for midterm+final grading too (TBC)
    2. Special part-time TA for grading midterm+final only: Ivan Chew Teck Meng (likely confirmed, but not taking lab group)

    Part-time TAs applications

    • Category 1: Prof Halim's past TA(s), taken again pending official confirmation at TMTF system:
      1. @ahzong, Chong Chin Herng (peak rating: 5.0/CS2040S S2 AY24/25)
      2. @chronal_02, Winston Leonard Prayonggo (peak rating: 4.9/CS2040S S1 AY24/25)
      3. @pisciprehender, Zhang Puyu (peak rating: 4.8/CS2040S S1 AY24/25)
    • Category 2: Has other NUS teaching experience(s), chance correlates with teaching feedback of those past experiences (sorted by decreasing peak-performance) and perceived 'spare mental capacities left to do far-higher-than-average TA job again', all taken:
      1. Sherisse Tan Jing Wen, ex CS2040S S1 AY24/25 (peak rating: 4.7/CS2040S S2 AY24/25)
      2. Lew Choon Hean, ex CS3233 S2 AY24/25 (peak rating: 4.5/CS2030S TA S2 AY24/25)
      3. Hong Jung Woo, ex CS2040S S1 AY23/24 and CS3230 S1 AY24/25, (peak rating: 4.5/CS2040 S1 AY24/25)
      4. Nguyen Anh Quan, ex CS3233 S2 AY24/25 (peak rating: 4.3/CS2040S S2 AY24/25)
      5. Low Khing Wei, Ryan, ex CS2040S+CS2106 TA in S2 AY24/25 (peak rating: 4.2+4.2), CS1231S in S1 AY24/25 (peak rating: 4.3)
      6. Other prospective part-time TAs should inform Prof Halim about your intention to TA as soon as you can
    • Category 3: New with NUS teaching (sorted by alphabetical order of their names), chance correlates with Prof Halim's 'spider sense' about the candidates potential teaching capabilities and perceived 'spare mental capacities left to do first time TA job' (for future TA army replenishment):
      1. Ang Wei Jian, ex CS2040S S1 AY24/25
      2. Chua Wei En Zechary, ex CS2040S S1 AY24/25
      3. Suhail Loya, ex CS3233 S2 AY24/25
      4. Sultan Shayaan, ex CS2040S S1 AY23/24
      5. Tan Guan Qun, ex CS2040S S1 AY24/25, either CS2040S or CS3230
      6. Other prospective part-time TAs should inform Prof Halim about your intention to TA as soon as you can

    Any other applicant(s) who put CS2040S in the TMTF system but without informing Prof Halim will not be considered.

  4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
  5. For CS2040S, have you passed CS1231 (or its variants)? You have to...
  6. Have you taken CS1020/CS1020E/CS2010/CS2020? You cannot take CS2040/C/S if you have taken similar/older course(s) that have huge degree of overlap with this course.

Syllabus

This is what students learn in CS2040/C/S as taught by Prof Halim, compare it with the subset IT5003 version:

Course Registration Additional FAQ

If you have any important questions regarding this course, email dcssh at nus edu sg. Relevant answers will be posted here to reach wider audiences.

Q: Will there be a Practical Exam (PE) for your version of CS2040/C/S?
A: Probably no starting from S1 AY25/26... The weightage (that was previously for the stressful PE) will be passed to Final instead.
Q: Will this course be graded using Bell curve?
A: CS2040S has much more than 40 students each semester. Bell curve system will obviously be used.
Q: I am from CS1101S (subset of JavaScript)/CS1010S or CS1010E (Python)/other modules that do not use Java, should I pick up Java on my own during this May-June-July 2025 University Holiday?
A: Yes, that is a very good idea. We will only review basic Java in the first few weeks of this course and then Prof Halim will encourage you to self-learn Java along the way.
Q: What Integrated Development Environment (IDE) that we will use in your version of CS2040/C/S?
A: The choice of IDE to do the bi-weekly assignments is "up to you but" (as there is no PE).
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 ~4800+ problems in that book, near impossible to solve them all in just one semester.
Q: Can I S/U this course if I am a freshman when I take this course?
A: No, as this is a level-2 core course. CS2040/C/S has CS1010 as pre-requisite and according to Registrar's Office: "The S/U option will apply to all Level 1000 courses (with or without pre-requisites) and Level 2000 courses without other NUS courses as pre-requisites, unless otherwise stipulated by the Faculties/Departments.". So factor this information when taking this course.
Q: I heard from my friend/senior that your version of CS2040/C/S is a flipped classroom course?
A: You heard that correctly. Prof Halim uses his 24/7 electronic clone, VisuAlgo, to be able to explain basic data structures and algorithms concepts covered in CS2040/C/S as clear as possible to first timer (and to automatically test students about these basic concepts). This will free some substantial minutes from the precious 2+1h (effective 95+45m = 140m per week to discuss the harder/deeper part of the syllabus and to do live demonstration of how those data structures and algorithms can be used to solve (real life, but sometimes fictional) programming problem. This will also help Prof Halim to scale himself (one person) to handle large algorithm classes.
Q: What are the potential changes that you will apply to CS2040/C/S in S1 AY 2025/26 compared to your many earlier runs of this course?
A: Prof Halim only plan to change these variables this time (all others are planned to be kept roughly constant):
  1. [TO BE PERFECTED]: From last AY, S1 AY24/25, IT5003 (Python) also starts from Week 01. Prof Halim had made 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 morning (9-10am XYb lecture).
  2. [TO TRY ONE MORE TIME]: Prof Halim will try to make this course has difficulty rating in [4.0-4.1] range instead of 4.3, 4.3, 4.2, 4.2 in his last four iterations..., so let's see if removing PE helps to achieve this.
  3. Prof Halim will have to disappear again, but at least just once this semester, on Week 04 (ICPC World Finals 2025, Baku, Azerbaijan). There will be substitute lecturer for that week.
  4. Prof Halim started joining LeetCode effectively from CNY 2025 (at this point of writing, he has solved 1143 out of 3580 tasks (~32%)). He plans to reach ~1300 tasks solved (~36%) by the time S1 AY25/26 starts (11 August 2025) and ~1600 tasks solved (45%) by the time S1 AY25/26 is over (30 November 2025). He will mix Kattis (much longer/story-based problem statement) and LeetCode more direct interview-style questions in class demos.
  5. Final assessment weightage now increases from 40% to 60%...

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 CS2040/C/S syllabus will be delivered over 13 weeks.
This course is a superset of the content of a similar IT5003 course, approximately 39/24 ~= 63% more content than IT5003.
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 Java references (especially during the early transition weeks) 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 CS2040/C/S 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. This semester, we only have 8 available options (all on Monday), starting from Wk03,
  3. There are two lecture sessions weekly starting from Wk01:
    1. 2-hour/week (effective 95m) in-class lecture 1 on Wed, 10am-12nn @ LT19 (start on time at 10.00am and end by around 11.35am), we will roughly do: 5m (buffer) + 5m (admins) + 35m (fast in class review of the more difficult parts of the designated VisuAlgo e-Lecture topics) + 7m (break) + 30m (application 1 - solving at least 1 Online Judge problem live) + 13m (buffer),
    2. 1-hour/week (effective 45m) in-class lecture 2 on Thu, 9-10am @ LT19 too, we will roughly do: 5m (buffer) + 5m (admins) + 30m (application 2 - solving at least another 1 Online Judge problem live) + 5m (buffer) — this additional 35-40m lecture per week is the one that is different from IT5003 version,
  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 attempting 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 and/or LeetCode demo problems (or more) that are related to CS2040/C/S 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 2025/26 timetable below is still tentative, especially those that are highlighted with pink color. The Wed morning of CS2040S will be as close as possible with Wed evening of IT5003.

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,
28 Jul-01 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 and LeetCode (use full name as in Matric card),
read Java specific instructions @ Kattis,
pick up basic Java by yourself,
and solve the selected Online Judge (OJ)
Problem Set 0 (PS0) by yourself (CS1101S/IT5001/equivalent level)
and LeetCode OJ programming-skills study plan
(solving many 'trivial problems' from this set
---the Kattis one is trackable by Prof Halim, indirectly tells him
about your CS1101S/IT5001/equivalent rough grade)
There is a CS2040 placement test
for AY25/26 incoming IOI medallists
on Thu, 31 Jul 2025, 9-11am SGT
(and Wed, 30 Jul 2025 evening Bolivia time, TBC)
 		PS0: Easy Coding Challenges
(01-13 Aug)
Already graded to speed up
registration admins
Solve any 3 out of 10 trivial tasks for 1%
00,
04-08 Aug 		Has Not Started Has Not Started
Continue attempting Kattis PS0 and LeetCode programming-skills study plan
(hints in class Discord)
Singapore National Day on Sat, 09 August 2025
 		PS0, continued
Remember, solve any 3 for 1%
01,
11-15 Aug 		Has Not Started 01a. Course Admin, (Re-)Introduction to Java
1. Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + LeetCode + Kattis (NUS)
2. Basic Java review/new feature introduction
Kattis/LeetCode problem(s) discussed today:
A few PS0 and/or programming-skills problems (just for warm-up)
In the middle of 01a: VisuAlgo Online Quiz 0 (0%)
There was 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
01b. Algorithms on Unsorted Array
Kattis/LeetCode problem(s) discussed today:
rankproblem (a List ADT task; Java ArrayList operations:
add (2 versions), indexOf, remove; and using Java class)
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, 13 Aug 25, 11.29am
PS1: Basic Programming
Out: Wed, 13 Aug 25, 11.30am
Mentioned at the end of the first lecture
CS2040S students do problem B+C
problem A is optional (extra practice)
02,
18-22 Aug 		Has Not Started

But (e-)Consultation starts
from Fri, 23 Aug
Review demo code so far, focusing on
Java API (ArrayList, String, Collections)
 		02a. Analysis of Algorithms (Slide 1 to 9-3)
1. Live SpeedTest.cpp | py | java demo
(measure runtime, count # of operations, vs asymptotic analysis)
2. Fast review of O(N^2) sorting algorithms
Kattis/LeetCode problem(s) discussed today:
thanos (analysis: exponential growth, logarithmic steps)
mjehuric (bubble sort simulation)
height (insertion sort simulation)
nothanks (sorting library and linear pass)
02b. Algorithms on Sorted Array
Kattis/LeetCode problem(s) discussed today:
classfieldtrip (merge of mergesort; or any other solution that works)
Last flipped classroom reminder:
Read all sorting e-Lecture slides before next lecture
 PS1 (2%)
Due: Sat, 23 Aug 25, 07.59am
PS2: Sorting-related Problems
Out: Sat, 23 Aug 25, 08.00am
03,
25-29 Aug 		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)
 		03a. Sorting (Slide 10 to 13-2)
1. O(N log N) Merge Sort (C++ stable_sort; Java Collections.sort; Python list.sort)
2. Exp O(N log N) (Rand) Quick Sort (C++ sort; Java Arrays.sort (primitives); N/A in Python)
Sorting Online Quiz (easy)
White-box: SortingDemo.cpp | py | java
Black-box: Java Collections.sort, Arrays.sort (object), Arrays.sort (primitives)
Kattis/LeetCode problem(s) discussed today:
merge-strings-alternately (variant of merge of Merge sort)
03b. Sorting Extras (until end)
A preview of Ω(N log N) lower-bound of comparison-based sorting algorithms
Special-purpose O(N) sorting algorithm: Counting Sort (Only)
Other topics of sorting, e.g., counting inversions, counting minimum swaps
 		PS2, continued
04,
01-05 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 at Baku, Azerbaijan,
for the 2025 ICPC World Finals.
Lec04a will likely be delivered by ??? (TBC).
Lec04b will likely be delivered by ??? (TBC).
04a. List ADT: SLL/Stack/Queue/DLL/Deque (all slides)
1. Introducing List ADT, (resizeable) array versus Singly Linked List (SLL) way
2. Introducing Stack/Queue ADT
3. Wrapping up with DLL and Deque ADT
Linked List Online Quiz (easy)
White-box: SLLDemo.cpp | py | java implementation
Black-box: Stack, but using Java ArrayList implementation versus Java LinkedList and Stack classes
Fixed-size array, circular array version, versus Java Queue and Deque interfaces
Kattis/LeetCode problem(s) discussed today:
delete-the-middle-node-of-a-linked-list (two passes versus two pointers strategies)
removing-stars-from-a-string (bracket matching variant)
04b. List Extras
Kattis/LeetCode problem(s) discussed today:
maximum-twin-sum-of-a-linked-list (how to go backwards in SLL?)
online-stock-span (O(n^2) TLE vs O(n) solution)
 		PS2 (2%)
Due: Sat, 06 Sep 25, 07.59am
PS3: List+PQ Problems
Out: Sat, 06 Sep 25, 08.00am
05,
08-12 Sep 		T03+L03: tut03.pdf
Linked List, mini experiment,
Applications: Reversing/Sorting a List,
Application: Stack-related,
PS2 Debrief (short),
Java LinkedList/Stack/Queue/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)
1. Introducing PQ ADT
2. Introducing basic Binary Heap structure and its Insert+ExtractMax operations
3. Discussing CreateHeap (two versions) and HeapSort operations
Binary Heap Online Quiz (easy)
White-box: BinaryHeapDemo.cpp | py | java
Black-box: priority_queue.cpp | py | java
Kattis/LeetCode problem(s) discussed today:
kth-largest-element-in-an-array (long and short ways)
Last 15m of 05a: VisuAlgo Online Quiz 1 (4%)
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: /array (1Q + 2 'new'), /sorting (3 Qs), /list (3 Qs),
and 3 'new' questions especially on asymptotics.
05b. PQ Extras (until end)
1. O(N) CreateHeap analysis and O(N+K log N) PartialSort
2. Discussing UpdateKey(i, newv) and Delete(i) operations
Kattis/LeetCode problem(s) discussed today:
rationalsequence3 (stack/LIFO and binary heap indexing)
 		PS3, continued
06,
15-19 Sep 		T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
Java PriorityQueue,
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)
06b. Hash Table Extras (until end)
HashTableDemo.cpp | py | java (all use SC)
Java HashSet/HashMap/Hashtable classes
See unordered_map_unordered_set.cpp | py | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
proofs (a simple table ADT task)
 		PS3 (2%)
Due: Sat, 20 Sep 25, 07.59am
PS4: Hash Table Problems
Out: Sat, 20 Sep 25, 08.00am
Recess Week, 20-28 Sep 2025
You can take a break this week :)
07,
29 Sep-04 Oct 		T05+L05: tut05.pdf [Special]
Past midterm paper(s) discussions
 		Midterm Test (10%)
Open book
Three essay questions, with sub-boxes
There are a few blank boxes, which will be given 1 mark if left blank,
but 0 if answered (even a single character) and declared (very) wrong
Material: Up to PQ (L05ab on Week 05 + T04+L04 on Week 06), NO Hash Table yet

Midterm Test Past Papers (recent 3 AYs only):
AY 2022/23: S1-midterm.pdf, [I didn't teach CS2040C in S2],
AY 2023/24: S1-midterm.pdf, [I didn't teach CS2040S in S2],
AY 2024/25: S1-midterm.pdf, [I don't teach CS2040S in S2],
AY 2025/26: S1-midterm.pdf (to be our paper), [I don't teach CS2040S in S2].
07b. Union-Find Disjoint Sets (all slides)
Quick Recap with VisuAlgo
See unionfind_ds.cpp | py | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
tildes (basic UFDS task)
PS: UFDS is reused in Connected Component (CC) and MST topics
 		PS4, continued
08,
06-10 Oct 		T06+L06: tut06.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
Java HashSet/HashMap,
PS3 Debrief (short),
Only for CS2040S: UFDS review,
VA OQ demo (hashtable,ufds),
Skipped for CS2040S: 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
Kattis/LeetCode problem(s) discussed today:
search-in-a-binary-search-tree (implement what we discuss today)
delete-node-in-a-bst (implement the three cases)
08b. Balanced BST and Applications (until end)
QnA about AVL Tree concepts
BST+AVL Online Quiz (hard; need to clear pre-req)
AVL.cpp | (no py yet) | java
Java TreeSet/TreeMap classes
See map_set.cpp | (no built-in py) | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
kattissquest (combo DS, e.g., TreeMap int to PQ of ints, etc)
 		PS4 (2%)
Due: Sat, 11 Oct 25, 07.59am
PS5: Graph DS + Traversal Problems
Out: Sat, 11 Oct 25, 08.00am
09,
13-17 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,
Java TreeSet/TreeMap,
PS4 Debrief (short),
VA OQ demo (bst or avl (need to clear pre-req))
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
See dfs_cc.cpp | py | java
Kattis/LeetCode problem(s) discussed today:
destination-city (degree checks)
Last 15m of 08a: VisuAlgo Online Quiz 2 (4%)
Material: /heap (3 Qs), /hashtable (3 Qs), /bst (3 Qs)
and 3 'new' questions.
09b. Graph Traversal Applications (Slide 7-3 to 7-8)
Finding Connected Components
Kattis/LeetCode problem(s) discussed today:
weakvertices (AM demo)
reachableroads (AL demo; count #CC; DFS vs UFDS implementation)
 		PS5, continued
10,
20-24 Oct 		As Mon, 20 Oct 2025 is Deepavali PH
and Tue, 21 Oct 2025 is NUS well-being day
We move our last three downwards
 		10a. Graph Traversal Applications (Slide 6 to 7-12)
Review DFS and introducing BFS
Focus on a few more basic DFS/BFS applications
(we skip slide 8-11, 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/LeetCode problem(s) discussed today:
number-of-provinces (AM; count #CC; DFS vs BFS way)
course-schedule-ii (cycle detection and provide one topological order if acyclic)
10b. More Graph Applications
Kattis/LeetCode 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, continued
11,
27-31 Oct 		T08+L08: tut08.pdf
Graph DS Review,
Some Graph Properties Discussion,
Graph DS Conversion Exercise,
DFS Review,
Only for CS2040S: UFDS revisited,
Custom graph DS implementation review,
VA OQ demo (graphds,dfsbfs),
Hands-on, a simple Graph DS task,
PS5 Discussion (algorithmic)
 		11a. 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/LeetCode problem(s) discussed today:
rotting-oranges (SSSP; unweighted undirected implicit grid graph; BFS)
network-delay-time (basic Dijkstra's; focus on easy lazy-minPQ implementation)
 		PS5 (2%)
Due: Sat, 01 Nov 25, 07.59am
PS6: Graph(-Related) Problems
Out: Sat, 01 Nov 25, 08.00am
12,
03-07 Nov 		T09+L09: tut09.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)
 		12a. MST Problem (Slide 1 to end)
Review of basic MST problem
QnA on Kruskal's and Prim's algorithms
Mix and Match of various data structures/algorithms covered so far
Kattis/LeetCode problem(s) discussed today:
cats (MST application)
Onsite class photo as momento
Last 15m of 12a: VisuAlgo Online Quiz 3 (4%)
Material: /graphds (3 Qs), /dfsbfs (3 Qs), /sssp (3 Qs),
and 3 'new' questions.
12b. SSSP+MST Wrap-Up
QnA on Modified Dijkstra's
Other special cases of SSSP problem
Other MST Variants
 		PS6, continued
13,
10-14 Nov 		T10+L10: tut10.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%) 		13a. Make-up time window:
for VA OQ 1/2/Midterm Test/VA OQ3
(details TBC)

13b. The Last Lecture
Course wrap-up et al:
Undoing all the illegal Java coding techniques,
Semester summary via... IT5003 past paper discussion,
Review of what can be done better for future iterations,
Advertisement of future (algorithm) courses: CS3230 (S1 or S2)
Advertisement for part-time TA jobs (A-/A/A+ only),
Ending: a few Final Assessment Tips.
 		PS6 (2%)
Due: Sat, 15 Nov 25, 07.59am
Study Week, 15-21 Nov 2025

Final Assessment Discussions at Class Discord

Final Assessment Past Papers (recent 3 AYs only, note the transition from CS2040C/C++ to CS2040S/Java):
AY 2022/23: S1-final.pdf, [Prof Halim didn't teach CS2040C in S2],
AY 2023/24: S1-final.pdf, [Prof Halim didn't teach CS2040S in S2],
AY 2024/25: S1-final.pdf, [Prof Halim does not teach CS2040S in S2],
AY 2025/26: S1-final.pdf (will be our paper).

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (60%)
Date and Time: Thu, 27 Nov 2025, 01.00-03.00pm
Venue: TBA
Open book
The rest TBA