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, binary search trees, and graphs), searching and sorting algorithms, basic analysis of algorithms, and very basic object-oriented programming concepts (more details of OOP are in CS2030).

The programming language used for this course is Java.

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 no longer teaching CS2040C starting from the recent S2 AY 2022/23, and this change may continue for several upcoming AYs.

Instead, Prof Halim is now teaching CS2040S in S1 AY 2023/24 (Aug-Nov 2023). He has gained significant experience teaching CS2040/C/S courses over the past half-decade, consistently receiving (far-above)-average course ratings compared to the NUS SoC average. In this upcoming semester (S1 AY 2023/24), the main difference is that Prof Halim is transitioning from CS2040C (C++) to CS2040S (Java), which is exclusively for CS students in SoC.

Some additional 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.460 (very good).
  2. Apart from teaching CS2040/C/S on multiple occassions from 2017 to the present, Prof Halim has also taught similar courses, including CS2020 once (2011), CS2010 six times (2011-2016), and CS1020E once (2016).
  3. Teaching staffs:
    Associate Professor Steven Halim, the key man behind VisuAlgo, a tool that will be extensively utilized in this course. The primary goal for this semester is for Prof Halim to swiftly refresh his Java coding skills after dedicating substantial time to the C++ (CS2040C) and Python (IT5003) versions of this course over the past half-decade.

    Rating
    (out of 5.0)    		 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% ▲    		 Aug-Dec 20
    (n=60/115)
    52% ▼
    Course feedback (SoC avg lvl 2000 ~3.9) 4.2 == 4.2 == 4.2 == (+Alan) 4.2 == 4.2 ▲ (+Alan) 3.8 ▼ (C-19+IOI 20)
    Course difficulty (SoC avg lvl 2000 ~3.8) 4.3 == 4.3 ▲ 4.2 == (high) 4.2 ▲ 3.9 ▼ (easiest) 4.6 ▲ (C-19+IOI 20)
    Prof Halim's teaching (SoC avg lvl 2000 ~4.2) 4.4 ▼ 4.5 ▲ 4.3 ▼ (+Alan) 4.5 ▲ 4.4 ▲ (+Alan) 4.3 ▼ (C-19+IOI 20)

    Date, Time Live Session (Venue) (#Stu/#Cap) No Tutor
    1/Mon, 1000-1200 COM1-B109 (PL2) (16/16) 01 Ayaz
    1/Mon, 1000-1200 COM1-B108 (PL3) (16/16) 02 Ren Weilin
    1/Mon, 1200-1400 COM1-B109 (PL2) (16/16) 03 Ramapriyan
    1/Mon, 1200-1400 COM1-B108 (PL3) (16/16) 04 Ryan Tan
    1/Mon, 1400-1600 COM1-B108 (PL3) (16/16) 05 Jason
    1/Mon, 1400-1600 COM1-B111 (PL4) (15/16) 06 Ernest Ng
    1/Mon, 1600-1800 COM1-B108 (PL3) (16/16) 07 Rezwan Arefin
    1/Mon, 1600-1800 COM1-B111 (PL4) (17/16) 08 Timothy Wan
    5/Fri, 2000-2200 (night) Zoom Recurring Link (free and easy) - At least 2 TAs/session
    6/Sat, 1000-1200 Zoom Recurring Link (free and easy) - Ren Weilin
  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 you will learn if you take CS2040/C/S taught by Prof Halim:

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 CS2040S S1 AY 2023/24 has onsite components?
A: Last S1 2022/23 with Dr Chong Ket Fah, there were two e-Learn lectures (2+1 hours), 8 e-Learn tutorials on Monday, and 8 e-Learn labs on Thursday. Prof Halim prefers all of these to be onsite for S1 2023/24 (and to merge tut+lab together) and I just got a confirmation (early June 2023) that it will be the case.
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 11, 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. Instead, the plan is to implement onsite proctoring with an 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 — some events are resuming...) 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 2023 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 ~3700+ 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).
Q: What are the potential changes that you will apply to CS2040/C/S in S1 AY 2023/24 compared to your many earlier runs of this course?
A: NUS @ Kattis is still used and the PE difficulty will be set to CS2040C S1 AY 2021/22 + S2 AY 2021/22 levels (S1 AY 2022/23 version was a bit too hard). However, these are the potential changes:
  1. 100% onsite class activities.
  2. Prof Halim will relearn (the latest version of) Java 11 (the one used in nus.kattis.com) during June-July 2023 holiday period (and throughout the semester).
  3. Reduce the weightage of the two-weeks Problem Sets (it is too difficult to fight ChatGPT/generative AI...), then increase the weightage of the Midterm and the two three VisuAlgo Online Quizzes.
  4. NEW: There may be a few SGP NOI 2023 Silver medallists joining this course under CeNCE project (CS2); update: only one...

