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

Prof Halim is focusing on SoC Computer Science (CS) cohort since S2 AY 2022/23 - present.
That's it, if you are a SoC CS student, you may encounter Prof Halim in CS2040S S1 and/or CS3230 S1.
If you reach this page because you are looking for CS2040/C information, Prof Halim doesn't teach those version now, contact Dr Chong Ket Fah Prof Roger/Sanka/Anandha (CS2040) or Prof Alan (CS2040C).

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 (slightly above average) to 4.8 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.455 (very 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 (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 AY2024/25 is for Prof Halim to survive teaching three (two are large) courses at the same time (CS2040S - 161 pax; IT5003 - 33 pax (small); CS3230 - 434 pax; totalling up to 628 pax).
    One key way to do that is to align CS2040S as close as possible to its subset course IT5003.

    Rating
    (out of 5.0)    		 Aug-Nov 24
    (n=128/161)
    80% ▲    		 Aug-Nov 23
    (n=90/128)
    70% ▼    		 Aug-Nov 22
    (n=162/206)
    79% ▲    		 Jan-May 22
    (n=101/131)
    77% ▲    		 Aug-Dec 21
    (n=49/69)
    71% ▲    		 Jan-May 21
    (n=158/253)
    62% ▲
    Course feedback (SoC avg lvl 2000 ~3.9) 4.2 == 4.2 == 4.2 == 4.2 == (+Alan) 4.2 == 4.2 ▲ (+Alan)
    Course difficulty (SoC avg lvl 2000 ~3.8) 4.2 ▼ (almost 4.1) 4.3 == 4.3 ▲ 4.2 == (high) 4.2 ▲ 3.9 ▼ (easiest)
    Prof Halim's teaching (SoC avg lvl 2000 ~4.2) 4.5 (PB)▲ 4.4 ▼ 4.5 ▲ 4.3 ▼ (+Alan) 4.5 ▲ 4.4 ▲ (+Alan)

    TAs:

    Date, Time Live Session (Venue) (#Stu/#Cap) No TA
    1/Mon, 1000-1200 COM1-B109 (PL2) (22/22) 01 @pisciprehender
    1/Mon, 1000-1200 COM1-B108 (PL3) (22/22) 02 @saddle196883
    1/Mon, 1200-1400 COM1-B109 (PL2) (21/21) 03 @chiralcentre
    1/Mon, 1200-1400 COM1-B108 (PL3) (22/22) 04 @ernest__
    1/Mon, 1400-1600 COM1-B108 (PL3) (19/21) 05 @sandyk_sk
    1/Mon, 1400-1600 COM1-B111 (PL4) (19/21) 06 @chronal_02
    1/Mon, 1600-1800 COM1-B108 (PL3) (20/21) 07 @json.c
    1/Mon, 1600-1800 COM1-B111 (PL4) (16/21) 08 @ahzong
    5/Fri, 1900-2100 2100-2300 Zoom Recurring Link (free and easy) - various TAs

    List of TAs (ordered using Lab Group Number):

    1. @pisciprehender, Zhang Puyu (peak rating: 4.9/CS1010)
    2. @saddle196883, Timothy Wan Kai Yang (peak rating: 4.8/CS2040S)
    3. @chiralcentre, Ryan Tan Wei Jie (peak rating: 4.9/CS2040S)
    4. @ernest__, Ernest Ng Zi Xuan (peak rating: 4.6/CS2040S+CS2040C)
    5. @sandyk_sk, Sandy Kristian Waluyo (IMO 22 Bronze, new NUS TA)
    6. @chronal_02, Winston Leonard Prayonggo (peak rating: 4.9/CS2040S)
    7. @json.c, Jason Christopher (peak rating: 5.0/CS2040S)
    8. @ahzong, Chong Chin Herng (peak rating: 4.9/CS1231S)
    9. Special full-time TA for Week 02-04 only: @dustbinnnnnn, Ng Tzer Bin
    10. Special part-time TA for grading midterm+final only: Ivan Chew Teck Meng
    11. PE Setting Only: Muhammad Ayaz Dzulfikar
  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: Yes, there will be a Practical Exam (PE) held once, specifically on Week 10, covering all topics up to just before the graph data structure. However, due to the availability of generative AI tools like ChatGPT, Prof Halim is no longer feels comfortable conducting an Open Internet PE (and also not allowed to). Instead, the plan is to implement onsite proctoring with some form of Internet firewall. The specific details are yet to be confirmed.
Q: PE sounds scary... Will there be a make up PE if I am sick/underperform...?
A: Yes. Prof Halim is aware that many students are still at learning stage. Those who are absent from the official ones for valid reason (clash with another official NUS course, Medical Certificate (MC), Bereavement of immediate family member, representing NUS for official event) and a few bottom X (TBC) students will be invited for the make up PE sometime during study week.
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 2024 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 is "up to you but", but do check what Java-related IDEs are available in our PLs.
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 ~4200+ 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 and his FYP students are working hard at the background to continuously improve 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 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 much larger algorithm class (CS2040/C/S are projected to be as big as of now (over 1000 students per batch) in future AYs as NUS SoC freshmen intake remains at high level — but Prof Halim feels the student intake number will plateau soon).
Q: What are the potential changes that you will apply to CS2040/C/S in S1 AY 2024/25 compared to your many earlier runs of this course?
A: NUS @ Kattis is still used. Prof Halim only plan to change these variables this time (all others are planned to be kept roughly constant):
  1. From S1 AY24/25, IT5003 (Python) also starts from Week 01. That course only has 2 hours Wednesday night lecture per week instead of 2+1 = 3 hours and will end by Week 12 instead of Week 13. 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 morning (9-10am XYb lecture).
  2. 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..., i.e., he is consciously making the course a bit easier, closer to IT5003 version.
  3. Prof Halim had disappeared three times: on Week 04 (IOI 2024, Alexandria, Egypt), on Week 06 (ICPC World Finals 2024, Astana, Kazakhstan), and on Week 09 (ICPC Challenge Championship powered by Huawei). On all weeks, Prof Halim had been substituted by TAs.
  4. Since our Thursday lecture slot is moved from 5-6pm (evening) to 9-10am (morning), Prof Halim decides to halve the duration (and thus the difficulty) of PE. The weightage of 15% PE is now reduced to 11% and the 4% is spread to midterm and the usually easier VisuAlgo Online Quizzes.

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

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 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)
(solving many 'trivial problems' from this set
---trackable by Prof Halim, indirectly tells him
about your CS1101S/IT5001/equivalent rough grade)
Dr Chong Ket Fah ran CS2040 placement test
for AY24/25 incoming IOI medallists
on Fri, 02 August 2024, 9-11am
 		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 Java
Setting the tone for a flipped classroom course
VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open)
Basic Java 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 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 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, 14 Aug 24, 11.29am
PS1: Basic Programming
Out: Wed, 14 Aug 24, 11.30am
Mentioned at the end of the first lecture
CS2040S students do problem B+C
02,
19-23 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)
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)
02b. Algorithms on Sorted Array
Kattis 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, 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, 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)
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
Java Collections.sort, Arrays.sort (object), Arrays.sort (primitives)
Sorting Online Quiz (medium)
Kattis problem(s) discussed today:
sortofsorting (custom comparator, stable sorting library)
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
Prof Halim departed 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 was in Alexandria, Egypt,
for IOI 2024 (01-08 Sep 2024)
04a lecture was covered by Full-Time TA: Tzer Bin.
04b lecture was covered by TA: Ryan Tan.
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 Java ArrayList implementation versus Java LinkedList and Stack classes
Introducing Queue ADT and MyQueue implementation (another extension of SLLDemo)
DLL and Deque ADT
Fixed-size array, circular array version, versus Java Queue and Deque interfaces
Linked List Online Quiz (medium)
A few other LL technicalities
04b. List (Stack) Review
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),
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)
Introducing PQ ADT
Introducing basic Binary Heap structure and its Insert+ExtractMax operations
Discussing CreateHeap (two versions) and HeapSort operations
BinaryHeapDemo.cpp | py | java
Java PriorityQueue class; see priority_queue.cpp | py | java at GitHub repo of CPbook website
Last 15m of 05a: VisuAlgo Online Quiz 1 (7%)
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: /array (3 Qs), /sorting (3 Qs), /list (3 Qs),
and 3 'new' questions.
05b. PQ Extras (until end)
Clearing a few more details about Binary Heap
O(N) CreateHeap analysis and O(N+K log N) PartialSort
Max-to-Min heap conversions (numbers only)
Discussing UpdateKey(i, newv) and Delete(i) operations
Binary Heap Online Quiz (medium)
Kattis problem(s) discussed today:
rationalsequence3 (stack/LIFO and binary heap indexing)
Prof Halim departed to Astana, Kazakhstan 		PS3, continued
06,
16-20 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)
 		Prof Halim was in Astana, Kazakhstan,
