CS2040C - Data Structures and Algorithms (C++)

Prof Halim is no longer teaching CS2040C.
He is teaching CS2040S in Sem 1 instead.
This page below is very outdated.

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 C++ (as of 2022, we still use C++17, pick up as much as possibly via self-learn from this site: learncpp.com).

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

Steven teaches CS2040C (NOT CS2040 — contact Prof Roger Zimmermann and A/Prof Tan Sun Teck — nor CS2040S — contact Dr Chong Ket Fah) in S1 AY 2022/23 (Aug-Nov 2022). Steven already had enough experiences teaching CS2040/C/S course in previous half decade (many times, all course ratings are above NUS SoC average). This S1, there is a major change where the majority of 200-about 50 pax = 150 other pax of Computer Engineering (CEG) students from August 2021 intake will take CS2040C in their sem 3 (S1 AY 2022/23 - this semester).

There are a few exchange students as exchange programme has restarted in 2022.

Some other facts:

  1. Steven uses flipped classroom, machine-teach-(and-auto-test)-students-on-basic-stuffs, and in-class live discussion of (hard)er problems in his CS2040/C/S classes many times in recent AYs (AY 2017/18 - present). His teaching feedback ratings for those offerings vary in [4.2 (just slightly above average)..4.8 (v good)] bracket out of maximum 5.0.
  2. On top of teaching CS2040/C/S many times so far (2017-present), Steven has also taught other similar modules: CS2020 once (2011), CS2010 six times (2011-2016), and CS1020E once (2016).
  3. Teaching staffs:
    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used very extensively in this course.
    The main target for this semester is to have many onsite components (see below for the details).
    Rating
    (out of 5.0)
    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%
    Aug-Dec 19
    (n=56/96)
    58%
    Course feedback (SoC avg ~3.9) 4.2 == (more than target) 4.2 == (+Alan) 4.2 == 4.2 (+Alan) 3.8 (C-19+IOI 20) 4.0 ==
    Course difficulty (SoC avg ~3.8) 4.3 (wah, increases) 4.2 == (hm, still high) 4.2 3.9 (easiest) 4.6 (C-19+IOI 20) 4.2
    Steven's teaching (SoC avg ~4.2) 4.5 (more than target) 4.3 (+Alan) 4.5 4.4 (+Alan) 4.3 (C-19+IOI 20) 4.4
    Date, Time Live Session (Venue) (#Stu/#Cap) No Tutor
    1/Mon, 1000-1200 COM1-0120 (PL6) (25/28) 02 ayaze
    1/Mon, 1200-1400 COM1-0120 (PL6) (28/28...) 03 dZhei
    1/Mon, 1400-1600 COM1-0120 (PL6) (29/28...) 04 RezwanArefin01
    1/Mon, 1600-1800 COM1-0120 (PL6) (12/28) 05 T1duS
    2/Tue, 1000-1200 COM1-0120 (PL6) (26/28) 06 rama_pang
    2/Tue, 1200-1400 COM1-0120 (PL6) (29/28...) 07 athin
    2/Tue, 1400-1600 COM1-0120 (PL6) (28/28) 08 Berted
    2/Tue, 1600-1800 COM1-0120 (PL6) (29/28...) 09 jialin
    3/Wed, 2000-2100
    (1h consultation slot)
    Zoom Recurring Link (free and easy) - jialin
    3/Wed, 2200-2300
    (1h consultation slot)
    Class Discord Study Room 2 - T1duS (online, free and easy) - T1duS
    4/Thu, 2000-2100
    (1h consultation slot)
    Zoom Recurring Link (free and easy) - RezwanArefin01
    4/Thu, 2100-2200
    (1h consultation slot)
    Class Discord Study Room 1 - dZhei (online, free and easy) - dZhei
    5/Fri, 1000-1100
    (1h consultation slot)
    Zoom Recurring Link (free and easy) - ayaze
    5/Fri, 1300-1400
    (1h consultation slot)
    NUS ICPC lab COM1-02-15 (onsite, free and easy) - Berted
    5/Fri, 1500-1700
    (the only 2h consultation slot)
    Zoom Recurring Link (free and easy) - athin
    5/Fri, 2000-2100
    (1h consultation slot)
    Zoom Recurring Link (free and easy, PS deadlines last minute help) - rama_pang

    List of TAs:

    1. @athin, Ammar Fathin Sabili ("full-time" TA and PhD student)
    2. @ayaze, Muhammad Ayaz Dzulfikar (PhD student)
    3. @Berted, Edbert Geraldy Cangdinata
    4. @T1duS, Udit Sanghi
    5. @dZhei, Joshua Nee Ting Feng
    6. @jialin, Cai Jia Lin
    7. @rama_pang, Rama Aryasuta Pangestu
    8. @RezwanArefin01, Rezwan Arefin
  4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
  5. 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 Steven:

Course Registration Additional FAQ

If you have any important questions regarding this course, email stevenhalim at gmail dot com. Relevant answers will be posted here to reach wider audiences.

Q: Will CS2040C S1 AY 2022/23 has onsite components?
A: Yes. For the lecture component, we will have onsite sessions on Wednesdays at LT15 (venue booked) but online sessions on Thursday (venue (COM3-MPH123) is not ready to be used). For the Tut+Lab combo, we will run all lab sessions in F2F mode. All formal assessments of this course: Midterm Test + VisuAlgo Online Quiz 1 on Wed of Week 07 (moved backwards from initially Week 06, additional venue booked), Practical Exam on Week 11 (evening, venue booked), VisuAlgo Online Quiz 2 on Wed of Week 12, and Final Assessment will all be F2F.
Q: Will there be a Practical Exam (PE) for your version of CS2040/C/S?
A: Yes, once only, on Week 11 (everything up to just before graph data structure).
We will do the scary-sounding Open Internet PE but with onsite proctoring. This time, students who are still overseas will be deemed as absent, so plan accordingly.
Q: Open Internet PE sounds scary... Will there be a make up PE if I am sick/underperform...?
A: Yes. Steven 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, 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: CS2040C 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 C/C++, should I pick up C++ on my own during this May-June-July 2022 University Holiday?
A: Yes, that is a very good idea. We will only review basic C++ in the first few weeks of this course and then Steven will encourage you to self-learn C++ along the way. One very good resource is learncpp.com. A few early admin emails will be sent to students who are already enrolled from 23 June 2022 onwards to start this process early.
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" we recommend Visual Studio that is confirmed available in various PLs in NUS SoC. But since PE for this semester is likely using the same BYOB (Bring Your Own Device) style, then you are free to use any C++ IDE that you are most comfortable with.
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 ~3600+ 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 has CS1010 as pre-requisite and according to Registrar's Office: "The S/U option will apply to all Level 1000 modules (with or without pre-requisites) and Level 2000 modules without other NUS modules 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. This AY 2022/23, Steven and his three 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 Steven to scale himself (one person) to handle much larger algorithm class (CS2040/C/S are projected to be as big as of now (over 1500 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 2022/23 compared to your nine earlier runs of this course?
A: NUS @ Kattis is still used and the PE difficulty level of S1 AY 2021/22 + S2 AY 2021/22 are 'good enough', so the standard will be kept at those levels. However, these are the potential changes:
  1. More onsite components, especially assessment related, as Singapore moves towards COVID-19 endemicity.
  2. Steven will further balance the discussion of detailed data structures/algorithms with its C++ STL counterpart.
  3. There is a need to transition from LumiNUS to Canvas this semester... Steven is learning along with most students.

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
-02/-01,
Bef Mon,
08 Aug
Not Started Not started, but please revise your CS1010
(Steven 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 C++ specific instructions @ Kattis,
pick up basic C++ by yourself via learncpp.com,
and solve the selected optional Online Judge (OJ)
Problem Set 0 (PS0) by yourself (CS1010 level):
(solving many 'trivial problems' from this set
---trackable by Steven, indirectly tells Steven
about your CS1010 rough grade)
PS0: Easy C++/coding challenges
(18 Jul-10 Aug)
obviously not graded
01,
08-12 Aug
Not Started Singapore National Day on Tue, 09 August 2022
CS2040C first lecture is not affected

But Steven is in Yogyakarta, Indonesia, for IOI 2022
Thus both Lectures on Week 01 were online but live


01a. Course Admin, (Re-)Introduction to C++
Setting the tone for a flipped classroom plus mostly ONSITE course
PS: *Except* for Wed, 10 Aug 2022 AM, as Steven is physically at Yogyakarta this day
VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open)
Basic C/C++ review/new feature introduction
Kattis problem(s) discussed today:
socialdistancing2 (introducing C++ std::vector/Boolean array)

01b. (Re-)Introduction to C++ (continued)
Kattis problem(s) discussed today:
vectorfunctions (more about C++ functions (const, &) and std::vector)
rankproblem (a new List ADT task; iota; std::vector insert and erase operations)

Reminder: Read summary on algorithm analysis (Slide 6 to 6-11)
before Lecture 02a
PS0
Due: Wed, 10 Aug 22, 11.59am
(0%)

PS1: Basic C++
This is now graded
Out: Wed, 10 Aug 22, 12.00nn
Mentioned at the end of the first lecture
02,
15-19 Aug
Not Started

But there will be one optional session
for official PS1 Discussion (algorithmic)
after Lecture 02b (same Zoom link),
but not recorded and this is done on purpose
02a. Analysis of Algorithms (Slide 6 to 6-11)
Live SpeedTest.cpp | py | java demo
(measure runtime, count # of operations, vs asymptotic analysis)
Kattis problem(s) discussed today:
rankproblem (NEW: recoded using C++ class)
thanos (Analysis: exponential growth, logarithmic steps)

Reminder: Read sorting e-Lecture slides (Slide 1 to 9-3)
before Lecture 02b

02b. Sorting (Slide 1 to 9-3)
C++ STL algorithm: std::sort, std::stable_sort
Kattis problem(s) discussed today:
mjehuric (bubble sort simulation),
height (insertion sort simulation),
sortofsorting (NEW: custom comparator, C++ STL std::stable_sort vs std::sort)
PS: stay back if you are still struggling with PS1

Last flipped classroom reminder: Read ALL sorting e-Lecture slides
before Lecture 03a
PS1
Due: Sat, 20 Aug 22, 07.59am
(1%)

PS2: Sorting-related Problems
Out: Sat, 20 Aug 22, 08.00am
03,
22-26 Aug
(e-)Consultation starts
Review demo code so far, focusing on
C++ STL (algorithm, std::vector, std::string)

T01+L01: tut01.pdf
Introduction,
OOP review (List ADT/ListArray)
Analysis,
Hands-on,
PS1 Debrief (short),
PS2 Discussion (algorithmic)
03a. Sorting (until end)
O(N log N) sorting algorithms: Merge and (Randomized) Quick Sort
See the details at SortingDemo.cpp | py | java
Special-purpose O(N) sorting algorithms: Counting and Radix Sort
Other topics of sorting e-Lecture
Sorting Online Quiz (medium)

03b. List ADT: (Singly) LL (Slide 1 to 3-22)
Introducting List ADT, (resizeable) array implementation, and SLL implementation
SLLDemo.cpp | py | java
C++ STLs: std::forward_list (an SLL), std::list (a DLL)
PS2, continued
04,
29 Aug-02 Sep
T02+L02: tut02.pdf
Sorting Application(s),
Sorting, mini experiment,
ADT re-introduction,
List ADT (array vs std::vector),
VA OQ demo (sorting),
Hands-on,
PS2 Discussion (algorithmic)
04a. Stack/Queue/Deque ADT (DLL) (until end)
Focus on Stack, Queue, DLL, Deque
Showing the implementations of MyStack and MyQueue (extension of SLLDemo)
Plus a few other LL technicalities
C++ STLs: std::stack, std::queue, std::deque (actually not a DLL)
Linked List Online Quiz (medium)
Kattis problem(s) discussed today:
circuitmath (classic postfix evalution; use a stack/LIFO)

04b. Priority Queue (PQ) ADT: Binary Heap (Slide 1-6)
Introducing PQ ADT
Introducing basic Binary Heap structure and its Insert+ExtractMax operations
PS2
Due: Sat, 03 Sep 22, 07.59am
(3%)

PS3: List-related Problems
Out: Sat, 03 Sep 22, 08.00am
05,
05-09 Sep
T03+L03: tut03.pdf
List/Stack/Queue/Deque ADT,
Linked List, mini experiment,
Applications
PS2 Debrief (short),
C++ STL (std::list/std::stack/std::queue/std::deque),
VA OQ demo (list),
PS3 Discussion (algorithmic)
05a. Priority Queue (PQ) (until end)
Discussing other PQ ADT details and Binary Heap implementation
BinaryHeapDemo.cpp | py | java
C++ STL: std::priority_queue, std::partial_sort
See priority_queue.cpp at GitHub repo of CPbook website
Binary Heap Online Quiz (medium)
Kattis problem(s) discussed today:
rationalsequence3 (stack/LIFO and binary heap indexing)

05b. Mock Practical Exam 1
Material: C++/Arrays/Vectors/Sorting/List/simpler PQ
(60 minutes with commentary; 2nd hour up to you)
A preparation for Midterm Quiz or future Practical Exam
Kattis problem(s) discussed today:
babypanda (think backwards; logarithmic)
gearchanging (sort gear ratios and check change of cadence)
heap (reinvent the wheel: BinaryHeapDemo.cpp or std::priority_queue)
PS3, continued
06,
12-16 Sep
T04+L04: tut04.pdf
PQ ADT
Binary Heap,
Additional ADT PQ Operations,
C++ STL (std::priority_queue),
Max-Min conversion,
VA OQ demo (heap),
PS3 last Discussion (algorithmic),
Hands-on 1,
Hands-on 2
06a. Table ADT part 1: Hash Table (Slide 1 to 6-2;
then 10 to 10-3)
Table ADT and DAT
Basic Hashing Concepts
One Collision Resolution Technique: CA (SC) first
Hash Table Online Quiz (easy)
HashTableDemo.cpp | py | java (all use SC)
C++ STLs: std::unordered_set, std::unordered_map, ums, umm
See unordered_map_unordered_set.cpp at GitHub repo of CPbook website
Kattis problem(s) discussed today:
proofs (a simple table ADT task; to showcase our own HashTableDemo.cpp)

06b. Hash Table, Continued (Slide 7 to 9-3;
then Slide 11 until end)
More Collision Resolution Techniques: OA (LP, QP, and DH)
Comparing OA: DH with CA: SC
Other technicalities of Hash Table
Hash Table Online Quiz (medium)
PS3
Due: Sat, 17 Sep 22, 07.59am
(3%)

PS4: PQ/HashTable-related Problems
Out: Sat, 17 Sep 22, 08.00am
Recess Week, 17-25 Sep 2022
We can take a break this week :)
But if possible, read UFDS e-Lecture slides by yourself first...
07,
26-30 Sep
T05+L05: tut05.pdf
Table ADT 1 - unordered,
Basic hashing concepts,
Hash Table issues,
PS3 Debrief (short),
C++ STL (um and us, plus optional umm/ums),
VA OQ demo (hashtable),
PS4 Discussion (algorithmic)

We will skip the hands-on session today
so that we have time for Midterm Quiz QnA
We will split the class (now of size 207) into two halves.
Look at your own full name as displayed in Canvas.
108 students ['Ae Shintaro'..'Muthya Narayanachary Akhil'] go to LT15.
(invigilator: @rama_pang).
99 students ['Nam Sangjun'..'Zhu Jingxi'] go to LT18.
(invigilator: @RezwanArefin01).
Students at LT18 group but wrongly appear at LT15 will be ask to 'run to LT18...'

First 15m: VisuAlgo Online Quiz 1 (5%)
Bring your own laptop that can run at least 15 minutes on battery power.
(we do not provide any spare laptop).
(we provide 5 power extension bars in each LT --- only for emergency cases).
207 pax will be divided into 3 staggered groups to balance server load:
[10.02-10.17am, 10.03-10.18am, 10.04-10.19am].
Material: /sorting, /list, /heap, and a few 'new' questions.
FAQ 1: Your VA OQ grouping is *not* the same as your LT15 vs LT18.
So check your time window at VA OQ system carefully (login and see).
FAQ 2: Review the first few slides of 04ab.List2-Heap.pptx for the setup.

Short 5-10m break
Aiming to start the next segment at 10.30am.

Next 60m: Midterm Quiz (9%)
Approx time window: [10.30am-11.30am]
Just a few short and essay questions
No more giveaway questions (the questions are either tricky or hard)
You can continue using your laptop (airplane mode) as it is 'open laptop'
(e.g., you want to test code your answer, thereby turning midterm into PE)
But if you don't need it, you can use any printed stuff ('open book')
(but we don't encourage you to kill trees..., using laptop as 'book' is better)
Material: Up to PQ (L05ab on Week 05 + T04+L04 on Week 06)
FAQ: Hash Table is NOT INCLUDED,
all questions can be answered without hash table

Midterm Test Past Papers (recent 3 AYs only):
AY 2019/20: S1-midterm.pdf, S2-midterm.pdf (Dr Alan, N/A),
AY 2020/21: S1-midterm.pdf, S2-midterm.pdf (Dr Alan + myself, N/A),
AY 2021/22: S1-midterm.pdf, S2-midterm.pdf (myself + Dr Alan),
AY 2022/23: S1-midterm.pdf (our paper).

07b. Union-Find Disjoint Sets (all slides)
Live Quick Recap with VisuAlgo
See unionfind_ds.cpp 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
PS4, continued
08,
03-07 Oct
T06+L06: tut06.pdf
Midterm Quiz Review,
UFDS Review,
VA OQ demo (ufds),
Hands-on,
PS4 Discussion (algorithmic)
08a. Table ADT part 2: BST + AVL Tree (until end)
BST concepts and basic BST operations
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 and AVLDemo.cpp | java
C++ STLs: std::set, std::map, std::multiset, std::multimap
See map_set.cpp at GitHub repo of CPbook website
Kattis problem(s) discussed today:
kattissquest (multiple DS implementation exercise)
PS4
Due: Sat, 08 Oct 22, 07.59am
(3%)

PS5: Heavy DS Problems
Out: Sat, 08 Oct 22, 08.00am
09,
10-14 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,
C++ STL (map and set; plus optional mm/ms),
PS4 Debrief (short),
VA OQ demo (bst or avl (need to clear pre-req))
Hands-on,
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 at GitHub repo of CPbook website,
Kattis problem(s) discussed today:
weakvertices (Adjacency Matrix demo)

09a. Graph Traversal (Slide 1 to 6-4)
Early discussion of the basic forms of
two basic Graph Traversal algorithms: DFS and BFS
Kattis problem(s) discussed today:
builddeps (Adjacency List of Strings)
PS5, continued
10,
17-21 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,
PS5 Discussion (algorithmic)
10a. Graph Traversal (Slide 7 to 7-11)
Recap of Graph Traversal algorithms
Focus on 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 dfs_cc.cpp, UVa00469.cpp, and bfs.cpp at GitHub repo of CPbook website,
Kattis problem(s) discussed today:
reachableroads (DFS (/BFS) introduction, count #CC)
builddeps (toposort demo)
runningmom (AL of strings; DFS; back edge detection)

10b. Mock Practical Exam 2
Material: Everything so far, from Week 01 until Week 10a: Graph Traversal
(only first 45 minutes have commentary)
Kattis problem(s) discussed today:
hotsprings (sort and analyze)
coursescheduling (combo DS)
skyislands (simple DFS/BFS)

Fri, 21 Oct 2022 is chosen as
NUS well being day S1 AY 2022/23
No CS2040C class is affected

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 2

PS5
Due: Sat, 22 Oct 22, 07.59am
(3%)

PS6: SSSP+MST Problems
Out: Sat, 22 Oct 22, 08.00am
Those (2 pax) who miss Midterm Quiz on Week 07 due to VALID reasons
(valid Medical Certificate; representing NUS for an official event; bereavement of immediate family member)
do make up midterm quiz on Week 10.
Note that there is no more make up of make up :O...
11,
24-28 Oct
T09+L09: tut09.pdf
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 2 next week,
Past PE Reviews
Diwali Public Holiday is on Mon, 24 Oct 2022
CS2040C Monday classes are affected.
See the arrangement outlined in T09+L09: tut09.pdf.

11a. SSSP Problem (Slide 1 to end)
Review of basic SSSP problem
QnA on BFS algorithm for unweighted SSSP
QnA on Dijkstra's algorithm (the original form first)
SSSP Online Quiz (medium)
See bfs.cpp (again) and dijkstra.cpp at GitHub repo of CPbook website

11b. Practical Exam (15%)
Timing: Thu, 27 Oct 2022, 6.00-8.00pm (120m)
That is, our usual Thu (e-Lecture) slot is cancelled
we will do PE from 6.00pm and continues until 8.00pm.
(venue restrictions at other timeslots).
67 students ['Ae Shintaro'..'Justin Soh Jun Hao'] go to LT16.
(invigilator: @dZhei).
73 students ['Keane Chan Xing Zhao'..'Ryuji Kow Jie Si'] go to LT17.
(invigilator: @Berted).
67 students ['Samuel Tan Sze Wee'..'Zhu Jingxi'] go to LT18.
(invigilator: Marc Phua).
Material: Week 01 until Week 10b.
It is an Open Internet PE.
PS6, continued
12,
31 Oct-04 Nov
T10+L10: tut10.pdf
BFS/Dijkstra's review
Modeling exercises (continued),
VA OQ demo (ufds,hashtable,bst,graphds,dfsbfs,sssp),
Hands-on,
PS6 Discussion (algorithmic)
(short PE debrief by TA)
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 at LT15 as momento

11.22-11.42am or 11.23-11.43am:
VisuAlgo Online Quiz 2 (12%)
must be onsite at LT15 to have valid VA OQ 2 grade
(MC/COVID+ moved to make-up VA OQ 2 on 16 Nov)
bring your own laptop
visualgo.net/tests page must be full screen throughout the test
all topics, including SSSP
MST is not included (for final later)

12b. SSSP+MST Extras
QnA on Bellman-Ford algorithm
QnA on Modification of Dijkstra's algorithm
QnA on other special cases of SSSP problem
Other MST variants
PS6, continued
13,
07-11 Nov
T11+L11: tut11.pdf
Bellman-Ford + Modified Dijsktra Review
MST Review (2 algorithms),
Final paper preparation (from any past paper),
VA OQ demo (mst),
Hands-on, PS6 Last Discussion (algorithmic)
Class Photo (for momento)

Tutorial Participation Marks given (3%)
Steven is at Dhaka, Bangladesh, for ICPC World Finals 2021
(that has been postponed until this week, 06-11 Nov 2022)
a short recording of the last lecture 13a has been released
(hard to do live at 8-10am Dhaka time)

13a. The Last Lecture (e-Lecture)
Course wrap-up et al:
Undoing all the illegal C++ coding techniques,
Semester summary,
Review of what can be done better for future iterations,
Advertisement of future (algorithm) modules: CS3233 or CS3230 → CS4234
Advertisement for part-time TA jobs (A-/A/A+ only),
Ending: a few Final Assessment Tips.

Lecture 13b is cancelled
It is the ICPC World Finals 2021 date
PS6
Due: Thu, 10 Nov 22, 07.59am
(3%)
Study Week, 12-18 Nov 2022
Make-up (or Remedial) Practical Exam
Timing: Wed, 16 Nov 2022 (10.00am-12.00noon, 120m)
Venue: SR@LT19 (next to LT19)
Details only given to those who are invited.

Make-up VisuAlgo Online Quiz 2
Venue: SR@LT19 too
Timing: Wed, 16 Nov 2022 (12.15-12.35noon, 20m)
(only for those with MC/COVID+ on 2 Nov)

Final Assessment Consultations (per request)

Final Assessment Past Papers (recent 3 AYs only):
AY 2019/20: S1-final.pdf, S2-final.pdf (Dr Alan, N/A),
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),
Final Preparation Tracker at nus.kattis
AY 2022/23: S1-final.pdf (our paper).

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Sat, 26 Nov 2022, 1-3pm
Venue: MPSH2-B
39% MCQs (very tricky); 15% easy essay; 46% differentiator questions

Partial Class Roster

Steven uses a small-scale gamification system in his version of CS2040/C/S for extra study motivation.
The list of possible achievements are as follows: (achievements highlighted with red color/green color are already completed in the past/being given, respectively).
As the class size is large (more than 200), only students with at least one achievement will be listed below (so the list is not the full class roster).

  1. I Say Hi (#): Given to first 7 students who reply Steven's welcome email -- (sent on Thu, 23 Jun 2022, 4.15pm after seeing the non-zero class roster of 139 CEG students) with a long enough reply or write a (long enough) message at class Discord; Any early feedback will always help Steven in refining the preparation of the next iteration of this course
  2. Kiasu lv 1 (#): Given to the first 7 students who solve all 10 :O (yeah...) problems of PS0 — Easy C++/coding challenges, albeit that one is 'totally optional' and 'not graded'
  3. Kiasu lv 2 (#): Given to the first 7 students who solve all problems of PS1, the first graded PS
  4. My Life is in Order (#): Given to the first 7 students who solve all subtasks of PS2
  5. List Master (#): Given to the first 7 students who solve all subtasks of PS3
  6. Scheduling Master (#): Given to the first 7 students who solve all subtasks of PS4
  7. Chow-Yuan-Bin Award lv 1 (#): Given to the top 7 students who scored the highest in the first half VA OQ (likely 15/15) and if ties, by fastest submission time as acknowledged by VisuAlgo Online Quiz system
  8. Potential TA: Given to 7 students who score ≥ 88 points in the Midterm Quiz: You survived all those intellectual challenges...
  9. Heavy DS Master (#): Given to the first 7 students who solve all subtasks of PS5
  10. Graph Master (#): Given to the first 7 students who solve all subtasks of PS6
  11. Competitive Programmer to be (#): Given to to the first 7 (tie breaker with time) students who scored ≥ 144/200 points in Practical Exam (CS2040/C/S first 2/3) under that very stressful environment
  12. Sky Full Of Stars (#): Given to the first 7 students (closed by 22 Oct 2022) who get 10*3 = 30 stars (or slightly more) in your VisuAlgo account (read all e-Slides of CS2040/C/S topics; clear all medium level trainings, and also clear all hard level trainings) just before VisuAlgo Online Quiz 2
  13. Chow-Yuan-Bin Award lv 2 (#): Given to the top 7 students who scored the highest in the second half VA OQ (likely 20/20) and if ties, by fastest submission time as acknowledged by VisuAlgo Online Quiz system
  14. Nowhere to Hide (Reason): Given to students who already remembered by Steven (closed by last lecture). With more onsite components, this achievement will start to be meaningful again
  15. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 300.0 or more Kattis points at open.kattis during the execution of CS2040/C/S in S2 AY 2021/22 (closed by last lecture) (submitting all my AC/near-AC demo code will only give you about ~100.0 free Kattis points... so you must have done a lot more extra homework than necessary; PS: This is my account and this CS2040/C/S-specific page of Methods to Solve can help you get this achievement)
No Student Name Achievements