CS2040C - Data Structures and Algorithms (C++)

Introduction

This module introduces students to the design and implementation of fundamental data structures and algorithms. The module 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 module is C++.

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 Dr Chong Ket Fah nor CS2040S — contact Dr Soh Soon Hong, Harold) in S1 AY19/20 (Aug-Nov 2019). Steven already had enough experiences teaching CS2040/C module in previous 2 AYs (4x :O; 3 very successful, 1 "average"). There will only be a few local changes for Aug-Nov 2019 edition.

The max number of students for S1 AY19/20 (Aug-Nov 2019) is set at most 200 @ ModReg, but we are realistically looking at just ~100 students. This number is (much) higher than "only" 37 students in S1 AY 17/18 (2 AYs ago) and also a bit higher than 73 students in S1 AY18/19 (1 AY ago, taught by Assoc Prof Gary Tan). The students are minor/second major students, some freshmen from CEG and InfoSec AY19/20 students who are exempted from CS1010 (and a few from AY18/19 :O), a few exchange students, and a few Poly Preparatory Programme students.

Some other facts:

  1. Steven uses flipped classroom, machine-teach-(and-auto-test)-students, and in-class live discussion of (hard)er problems in his CS2040/C classes four times in last 2 AYs (AY17/18 + AY18/19). His teaching feedback ratings for those four offerings vary in [4.2 (just slightly above average)..4.8 (very good)] bracket out of maximum 5.0.
  2. On top of teaching CS2040/C four times so far (2017-2019), 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 module.
    Rating
    (out of 5.0)
    (SoC avg ~4.1)
    Aug-Dec 19
    (n=??/98)
    ??+%
    Jan-May 19
    (n=144/269)
    54%
    Jun-Aug 18
    (n=33/38)
    87%
    Jan-May 18
    (n=145/173)
    84%
    Aug-Dec 17
    (n=28/37)
    76%
    Module feedback Target return to 4.2? 4.0 (v large class) 4.4 (S1 level) 4.3 (large class) 4.4 (> avg :)
    Module difficulty Target stay at 4.0? 4.0 (easiest) 4.2 (Sp Sem) 4.0 (easiest) 4.1 (> avg :O)
    Steven's teaching Target return to 4.4? 4.2 (v large class) 4.8 (Thx God :) 4.5 (large class) 4.7 (> avg :)

    Latest info as of 18 Sep 2019, finally all 98 students have official tutorial group:
    Tutorial Teaching Assistants (6 tutorial sessions + 4 additional consultation (2-hours) sessions, sorted chronologically):
    Most tutorial sessions are between Wed lecture and before Thu lectures.
    One Friday tutorial session is after both Wed+Thu lectures (so will know some answers already, your choice).

    Date, Time COM1 Room (#Stu/#Cap) No Tutor
    2/Tue, 1400-1600
    (consultation slot)
    COM1-02-15
    (NUS ICPC Lab)
    - StevenW
    3/Wed, 1400-1600
    (consultation slot, after Wed lecture)
    COM1-02-Lobby Area
    (find Matthew near Steven's LEGO-ified poster)
    - Matthew
    3/Wed, 1600-1700 COM1-0120 (14/17) 09 Matthew
    4/Thu, 1000-1100 COM1-0120 (19/19) 03 StevenW
    4/Thu, 1100-1200 COM1-0120 (17/17) 04 StevenW
    4/Thu, 1400-1500 COM1-0120 (17/17) 07 KWei Heng
    4/Thu, 1500-1600 COM1-0120 (14/17) 08 KWei Heng
    4/Thu, 1615-1700 + 1745-1830
    (consultation slot)
    i3-Aud
    (Bef/Aft Thu Lecture)
    - Dr StevenH
    5/Fri, 1000-1200
    (consultation slot)
    COM1-02-Lobby Area
    (find KWei Heng near Steven's LEGO-ified poster)
    - KWei Heng
    5/Fri, 1200-1300 COM1-0208 (17/17) 01 Matthew
    1. Matthew Ng Zhen Rui (2 tutorial groups, CS2040C S2 AY 2018/19 teaching feedback rating of 4.8, A+ in CS2040C S2 AY2017/18, A- in CS3233 S2 AY 2018/19)
    2. Kuan Wei Heng (2 tutorial groups, A- in CS3233 S2 AY 2018/19)
    3. Steven Wijaya (2 tutorial groups, A in CS3233 S2 AY2018/19, Silver medalist in IOI 2018)

    Latest info as of 24 Sep 2019, finally all 98 students have official lab group:
    Laboratory Teaching Assistants (5 laboratory sessions, sorted chronologically):
    All Lab sessions are on Friday.
    We will do lots of hands-on (i.e. real coding of various data structures and algorithms) during these lab sessions.

    Date, Time COM1 Room (#Stu/#Cap) No Lab TA
    0800-0900 COM1-0120 (18/20) 01 Kane
    1200-1300 COM1-0120 (20/20) 05 Shantanu
    1300-1400 COM1-0120 (22/22) 06 Shantanu
    1400-1500 COM1-0120 (18/20) 07 Aaryam
    1500-1600 COM1-0120 (20/20) 08 Aaryam
    1. Srivastava Aaryam (2 lab groups, CS2040C S2 AY 2018/19 teaching feedback rating of 4.4, A in CS2040C S2 AY2017/18)
    2. Modak Shantanu Bharat (2 lab groups, A+ (raw rank 1) in CS2040C S2 AY2018/19)
    3. Quah You Jing Kane (1 lab group, A in CS2040C S2 AY2018/19, has discord channel about CS2040C)
    4. Joshua Casey Darian (assistant grader for Practical Exam 1, Midterm Quiz, Practical Exam 2, not running a Lab Group)
  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 if you have taken similar/older module(s) that have huge degree of overlap with this new module.

Syllabus

This is what you will learn if you take CS2040/C taught by Steven:

Course Registration Additional FAQ

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

Q: Will there be a practical exam/coding test for CS2040/C?
A: Yes, twice, on Week 6 (basic C++/sorting questions only) and on Week 11 (everything minus graph).
Q: PE sounds scary... and you make it 2x somehow... Will there be make up PE for CS2040/C if I got sick/underperform...?
A: Yes, also twice. Steven is aware that many students are still at learning stage. Those who are absent from the official ones for valid reason (MC, Bereavement of immediate family member, representing NUS for official event) and a few bottom 44 (2 spares, according to physical limit of COM1-B-PL2) students will be invited for the make up PE1 during recess week and/or make up PE2 during study week.
Q: Will this module be graded using Bell curve?
A: For S1 AY19/20 version with 98 students, obviously yes...
Q: I am from CS1101S/CS1010S/other modules that do not use C++, should I pick up C++ on my own during this July 2019?
A: Yes, that is a very good idea. We will only review basic C++ in the first few weeks of this module and then Steven will encourage you to self-learn C++ along the way. PS: Transition from C from CS1010 to C++ in CS2040C should be easier as most C++ compilers can compile C program too.
Q: What Integrated Development Environment (IDE) that we will use in CS2040/C?
A: The choice of IDE is "up to you but" we recommend Dev-C++. We will have Practical Exam (PE) on Week 6 and 11.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my Competitive Programming book, the 3.19a edition (actually for CS3233) 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 ~3 200+ problems in that book (CP3.19a) and the next full edition (CP4) with more challenging problems is in the pipeline... :D.
Q: Can I S/U this module if I am a freshman when I take this module?
A: No, as this is a level-2 core module. 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 module during your freshmen year.
Q: I heard from my friend/senior that this CS2040/C is a flipped classroom module?
A: You heard that correctly. Steven is working hard at the background to continuously improve his 24/7 electronic clone, VisuAlgo, to be able to explain basic data structures and algorithms covered in CS2040/C as clear? (that's debate-able) as possible to first timer. 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 are projected to grow bigger in future AYs when the CS1020+CS2010 route is fully closed).
Q: What are the potential changes that you will apply to CS2040/C in S1 AY19/20 compared to your four runs in S1+S2+S4 AY17/18 ('ok') and in S2 AY18/19 ('average')?
A: These are the potential changes:
  1. NUS @ Kattis integration remains (or actually much stronger); NUS will be a paying customer starting this semester.
  2. We will have TWO Practical Exams instead of 1: On Week 6 (7%) and on Week 11 (12%), both auto graded by machine and with at most 1 make-up PE each (no make-up of make-up).
  3. We will have very short Midterm Quiz/written test (theory only, 8%),
  4. Yet another iterative enhancement to various VA e-Lecture slides, Steven may even want to 'make this a printed book' combining these VA e-Lecture slides with the relevant parts of CP3.19a book,
  5. Integrate many new VA OQ questions from various past CS1020/2010/2020/2040/C papers that can be digitised; make the new questions only appear during 'test mode'
  6. To minimize boredom of re-solving the same set of Kattis exercise problems, Steven intends to change some (not all) example problems compared to what he solved live in previous four semesters :O.
  7. Confirmed: Steven uses webcast this time... I relent...
  8. NEW: Steven try to use anonymous forum (discord) this time...
  9. All others are planned to be kept roughly constant as in S2 AY18/19 version

Note: This course registration section will not be prominent from Week 1 of S1 AY19/20 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.

News

Date News

Lesson Plan

Week Lecture,
2+1h/session
Every Wed 10am-12pm and
Every Thu 5-6pm
I3-AUD, from Wk01
Tutorial,
1h/session
Wed/Thu/Fri
6 slots
From Wk03
Lab,
1h/session
Every Fri
5 slots
From Wk03
Interesting Problem Set
@ Home
Every ~Two Weeks
~6++ hours/set
From Wk02
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
-03/-02/-01,
Bef Mon,
12 Aug
Not started, but please revise your CS1010
(Steven assumes that all? of you have taken
or exempted from this module/its variants)

Register at Kattis,
read C++ specific instructions @ Kattis,
and solve these optional OJ problems
by yourself (CS1010 level):
Optional Week -01 (29 Jul-02 Aug) very easy C++/coding challenges:
Week -01 (10 'easiest' problems in Kattis system)
Optional Week 00 (05-09 Aug) easy C++/coding challenges:
Week 00 (another 9 'easy' problems in Kattis system)
Not Started Not Started Not Started
01,
12-16 Aug
Hari Raya Haji is on Sun, 11 Aug 2019
The following Mon, 12 Aug 2019 is a Public Holiday
No CS2040C class is affected.

01a. Course Admin, (Re-)Introduction to C++
Setting the tone for a flipped classroom module
VisuAlgo + this Private IVLE + Kattis (NUS) + Kattis (open)
Basic C/C++ review/new feature introduction
Kattis problems discussed:
statistics (revise I/O, control flow: repetition, implicit selection)

01b. (Re-)Introduction to C++ (continued)
Kattis problems discussed:
quickbrownfox (1D Boolean array; duplicates possible;
NEW: C++ STL vector, C++ class (overkill actually)),

Reminder: Read old CS1020/E lecture note on algorithm analysis
before Lecture 02a
Not Started Not Started Trial PS0
not graded
Out: Wed, 14 Aug 19, 18.00pm
Showcased during second lecture
02,
19-23 Aug
02a. Analysis of Algorithms
(old CS1020/E lecture note on this topic will be digitised later)
(Kattis) problems discussed:
autori (NEW: C++ string, C++ istringstream),
filip (review: function),
Live speedtest.cpp demo
lineup (NEW: C++ STL sort, reverse),

Reminder: Read sorting e-Lecture slides before Lecture 02b
At least until slide 8-3, preferably more

02b. Sorting (until slide 8-3)
C++ STL algorithm: sort, stable_sort
Kattis problems discussed:
height (insertion sort simulation),
sortofsorting (NEW: custom comparator, C++ STL stable_sort)

Reminder: Read ALL sorting e-Lecture slides before Lecture 03a
Not Started Not Started Trial PS0
"due": Sat, 24 Aug 19, 07.59am
not graded

PS1: Sorting-related Problems
Out: Sat, 24 Aug 19, 08.00am
03,
26-30 Aug
03a. Sorting (until end)
Focus on the harder content of sorting e-Lecture
SortingDemo.cpp
Sorting Online Quiz (medium)

03b. List ADT: (Single) LL (until slide 3-22)
Introduction of List ADT and SLL operations
C++ STLs: forward_list (an SLL), list (a DLL)
Kattis problem discussed:
joinstrings (NEW: list concatenation via std::list (splice); or others)
T01: Introduction,
OOP (basic),
Analysis,
PS1 Discussion (up to 60 points),
tut01.pdf
L01: Quick Intro,
Review demo code so far, focusing on
OOP review (List ADT/ListVector)
C++ STL (algorithm, vector, string),
A sorting challenge,
PS1 Discussion (algorithmic)
PS1, continued
04,
02-06 Sep
04a. Stack/Queue/Deque ADT (DLL) (until end)
SLLDemo.cpp
Then focus on Stack, Queue, DLL, Deque
Plus a few other LL technicalities
C++ STLs: stack, queue, deque (actually not a DLL)
Linked List Online Quiz (medium)
Kattis problems discussed:
thegrandadventure (NEW for S1 AY19/20; NEW: C++ stack and its usage)
teque (NEW for S1 19/20, non 100 points subtasks, optional in PS2 later)

04b. Priority Queue (PQ) ADT: Binary Heap (until slide 6)
Review of basic ideas of PQ ADT and basic Binary Heap structure
C++ STL: priority_queue, partial_sort,
See priority_queue.cpp at GitHub repo of CPbook website
T02: Sorting Application(s),
Sorting, mini experiment,
ADT re-introduction,
List ADT (array vs vector),
PS1 Discussion (up to 100 points),
tut02.pdf
L02: Quick Re-introduction,
VA OQ demo (sorting,list),
PS1 last minute discussion,
Hands-on: gearchanging
(about sorting fractions)
PS1
Due: Sat, 07 Sep 19, 07.59am
(3%)

PS2: List-related Problems
Out: Sat, 07 Sep 19, 08.00am
B: teque is optional and not graded.
05,
09-13 Sep
05a. Priority Queue (PQ) (until end)
BinaryHeapDemo.cpp
Binary Heap Online Quiz (medium)
Kattis problems discussed:
numbertree (for a short wow moment)

05b. Mock Practical Exam 1
Material: C++/Arrays/Vectors/Sorting
(but 45 minutes only)
Kattis problems discussed:
pivot (O(n^2) TLE; O(n log n) difficult; O(n) easy)
froshweek (O(n^2) TLE again; O(n log n) possible)
T03: List ADT,
Linked List Review,
Stack/Queue/Deque ADT,
One application,
PS2 Discussion (up to 60 points),
tut03.pdf
L03: PS1 Quick Debrief,
C++ STL (list/stack/queue/deque),
VA OQ demo (heap),
PS2 Discussion (algorithmic)
Hands-on: throwns
(about LL/variant)
PS2, continued
06,
16-20 Sep
06a. Practical Exam 1 (7%)
During our Wed, 18 Sep 2019 lecture time (10.05am-11.35am, 90m)
Material: Up to Week 03 L03a + Week 04 T02+L02
i.e. Basic C++, Time Complexity, and Sorting only
Venue: Our lecture venue (I3-AUD), attendance is compulsory
Open book, bring your own laptop :O
Configure your laptop to compile C++ (-std=gnu++17) code offline
If you don't have laptop :O, or your laptop is broken...;
borrow someone else's or take (harder) re-PE1 @ PL2 on 25 Sep
Do NOT use online IDE (or share your work online using any means)
As plagiarism checkings are done at server side
Tips: The first few who manage to get (close to) 200/200
should apply "every man (woman) for himself (herself)" strategy
by keeping your work private until 11.35am
as we will definitely pairwise compare subsequent ACs with yours

06b. Midterm Quiz (8%)
During our Thu, 19 Sep 2019 lecture time (17.02pm-17.42pm, 40m)
Material: Up to Week 04 L04a + Week 05 T03+L03,
i.e. Basic C++ (comprehension), Time Complexity, Sorting, and Linked List
Venue: Our lecture venue (I3-AUD)
Open book (no restriction), theory only :O
but NO electronic device (insane level questions if I allow Open Internet)
No C++ coding question (but C++ code can be given in the question)
Format: MCQ, Fill in the Blanks, and Short Answers
The last question is a "feedback" question that you can pre-compute
Steven is especially interested to gather feedback about Open Internet PE1

Past Papers (different format):
CS2040C-2017-18-S1-midterm-medium.pdf,
CS2040C-2017-18-S2-midterm-medium.pdf,
CS2040-2017-18-S4-midterm-hard.pdf,
CS2040C-2018-19-S1-midterm-medium.pdf (Prof Gary),
CS2040C-2018-19-S2-midterm-medium.pdf,
CS2040C-2019-20-S1-midterm-medium.pdf (our paper).
T04: Midterm Quiz
Preparation or Solutions
(depends on timing),
Basic PQ ADT
tut04.pdf

L04: PE1 Upsolve
Lab TA will show
a detailed walkthrough
of nus.basicprogramming1
(CS1010 mass review) and
at least 79 points of
of nus.magicsequence
(on how to be faster than std::sort)
PS2
Due: Sat, 21 Sep 19, 07.59am
(3%)

PS3: PQ/Table-related Problems
Out: Sat, 21 Sep 19, 08.00am
Recess Week, 21-29 Sep 2019
We can take a break this week :)
Unless..., if you happen to also organize/participate in this event
But if possible, read Hash Table and BST e-Lecture slides by yourself first...

PS: Those who miss PE1 and/or Midterm Quiz due to VALID reasons (valid Medical Certificate; representing NUS for an official event; bereavement of immediate family member)
and those who want to retake (especially bottom 44 students) can take make-up/remedial PE1+midterm quiz:
Make up/Remedial Practical Exam 1, Wed, 25 Sep 2019 (10.00am-12.00pm, 120m, venue: COM1-B-PL2; capacity: 46; (replacement 8+7 = 15%; I take the best of the two))
Material: Now up to Week 06 stuffs, i.e. Priority Queue is now included (review PE1+Midterm Quiz on Week 06 too), and clearly harder than the original PE1+Midterm Quiz combo...
Note that there is no more make up of make up :O...
07,
30 Sep-04 Oct
07a. Table ADT part 1: Hash Table
C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap
Kattis problems discussed:
competitivearcadebasketball (NEW for S1 AY19/20; at open.kattis only for now),
whatdoesthefoxsay (assume there are 10 000 animals; string hashing)

07b. More Hashing
See unordered_map_unordered_set.cpp at GitHub repo of CPbook website,
HashTableDemo.cpp
Hash Table Online Quiz (medium)
No Kattis live problem solving as this lecture is a bit technical
T05: More Binary Heap,
More ADT PQ Operations,
Midtest Review
tut05.pdf
L05: PS2 Debrief (short),
C++ STL (priority_queue),
Max-Min conversion,
PS3 Discussion (short),
Hands-on: canvas
(greedy simulation with PQ)
PS3, continued
08,
07-11 Oct
08a. Table ADT part 2: Binary Search Tree (until slide 11)
C++ STLs: set, map, multiset, multimap,
BST Online Quiz (medium),
Kattis problem discussed:
kattissquest (NEW for S1 AY19/20)

08b. Adelson-Velskii Landis (AVL) Tree
AVL Tree Online Quiz (medium),
See map_set.cpp at GitHub repo of CPbook website,
BSTDemo.cpp,
AVLDemo.cpp,
No Kattis live problem solving as this lecture is a bit technical
T06: Table ADT 1 - unordered,
Hashing concepts,
Hash Table issues,
tut06.pdf
L06: C++ STL (unordered_map) (short),
C++ STL (unordered_set) (optional),
C++ STL (map) (short),
C++ STL (multimap, set, multiset) (optional),
VA OQ demo (hashtable,bst,avl),
Hands-on: baconeggsandspam
(simple Table ADT)
PS3
Due: Sat, 12 Oct 19, 07.59am
(3%)

PS4: Table-related Problems
Out: Sat, 12 Oct 19, 08.00am
09,
14-18 Oct
09a. Graph DS + Applications
Graph DS Online Quiz (medium),
No built-in C++ STL container,
See graph_ds.cpp at GitHub repo of CPbook website,
Kattis problem discussed:
flyingsafely (for a 30s jaw-dropping moment)

09b. Graph Traversal + Simple Applications (until slide 5-8)
DFS/BFS Online Quiz (easy),
No built-in C++ STL algorithm,
See dfs_cc.cpp, UVa00469.cpp, and bfs.cpp at GitHub repo of CPbook website,
Kattis problem discussed:
reachableroads (DFS/BFS introduction, count #CC)
T07: Table ADT 2 - ordered,
BST/AVL advanced stuffs: Select and Rank,
PQ ADT alternative implementation,
Comparison with Table ADT 1,
unordered vs ordered,
tut07.pdf
L07: PS3 Debrief (short),
PS4 Discussion (short),
VA OQ demo (graphds)
Hands-on: traveltheskies
('challenging' graph DS)
PS4, continued
10,
21-25 Oct
10a. Mock Practical Exam 2
Material: Everything so far, from Week 01 until Graph Traversal
Kattis problems discussed (TBA):
A (?),
B (?),
C (?).

10b. Graph Traversal continued (until slide 7-11)
(we skip slide 8-12, out of CS2040/C scope)
DFS/BFS Online Quiz (medium)
Kattis problems discussed:
runningmom (AL of strings; DFS; back edge detection)
T08: Graph DS Review,
Graph DS Conversion Exercise,
Some Graph Properties Discussion,
Graph Modeling exercise 1,
DFS/BFS Review
tut08.pdf
L08: VA OQ demo (dfsbfs)
Hands-on: ???
(something graph traversal)
PS4
Due: Sat, 26 Oct 19, 07.59am
(3%)

PS5: Graph-related Problems
Out: Sat, 26 Oct 19, 08.00am
ICPC Asia Jakarta 2019
Steven will bring a few NUS students (none from this class) to compete in ICPC Asia Jakarta 2019, Fri 25 Oct (AM) - Tue, 29 Oct 2019 (PM)
No CS2040C class is affected.

Diwali is on Sun, 27 Oct 2019
The following Mon, 28 Oct 2019 is a Public Holiday
No CS2040C class is affected.
11,
28 Oct-01 Nov
11a. This 2h lecture is cancelled
so that students can prepare for PE2 tonight

Practical Exam 2 (12%)
Timing: Wed, 30 Oct 2019, 6.30-8.30pm
Venues with total capacity ≥ 96:
COM1-B-PL2 (capacity 46; for 42 who attended re-PE1)
COM1-B-PL4 (capacity 25; for 21 who scored ≤ 123 in PE1 but no re-PE1)
COM1-B-PL1 (capacity 44; for the other 33 students)
Open Internet but full invigilation setup

11b. Single-Source Shortest Paths (SSSP) Problem: Bellman Ford's, BFS
No built-in C++ STL algorithm,
See bellman_ford.cpp at GitHub repo of CPbook website,
Kattis problem discussed:
shortestpath1 (that Bellman Ford's will TLE)
knightjump (NEW for S1 AY19/20; BFS demo; implicit graph demo)
T09: DFS/BFS advanced stuffs,
Cycle, Toposort++, (Floodfill/CC),
Modeling exercise 2 (time permitting),
(or PE2 preperation for TG09),
tut09.pdf
L09: PS4 Debrief (short),
PS5 Discussion (short),
PE2 upsolve
PS5, continued
12,
04-08 Nov
12a. SSSP continued: Dijkstra's (original version+implementation)
Kattis problem discussed:
shortestpath1 (that Dijkstra's implementation is easy)
No built-in C++ STL algorithm,
See dijkstra.cpp at GitHub repo of CPbook website,
SSSP Online Quiz (medium)

12b. SSSP continued: Modified Dijkstra's, On Tree, On DAG
Kattis problems discussed:
shortestpath1 (modified Dijkstra's implementation)
flowerytrails (Dijkstra's (any version) and DFS/BFS to traverse the shortest path(s))
detour (SDSP),

NUS Online Teaching Feedback System opens this Friday
T10: Bellman Ford's, BFS, and
Original Dijkstra's Review,
Modeling exercises 3,
tut10.pdf

(Participation Marks Given, 3%)
L10: VA OQ demo (sssp)
Tips for OQ preparation
Class Photo (for momento),
Hands-on: ???,
(something SSSP)
PS5 last minute discussion (offline)

(Participation Marks Given, 3%)
PS5
Due: Sat, 09 Nov 19, 07.59am
(3%)
13,
11-15 Nov
13a. This 2h lecture will be just 1h because Steven
has important CS4234 mini project evaluation at 12-2pm

13a. Optional Lecture: MST
Prim's algorithm only (Priority Queue++)

13b. Last Lecture
Semester summary,
Review of what can be done better for future iterations,
Advertisement of future (algorithm) modules,
Ending: a few Final Assessment Tips.
T11: Final paper preparation,
Class Photo,
tut11.pdf
D11: VA Online Quiz (12%)
(URL: https://visualgo.net/training, click 'CS2040C Quiz')
Time: 25+5m, 18+2 random hard (may luck be with you) questions
All topics in CS2040C
Student can do one more random round if the first one is not 18/18
But to prevent abuse, we will only take the latest score :O
PS: Steven add a few new Q19+Q20 that cannot be prepared by anyone
No more PS
Study Week, 18-22 Nov 2019
Make up/Remedial Practical Exam 2, Wed, 20 Nov 2019 (10.00am-12.00pm, 120m)
Venue: TBA
Eligibility TBA

Final Assessment Consultations (per request)

Final Assessment Past Papers:
CS2040C-2017-18-S1-final.pdf,
CS2040C-2017-18-S2-final.pdf,
CS2040-2017-18-S4-final.pdf,
CS2040C-2018-19-S1-final.pdf (Prof Gary),
CS2040C-2018-19-S2-final.pdf,
CS2040C-2019-20-S1-final.pdf (our paper, obviously link TBA),


NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Wed, 04 Dec 2019, 09-11AM
Venue: TBA
New this time: I may have T/F or MCQ questions this time, to reduce my grading load a bit (CS4234 exam on Tue, 03 Dec 2019)...

Partial Class Roster

Steven uses a small-scale gamification system in his version of CS2040/C 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 big (~90), 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 Friday, 02 August 2019); Any early feedback will always help Steven in refining the preparation of the fourth iteration of this module
  2. Kiasu (#): Given to the first 14 students who solve all problems of Trial PS0, albeit that one is 'totally optional' and 'not graded'
  3. My Life is in Order (#): Given to the first 14 students who solve all subtasks of PS1, the first graded PS of CS2040/C
  4. I am a List Master (#): Given to the first 14 students who solve all subtasks of PS2 including the optional problem B...
  5. Your Coding Skill is Good (#): Given to first 4 students who scored 179 (out of 200) for PE1 (CS2040/C first 1/4) under that stressful environment
  6. Potential TA: Given to everyone who score ≥ 87 points in the Midterm Quiz: You survived all those intellectual challenges...
  7. Scheduling Master (#): Given to the first 14 students who solve all subtasks of PS3
  8. Your Coding Skill is Also Good (#): Given to first 3 students who scored 200 (out of 200) for re-PE1 (CS2040/C first 1/3) under that stressful environment
  9. Mapping Master (#): Given to the first 14 students who solve all subtasks of PS4
  10. Competitive Programmer to be (#): Given to (up to) first 14 students who can solve all PE2 problems (CS2040/C first 2/3) under that stressful environment
  11. Graph Master (#): Given to the first 14 students who solve all subtasks of PS5
  12. Chow-Yuan-Bin Award (#): Given to the top students from each lab group who scored the highest (and if ties, by fastest submission time as acknowledged by Lab TA) in CS2040/C final Online Quiz using machine: VisuAlgo (before the actual Final Assessment set by a human); Note: students who need second attempt will not get this achievement
  13. Nowhere to Hide (Reason): Given to students who already remembered by Steven (closed one day before final assessment); These students can choose to hide their matric cards during CS2040/C official assessments and Steven will allow them to do so
  14. 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 in S1 AY19/20 (closed one day before final assessment) (submitting all my AC/near-AC demo code will only give you about ~150.0 free Kattis points... so you must have done a lot more extra homework than necessary; PS: This is my account)
No Student Name Achievements