for ICPC World Finals 2024 (15-20 Sep 2024)
NUS team got a historic Silver medal at that WF24 :)
06a lecture was covered by TA: Jason Christopher.
06b lecture was covered by TA: Timothy Wan.
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, 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+L05: tut05.pdf [Special]
Past midterm paper(s) discussions
 		First 15m of 07a: LL (wk4) + Hash (wk6) review
Then 7m break (paper distribution)
Next 70m of 07a: [10.22am-11.32am]: Midterm Quiz (11%)
Open book
A few short questions
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 (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,
07-11 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
Last 15m of 08a: VisuAlgo Online Quiz 2 (7%)
Material: /heap (4 Qs), /hashtable (4 Qs), /ufds (4 Qs),
and NO 'new' question.
Go and get your 'near free' 7%...
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)
Prof Halim departed to Shenzhen/Dongguan, China 		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,
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)
 		Prof Halim was in Shenzhen/Dongguan, China,
for ICPC Challenge Championship powered by Huawei
09a lecture was covered by TA: Chin Herng.
09b lecture was covered by Jonathan Irvin.
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
09b. Graph Traversal Applications (Slide 7-3 to 7-8)
Finding Connected Components
Kattis problem(s) discussed today:
weakvertices (AM demo)
reachableroads (AL demo; count #CC; DFS vs UFDS implementation)
 		PS5, continued
10,
21-25 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)
 		10a. Graph Traversal Applications (Slide 6 to 7-11)