Note: This course registration section will not be prominent from Week 1 of S1 AY 2022/23 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,
31 Jul-04 Aug 		Has Not Started Has Not Started, but please revise your CS1010/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 (CS1010/equivalent level):
(solving many 'trivial problems' from this set
---trackable by Prof Halim, indirectly tells him
about your CS1010/equivalent rough grade)
 		PS0: Easy Java/coding challenges
(02-16 Aug)
already graded to speed up
registration admins
Solve any 3 out of 10 tasks for 1%.
00,
07-11 Aug
 Has Not Started Has Not Started, but please continue revising your CS1010/equivalent

Continue attempting PS0 (hints in class Discord)

 Singapore National Day on Wed, 09 August 2023
This time, CS2040S first lecture is not affected
 PS0, continued
01,
14-18 Aug 		Has Not Started 01a. Course Admin, (Re-)Introduction to Java
Setting the tone for a flipped classroom plus all ONSITE 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)
01b. (Re-)Introduction to Java (continued)
Kattis problem(s) discussed today:
rankproblem (a new 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 Lecture 02a
 		PS0 (1%)
Due: Wed, 16 Aug 23, 11.29am
PS1: Basic Java
Out: Wed, 16 Aug 23, 11.30am
Mentioned at the end of the first lecture
02,
21-25 Aug 		Has Not Started

But (e-)Consultation starts
from Fri, 25 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)

Reminder: Read sorting e-Lecture slides (Slide 1 to 11-11)
before Lecture 02b
02b. Sorting (Slide 1 to 11-11)
O(N log N) sorting algorithm: Merge Sort
Java Collections.sort, Arrays.sort (object), Arrays.sort (primitives)
Kattis problem(s) discussed today:
heirsdilemma (brute force math; O(1M possibilities * 6 digits) - 'small')
sortofsorting (NEW: custom comparator, Java Collections.sort)

Last flipped classroom reminder: Read ALL sorting e-Lecture slides
before Lecture 03a
Prof Halim departed to Europe
a few hours after this lecture 02b. 		PS1 (2%)
Due: Sat, 26 Aug 23, 07.59am
PS2: Sorting-related Problems
Out: Sat, 26 Aug 23, 08.00am
03,
28 Aug-01 Sep 		T01+L01: tut01.pdf
Introduction,
OOP review (List ADT/ListArray)
Analysis,
Hands-on, cutinline
(basic List ADT tasks)
PS1 Debrief (short),
PS2 Discussion (algorithmic)
 		Prof Halim was in Szeged, Hungary,
for IOI 2023 (28 Aug-04 Sep 2023)
03a+03b lectures have been recorded.
PS: There was also SoC Career Fair on 29-30 Aug.
03a. Sorting (until end)
Another O(N log N) sorting algorithm: (Randomized) Quick Sort
See the details at SortingDemo.cpp | py | java
Special-purpose O(N) sorting algorithm: Counting Sort (Only)
Other topics of sorting e-Lecture
Sorting Online Quiz (medium)
03b. Mock Practical Exam 1
Material: Java/ArrayLists/Sorting
(Prof Halim also recorded his live-(re-)solving attempt)
A preparation for Midterm Quiz and future Practical Exam
Kattis problem(s) discussed today:
laptopstickers (simple 2D array/grid manipulation)
gearchanging (sort gear ratios and check change of cadence)
 		PS2, continued
