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 ~90 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 should be 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.

Known information as of Friday, 02 August 2019 (71 students), updated on Tuesday, 13 August 2019 (76 students), updated again on Tuesday, 20 August 2019 (91 students officially enrolled according to Luminus class roster):

  1. 29→36→39 Engineering students (most likely minor/2nd major in computing students),
  2. 13→8→16 Exchange students (all Exchange students are channeled to CS2040C, not CS2040/CS2040S),
  3. 16→15→15 InfoSec students,
  4. 3→4→10 others (8 Sci, 1 Art, 1 SDE),
  5. 5→7→7 CEG students,
  6. 5→4→4 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=??/~80?)
    ??+%
    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 20 Aug 2019, setup for 91 students:
    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/16) 09 Matthew
    4/Thu, 1000-1100 COM1-0120 (11/16) 03 StevenW
    4/Thu, 1100-1200 COM1-0120 (14/16) 04 StevenW
    4/Thu, 1400-1500 COM1-0120 (13/16) 07 KWei Heng
    4/Thu, 1500-1600 COM1-0120 (12/16) 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-0120 (14/16) 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 20 Aug 2019, setup for 91 students:
    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 (12/19) 01 Kane
    1200-1300 COM1-0120 (16/19) 05 Shantanu
    1300-1400 COM1-0120 (16/19) 06 Shantanu
    1400-1500 COM1-0120 (16/19) 07 Aaryam
    1500-1600 COM1-0120 (16/19) 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 X (TBC) 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 about ~90 students, should be 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. 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

The S1 AY19/20 timetable below is still tentative, especially those that are highlighted with pink color.

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 (NEW for S1 AY19/20; 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 (NEW for S1 AY19/20: 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)
SLLDemo.cpp
Kattis problems discussed:
joinstrings (NEW for S1 AY19/20)
T01: Introduction,
OOP (basic),
Live problem solving,
Analysis,
tut01.pdf (Link TBA)
L01: Quick Intro,
Review demo code so far, focusing on
OOP review (List ADT/ListVector)
C++ STL (algorithm, vector, string),
PS1 Discussion (algorithmic)
PS1, continued
04,
02-06 Sep
04a. Stack/Queue/Deque ADT (DLL) (until end)
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, use two deques; NEW: C++ list/deque)

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 Introduction,
List ADT (array/vector),
PS1 Discussion
tut02.pdf (Link TBA)
L02: Quick Re-introduction,
VA OQ demo (sorting),
Hands-on: ???
(something sorting)
PS1
Due: Sat, 07 Sep 19, 07.59am
(3%)

PS2: List-related Problems
Out: Sat, 07 Sep 19, 08.00am
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)
froshweek (for another wow moment)

05b. Mock Practical Exam 1 - C++/Arrays/Vectors/Sorting
Kattis problems discussed:
TBA
T03: List ADT,
Linked List Review,
Stack/Queue/Deque ADT,
Applications,
PS2 Discussion
tut03.pdf (Link TBA)
L03: PS1 Quick Debrief,
C++ STL (list/stack/queue/deque),
,
VA OQ demo (list)
PS2 Discussion (algorithmic)
Hands-on: ???
(something LL)
PS2, continued
06,
16-20 Sep
06a. Practical Exam 1 (7%)
During our Wed lecture time (10.05am-11.35am, 90m)
Material: Up to Week 03 L03a + Week 04 D02+T02,
i.e. Basic C++ and Sorting only
Venue: Our lecture venue (I3-AUD)
Open book, bring your own laptop :O

06b. Midterm Quiz (8%)
During our Thu lecture time (17.05pm-17.35pm, 30m)
Material: Up to Week 04 L04a + Week 05 D03+T03,
i.e. Basic C++, Sorting, and Linked List
Venue: Our lecture venue (I3-AUD)
Open book (no restriction), theory only :O
Format: T/F, MCQ, and/or Short Answers

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,
T04: Midterm Test
Preparation or Solutions
(depends on timing),
Basic PQ ADT
tut04.pdf (Link TBA)

L04: PE1 Upsolve 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 (again :O) this week :)
But if possible, read Hash Table and BST e-Lecture slides by yourself first...
PS: Those who miss midterm test due to VALID reasons (representing NUS for an official event; valid Medical Certificate; bereavement of immediate family member) can take make-up PE1 and/or midterm quiz to be scheduled during recess week
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),
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 (Link TBA)
L05: PS2 Debrief (short),
PS3 Discussion (short),
VA OQ demo (heap,hashtable),
C++ STL (priority_queue),
Max-Min conversion,
Hands-on: ???
(something 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 (bst,avl)
Hands-on: ???
(something 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 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: ???
(something graph DS)
PS4, continued
10,
21-25 Oct
10a. Live Solve - PQs/Tables/Trees (Heap/bBST)/Graphs
List of selected problems:
abinitio (NEW for S1 AY19/20; graph data structures manipulation)
builddeps (toposort demo),
brexit (happening or not?),
conformity (mock PE S2 17/18),
detour (?),

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:
reachableroads (BFS this time, count #CC),
countingstars (floodfill, DFS, count #CC),
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 to compete in ICPC Asia Jakarta 2019, Fri 25 Oct - Mon, 28 Oct 2019
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
Lecture plan this week TBC

Practical Exam 2 (12%)
Timing: ???, ?? Oct 2019, TBA
Venue: Likely PL2+PL4, especially if total students ≤ 71
COM1-B-PL2 (capacity 46)
COM1-B-PL4 (capacity 25)
TBC: COM1-B-PL1 (capacity 44)
T09: DFS/BFS advanced stuffs,
Cycle, Toposort++, (Floodfill/CC),
Modeling exercise 2 (time permitting),
tut09.pdf
L09: PS4 Debrief (short),
PS5 Discussion (short),
PE2 upsolve
PS5, continued
12,
04-08 Nov
12a. 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)

12b. 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)

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

(Participation Marks Given, 3%)
L10: VA OQ demo (sssp)
Tips for OQ preparation
(students need to self practice on sssp module),
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. SSSP continued: Modified Dijkstra's, On Tree, On DAG,
Final Exam Tips, Last Lecture
Kattis problems discussed:
shortestpath1 (modified Dijkstra's implementation)
flowerytrails (Dijkstra's (any version) and DFS/BFS to traverse the shortest path(s))
Closed with a few minutes of semester summary,
followed with review of what can be done better for future iterations...

Lecture 13b will be a buffer slot...
D11: VA Online Quiz (12%)
(URL: https://visualgo.net/training, click 'CS2040C Quiz')
Time: 30m, 19+1 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 19/19
But to prevent abuse, we will only take the latest score :O
PS: Steven add a bunch of new Q20 that cannot be prepared by anyone
T11: Final paper preparation,
Class Photo,
tut11.pdf
No more PS
Study Week, 18-22 Nov 2019
Makeup/remedial Practical Exam, if any, will be during reading week for some students only
Venue: 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,


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

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
  5. Your Coding Skill is Good (#): Given to (up to) first 14 students who can solve all PE1 problems (easy) under that stressful environment
  6. Potential TA: Given to everyone who score ≥ 90.0 points (cutoff TBC) 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. Mapping Master (#): Given to the first 14 students who solve all subtasks of PS4
  9. 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
  10. Graph Master (#): Given to the first 14 students who solve all subtasks of PS5
  11. 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
  12. 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
  13. 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