Review Graph DS (AM, AL), DFS and introducing BFS
Focus on a few more basic DFS/BFS applications:
Reachability, Print Path, CC, Cycle Check, Toposort
(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:
reachableroads (BFS implementation this time)
builddeps (AL of Strings + postorder DFS toposort demo)
10b. Practical Exam (11%)
Thu, 24 Oct 2024, 8.50-9.50am (60m)
Just one task with a bit more of subtasks (instead of two tasks in two hours)
See official broadcast at Canvas announcement.
NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until you have done (the easy) VA OQ 3
 		PS5 (2%)
Due: Sat, 26 Oct 24, 07.59am
PS6: Graph Problems
Out: Sat, 26 Oct 24, 08.00am
Make-up time window: Wed, 23 Oct 2024, 9.45-10.00am
Official absentees for VA OQ 1 on Wk5: 8 pax (1 AWOL)
Official absentees for VA OQ 2 on Wk8: 11 pax (2 AWOLs), disjoint from the 8 pax above, but 3 out of 11 will only do this on Recess Week

Make-up time window: Wed, 23 Oct 2024, 3.00-4.10pm (NUSOne slot)
Official absentees for Midterm Quiz on Wk7: 3 pax (2 AWOLs), 2 overlap with the 19 above...
11,
28 Oct-01 Nov 		T09+L09: tut09.pdf
BFS Review
DFS/BFS advanced stuffs:
Cycle Detection, Toposort++, Floodfill/CC,
Modeling exercise,
PS5 Debrief (short),
VA OQ demo (dfsbfs),
CS2040S Only: short PE debrief by TA,
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 (original Dijkstra's first for CS2040S;
but modified Dijkstra's first for IT5003)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
modulosolitaire (SSSP; directed unweighted implicit graph; BFS)
shortestpath1 (basic Dijkstra's; focus on implemetation; for PS6B)
Thu, 31 Oct 2024 is Deepavali PH
CS2040S 11b lecture is cancelled

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 		T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (sssp),
Hands-on, an SSSP 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 problem(s) discussed today:
cats (MST application)
Onsite class photo as momento
Last 15m: VisuAlgo Online Quiz 3 (7%)
Material: /bst (3 Qs), /graphds (3 Qs), /dfsbfs (3 Qs), /sssp (3 Qs).
No new question, all 12 questions are as it is in VA OQ, hard mode setting.
12b. SSSP+MST Wrap-Up
QnA on Modified Dijkstra's
Other special cases of SSSP problem
Other MST Variants
 		PS6 (2%)
Due: Sat, 09 Nov 24, 07.59am
13,
11-15 Nov 		T11+L11: tut11.pdf
MST Review
Past final assessment paper(s) discussions
VA OQ demo (mst),
Class Photo (for momento)
Tut+Lab participation marks given (3%) 		13a. Make-up (or Remedial) Practical Exam slot
Wed, 13 Nov 2024 (10.10-11.10am, 60m)
Venue: SR@LT19 plus our own LT19
Details only given to those who are invited.
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.
 		No more :)
Study Week, 16-22 Nov 2024

Make-up VA Quiz 2+3 slot
Date: Tue, 19 Nov 2024
Venue: SR@LT19
Timing: Make-up VA OQ 2 (3 pax), 1.20-1.35pm
Timing: Make-up VA OQ 3 (11 pax, 2 overlap with above), 1.40-1.55pm

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 (our paper, a bit too hard), [Prof Halim does not teach CS2040S in S2].
NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Wed, 27 Nov 2024, 5.00-7.00pm
Venue: MPSH2-A (Prof Halim with 2 TAs) + COM3-01-22 (Special Needs)
Open book
40% MCQs (extremely tricky)
(the MCQs are there to speed up grading as Prof Halim has two other final assessments
on 13 Nov (33 pax) and 29 Nov (434 pax))
2 questions with shorter answers, the easier ones (20%)
3 application questions, the harder ones (40%)