04,
04-08 Sep 		T02+L02: tut02.pdf
Sorting Application(s),
Sorting, mini experiment,
QuickSelect,
ADT/List ADT (array vs ArrayList),
VA OQ demo (sorting),
Hands-on, basicprogramming2
(many applications about sorting)
PS2 Discussion (algorithmic)
 		04a. List ADT: (Singly) LL/Stack/Queue (Slide 1 to 5-6)
Introducting List ADT, (resizeable) array implementation, and SLL implementation
SLLDemo.cpp | py | java
Introducing Stack ADT and MyStack implementation (extension of SLLDemo)
Java LinkedList and Stack classes
Stack, but using (resize-able) Array implementation
Introducing Queue ADT
04a. Queue ADT, DLL, and Deque ADT (until end)
Introducing MyQueue implementation (another extension of SLLDemo)
Queue, but using (resize-able) Array implementations (2 ways)
DLL and Deque ADT (no DLLDemo, may be needed for your PS3)
Java Queue and Deque interfaces
A few other LL technicalities
Linked List Online Quiz (medium)
Kattis problem(s) discussed today:
delimitersoup (classic bracket matching variant; use a stack/LIFO)
 		PS2 (2%)
Due: Sat, 09 Sep 23, 07.59am
PS3: List+PQ Problems
Out: Sat, 09 Sep 23, 08.00am
05,
11-15 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, joinstrings
(list concatenation; several ways)
PS3 Discussion (algorithmic)
 		05a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3)
Introducing PQ ADT
Introducing basic Binary Heap structure and its Insert+ExtractMax operations
Discussing other PQ ADT details and Binary Heap implementation
BinaryHeapDemo.cpp | py | java
05b. Priority Queue (PQ) (until end)
Clearing a few more details about Binary Heap
Java PriorityQueue class
See priority_queue.cpp | py | java at GitHub repo of CPbook website
Binary Heap Online Quiz (medium)
Kattis problem(s) discussed today:
rationalsequence3 (stack/LIFO and binary heap indexing)
 		PS3, continued
06,
18-22 Sep 		T04+L04: tut04.pdf
Binary Heap,
Max-Min conversion,
Additional ADT PQ Operations,
Java PriorityQueue,
VA OQ demo (heap),
PS3 last Discussion (algorithmic)

We will skip the hands-on session today
so that we have time for Midterm Quiz QnA
 		First 15m: VisuAlgo Online Quiz 1 (6%)
Time window: [10.02-10.17am] (15 Qs, 15 mins).
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: /sorting, /list, /heap (2 Qs), and a few 'new' questions.
 Short Break
Next 70m: Midterm Quiz (11%)
Time window: [10.26am-11.36am] (70 minutes).
Open laptop (but no Internet)
A few short questions (close-ended) and one (hard) essay question
No more giveaway questions (the questions are either tricky or hard)
There will be 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)

Midterm Test Past Papers (recent 3 AYs only):
AY 2021/22: S1-midterm.pdf, S2-midterm.pdf (myself + Dr Alan),
AY 2022/23: S1-midterm.pdf, [I didn't teach CS2040C in S2],
AY 2023/24: S1-midterm.pdf (our paper), [I don't teach CS2040S in S2].
06b. Union-Find Disjoint Sets (all slides)
Live 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 will be reused in Connected Component (CC) and MST topics
 		PS3 (2%)
Due: Sat, 23 Sep 23, 07.59am
PS4: UFDS+Hash Table Problems
Out: Sat, 23 Sep 23, 08.00am
Recess Week, 23 Sep-01 Oct 2023
You can take a break this week :)
Prof Halim and a full-time TA has graded your Midterm Quiz during this period
But if possible, read Hash Table e-Lecture slides by yourself first...
07,
02-06 Oct 		T05+L05: tut05.pdf
Midterm Quiz Review,
UFDS Review,
VA OQ demo (ufds),
Hands-on 1: speedrun
(classic greedy involving sorting)
Hands-on 2: annoyedcoworkers
(a greedy problem involving PQ)
PS4 Discussion (algorithmic)
 		07a. Table ADT part 1: Hash Table (Slide 1 to 7-11;
then 10 to 10-3)
Table ADT and DAT
Basic Hashing Concepts
One Collision Resolution Technique: OA (LP)
Another Collision Resolution Technique: CA (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; to showcase HashSet and/vs our own HashTableDemo.java)
07b. Hash Table, Continued (Slide 8 to 9-3;
then Slide 11 until end)
More Collision Resolution Techniques: OA (QP and DH)
Comparing OA: DH with CA: SC
HashTableDemo.cpp | py | java (all use SC)
Other technicalities of Hash Table
Hash Table Online Quiz (easy; tedious on medium/hard settings)
 		PS4, continued
08,
09-13 Oct 		T06+L06: tut06.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
PS3 Debrief (short),
Java HashSet/HashMap,
VA OQ demo (hashtable),
Hands-on: bokforing
(hash table application)
PS4 Discussion (algorithmic)
 		08a. Table ADT part 2: BST + AVL Tree (until end)
BST concepts and the various BST operations
NEW: The multiset idea
QnA about AVL Tree concepts
08b. Balanced BST Applications
BST (only) Online Quiz (medium)
BST+AVL Online Quiz (hard; need to clear pre-req)
BSTDemo.cpp | py | java
AVLDemo.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, 14 Oct 23, 07.59am
PS5: Combo DS+Graph DS Problems
Out: Sat, 14 Oct 23, 08.00am
09,
16-20 Oct 		T07+L07: tut07.pdf
Table ADT 2 - ordered,
BST/AVL 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: coursescheduling
(a combo DS task)
PS5 Discussion (algorithmic)
 		09a. Graph DS
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,
Kattis problem(s) discussed today:
weakvertices (Adjacency Matrix demo)
Last 15m: VisuAlgo Online Quiz 2 (6%)
Approx time window: [11.20-11.35am] (15 Qs, 15 mins).
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: /heap (≥ 3 Qs), /ufds (≥ 3 Qs), /hashtable (≥ 3 Qs), /bst (≥ 3 Qs),
and of course the rest are 'new' questions.
09a. Graph Traversal (Slide 1 to 5-8)
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 (count #CC, DFS introduction)
 PS5, continued
10,
23-27 Oct 		T08+L08: tut08.pdf
Graph DS Review,
Some Graph Properties Discussion,
Graph DS Conversion Exercise,
DFS/BFS Review,
UFDS Revisited,
Custom graph DS implementation review,
VA OQ demo (graphds,dfsbfs),
Hands-on: hermits
(a simple Graph DS task)
PS5 Discussion (algorithmic)
 		10a. Graph Traversal (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 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 (count #CC, replace DFS with BFS)
builddeps (Adjacency List of Strings + postorder DFS toposort demo)
10b. Mock Practical Exam 2
Material: Everything so far, from Week 01 until Week 10a: Graph Traversal
(only first 45 minutes have commentary)
Prof Halim is not aiming for full marks today, but will show how to avoid zeroes...
Kattis problem(s) discussed today:
teque (list ADT task)
nicknames (table ADT task)
ads (graph traversal task)
NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until you have done PE + VA OQ 3
 PS5 (2%)
Due: Sat, 28 Oct 23, 07.59am
PS6: SSSP+(Easy) MST Problems
Out: Sat, 28 Oct 23, 08.00am
Make-up time window
Those who miss VisuAlgo Online Quiz 1 + Midterm Quiz on Week 06 or VisuAlgo Online Quiz 2 on Week 09 due to VALID reasons
(valid Medical Certificate; representing NUS for an official event; bereavement of immediate family member)
do make up on Week 10 (details only for those eligible).
Note that there is no more make up of make up :O...
11,
30 Oct-03 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),
Tips for VA OQ 3 next week,
Past PE Reviews
 		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 (both versions, details on 12b)
See dijkstra.cpp | py | java at GitHub repo of CPbook website
Kattis problem(s) discussed today:
modulosolitaire (SSSP; unweighted graph; BFS; implicit graph)
11b. Practical Exam (15%)
Thu, 02 Nov 2023, 5.05-7.05pm (120m)
LT15 is available for us during this two-hours block (have deconflicted)
We will use BYOD (Bring Your Own Device) at LT15
but with Safe Exam Browser
Not Open-Internet (Generative AI tools make this scary)
Material: Week 01 until Week 10b.
NO LONGER OPEN INTERNET PE...
All other details in Canvas announcement.
 		PS6, continued
12,
06-10 Nov 		T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (ufds,hashtable,bst,graphds,dfsbfs,sssp),
Hands-on: onaveragetheyrepurple (unweighted SSSP),
PS6 Discussion (algorithmic)
(short PE debrief by TA)
Class Photo (for momento)
Tutorial Participation Marks given (3%)
 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:
shortestpath1 (basic Dijkstra's)
cats (MST application)
Onsite class photo as momento
Last 15m: VisuAlgo Online Quiz 3 (6%)
Approx time window: [11.20-11.35am] (15 Qs, 15 mins).
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
Material: all CS2040S topics excluding /mst.
12b. SSSP+MST Wrap-Up
QnA on Bellman-Ford algorithm (the general algorithm)
QnA on other special cases of SSSP problem
Other MST Variants
Fri, 10 Nov 2023 is chosen as
NUS well-being day S1 AY 2023/24

Prof Halim will depart to Sharm el-Sheikh, Egypt,
on Sat, 11 Nov 2023 night
WF22+23 is postponed again... due to war...
 		PS6, continued
13,
13-17 Nov 		Sun, 12 Nov 2023 is Deepavali PH
Thus, Mon, 13 Nov 2023 is also a PH
CS2040S last tutorial is cancelled
/mst will be asked in final as an 'easy Q'
 		Prof Halim will be in Sharm el-Sheikh, Egypt,
for combo ICPC World Finals 2022+2023 (12-17 Nov 2023)
WF22+23 is postponed again... due to war...
13a will be cancelled (WF22+23 date) and
13b will be recorded
13a will be used for make-up slot and 13b will be live
Make-up (or Remedial) Practical Exam
Wed, 15 Nov 2023 (09.35-11.35am, 120m)
Venue: LT15
Details only given to those who are invited.

Make-up VisuAlgo Online Quiz 3
Venue: LT15
Timing: 10.00-10.15am (parallel with make-up PE if no overlap; we use this now)
Timing: 11.38-11.53am (if got overlap with make-up PE; now we don't have)
13b. The Last Lecture
Course wrap-up et al:
Undoing all the illegal Java coding techniques,
Semester summary,
Review of what can be done better for future iterations,
Advertisement of future (algorithm) courses: CS3233 or CS3230 → CS4234
Advertisement for part-time TA jobs (A-/A/A+ only),
Ending: a few Final Assessment Tips.
Final Preparation Tracker at nus.kattis
 		PS6 (2%)
Due: Fri, 17 Nov 23, 07.59am
Study Week, 18-24 Nov 2023

Final Assessment Consultations (per request)

Final Assessment Past Papers (recent 3 AYs only, note the transition from CS2040C/C++ to CS2040S/Java):
AY 2020/21: S1-final.pdf, S2-final.pdf (Dr Alan+myself),
AY 2021/22: S1-final.pdf, S2-final.pdf (most recent past paper),
AY 2022/23: S1-final.pdf, [Prof Halim didn't teach CS2040C in S2],
Final Preparation Tracker at nus.kattis
AY 2023/24: S1-final.pdf (our paper).
NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Fri, 01 Dec 2023, 2.30-4.30pm
Venue: MPSH5
Open book but *not* Open Laptop (prepare accordingly)
50% MCQs (extremely tricky)
(the MCQs are there to speed up grading as Prof Halim has other final assessments
on 30 Nov (57 pax), ICPC Asia Jakarta (01-04 Dec), and 07 Dec (201 pax))
3 essays (20% easy+15% medium+last 15% differentiator question)