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 A/P Tan Sun Teck or Dr Chong Ket Fah for this) in S2 AY18/19 (Jan-May 2019). Steven already had enough experiences teaching CS2040/C module in previous AY17/18 (3x :O) and should be able to re-execute the rather successful flipped-classroom classes with similar (90%) setup with only a few local changes.

The max number of students for S2 AY18/19 (Jan-Apr 2019) is currently set at 300 (sorry, the correct max limit is 280) students. This number is (much) higher than 173 students in S2 AY17/18. This number as of 28 Feb 2019 is 269 students. The students should be almost everyone from CEG and InfoSec AY18/19 students (minus those who have somehow taken CS2040/C in earlier semester or deferring to take CS2040/C due to *some reasons :O*). There are some minor/second major and a few exchange students too.

Note: The old CS1020 has been dismounted by S2 AY18/19 and the last offering of CS2010 will be this S2 AY18/19.

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 three times in AY17/18. His teaching feedback ratings for those three offerings are in [4.5 .. 4.8] bracket out of maximum 5.0, i.e. 'not bad lah :)'.
  2. On top of teaching CS2040/C three times so far (2017-2018), 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)
    Jan-May 19
    (n=140+/269)
    52+%
    Jun-Aug 18
    (n=33/38)
    87%
    Jan-May 18
    (n=145/173)
    84%
    Aug-Dec 17
    (n=28/37)
    76%
    Module feedback 4.2? (v large class) 4.4 (S1 level) 4.3 (large class) 4.4 (> avg :)
    Module difficulty 4.0? (v large class) 4.2 (Sp Sem) 4.0 (better) 4.1 (> avg :O)
    Steven's teaching 4.4? (v large class) 4.8 (Thx God :) 4.5 (large class) 4.7 (> avg :)

    Tutorial Teaching Assistants (14 tutorial sessions + 2 hours consultation hours block, sorted chronologically):
    Tutorial and consultation sessions are scattered to every day of each week...
    PS: Some tutorial sessions are before and some others are after the Tuesday+Wednesday lecture slots.

    Date, Time COM1 Room (#Stu/#Cap) No Tutor
    1/Mon, 1000-1200
    (consultation slot)
    COM2-03-37
    (email first)
    - Steven
    1/Mon, 1400-1600
    (consultation slot)
    COM1-02-15/ICPC Lab
    (knock the door)
    - Lim Li
    2/Tue, 0900-1000
    (before Tue+Wed lectures)
    COM1-0114 (23/23) 08 Jin Zhe
    2/Tue, 1400-1500
    (before Wed lecture)
    COM1-0114 (26/26) 12 Ranald
    2/Tue, 1500-1600 COM1-B103 (24/24) 05 Ranald
    2/Tue, 1600-1700 COM1-0114 (23/23) 02 Ranald
    2/Tue, 1700-1900
    (consultation slot)
    COM1-02-Lobby Area
    (find Matthew)
    - Matthew
    3/Wed, 1200-1400
    (consultation slot)
    AS6-04-01/IOI Ops Room
    (knock the door)
    - Si Jie
    3/Wed, 1500-1600
    (after Wed lecture)
    COM1-0203 (20/20) 11 Lim Li
    3/Wed, 1600-1700 COM1-0203 (21/21) 09 Si Jie
    4/Thu, 1200-1400
    (consultation slot)
    AS6-04-27/Graduate Tutor office
    (knock the door)
    - Jin Zhe
    4/Thu, 1600-1700 COM1-0201 (19/20) 07 Si Jie
    4/Thu, 1700-1800 COM1-0217 (22/22) 10 Si Jie
    5/Fri, 0900-1000 COM1-0217 (25/25) 03 Jin Zhe
    5/Fri, 1100-1200 COM1-0201 (16/20) 04 Lim Li
    5/Fri, 1100-1200 COM1-0113 (10/20) 06 Jin Zhe
    5/Fri, 1100-1200 COM1-0217 (00/20,
    CLASS CANCELLED
    )
    14 -
    5/Fri, 1200-1400
    (consultation slot)
    AS6-04-01/IOI Ops Room
    (knock the door)
    - Ranald
    5/Fri, 1400-1500 COM1-0217 (18/20) 01 Matthew
    5/Fri, 1600-1700 COM1-0217 (23/23) 13 Matthew
    1. Dr Steven Halim (1 group, one of the three parallel Fri 11-12 classes (I move to Lab Group 14); consultation hour: Mon, 1000-1200, COM2-03-37)
    2. Jin Zhe (full time TA, 3 groups, consultation hour: Thu, 1200-1400, AS6-04-27/Graduate Tutor office, will also help Steven grade midterm, PE, and final)
    3. Ranald Lam Yun Shao (3 groups, very experienced CS2040/C TA, consultation hour: Fri, 1200-1400, AS6-04-01/IOI Ops Room)
    4. Lin Si Jie (3 groups, experienced CS2040/C TA, consultation hour: Wed, 1200-1400, AS6-04-01/IOI Ops Room)
    5. Lim Li (2 groups, SGP IOI coach 2018, consultation hour: Mon, 1200-1400, COM1-02-15/NUS ICPC Lab)
    6. Matthew Ng Zhen Rui (2 groups, A+ in CS2040C S2 AY2017/18, consultation hour: Tue, 1700-1900, COM1-02-Lobby Area)

    Laboratory Teaching Assistants (12 laboratory sessions, sorted chronologically):
    All Lab Demo sessions are on Monday, almost at every hour.
    Because of that, all Lab Demo sessions are before the Tuesday+Wednesday lecture slots.
    Many are on parallel time slots (peak at 1500-1600, with 4 parallel groups), so need different venues and different Lab TAs.

    Mon, Time COM1 Room (#Stu/#Cap) No Lab TA
    0800-0900 COM1-B110 (23/23) 03 Teh Nian Fei
    0800-0900 COM1-B111 (23/25) 04 Ler Wei Sheng
    0900-1000 COM1-B110 (23/23) 10 Teh Nian Fei
    1000-1100 No class at this hour Steven's consultation slot
    1100-1200 No class at this hour Steven's consultation slot
    1200-1300 COM1-B110 (23/23) 12 Srivastava Aaryam
    1200-1300 COM1-0120 (24/26) 13 Mohideen Imran Khan
    1300-1400 I3-0338 (24/24) 08 Ghozali Suhariyanto Hadi
    1300-1400 COM1-B110 (23/23) 11 Mohideen Imran Khan
    1300-1400 COM1-0120 (22/26) 14 Steven Halim
    1400-1500 No class at this hour Lim Li's consultation slot
    1500-1600 COM1-0120 (23/26) 01 Sidhant Bansal
    1500-1600 I3-0338 (10/24) 02 Ghozali Suhariyanto Hadi
    1500-1600 I3-0336 (00/24) 05 CLASS CANCELLED
    1500-1600 COM1-B111 (10/25) 09 Ammar Fathin Sabili
    1600-1700 COM1-B111 (24/25) 06 Ammar Fathin Sabili
    1700-1800 COM1-B110 (18/23) 07 Tan Jun An
    1. Ammar Fathin Sabili (NUS SoC PhD 1st year, 2 groups)
    2. Ghozali Suhariyanto Hadi (NUS SoC PhD 1st year, 2 groups)
    3. Sidhant Bansal (1 group, NUS ICPC member, CS2040C TA 2x, has 'special role')
    4. Tan Jun An (1 group, NUS ICPC member, CS2040C TA 2x, has 'special role')
    5. Teh Nian Fei (2 groups, A+ in CS2040C S2 AY2017/18)
    6. Mohideen Imran Khan S/O Z (2 groups, A+ in CS2040 S4 AY2017/18)
    7. Ler Wei Sheng (1 group, A in CS2040C S2 AY2017/18)
    8. Srivastava Aaryam (1 group, A in CS2040C S2 AY2017/18)
    9. Dr Steven Halim (1 group, emergency swap with Tutorial Group 04)
    10. Yohanes Yudhi Adikusuma (NUS SoC PhD 2nd year, grading only, e.g. midterm and PE)
  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, once only, on Tuesday of Week 10, nearing the end of the semester, after sufficient practices in Lab Demos and PSes.
Q: Will this module be graded using Bell curve?
A: For S2 AY18/19 version (~269 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 December 2018/early January 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 entirely up to you. But note that we will have Practical Exam (PE) on Week 10, so try to be familiar with the (C++) programming tools what we have in our various PLs. We have Dev-C++, Eclipse, Notepad++ and g++, etc.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my Competitive Programming book, the 3.18b 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 ~3000+ problems in that book (CP3.18b) 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. For AY18/19 freshmen who are going to take the S2 version, I believe that most of you will clear CS1010/its variants in S1 AY18/19, so this CS2040/C is not S/U-able if you choose to do CS2040/C as per normal timeline, i.e. in your Y1S2.
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). The first three experiments were conducted with 37+173+38 = 248 students in S1+S2+S4 of AY17/18 and all 'not bad lah :)'.
Q: What are the potential changes that you will apply to CS2040/C in S2 AY18/19 compared to your three runs in S1+S2+S4 AY17/18 (that I heard from my friend/senior)?
A: These are the potential changes:
  1. Yet another round of enhancement to various VA e-Lecture slides so that Steven receives even less 'basic' question than the already low number in S1+S2+S4, including adding a few more example code and self-check MCQs for earlier e-Lectures; Indonesian and Chinese translation for CS2040/C topics should be near complete by then; the print-friendly feature should be much more usable by then
  2. 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'
  3. 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 S1+S2+S4 :)
  4. Steven uses NUS @ Kattis very deeply this time
  5. All others are planned to be kept roughly constant as in AY17/18 version

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

News

Date News

Lesson Plan

Week Lab,
1h/session
Every Mon
Various Timing
From Wk02
Lecture,
2+1h/session
Every Tue 12-2pm and
Every Wed 8-9am
I3-AUD, from Wk01
Tutorial,
1h/session
Except Mon
Various Timing
From Wk02
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
-02/-01,
Bef Mon,
14 Jan
Not Started 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):
hello (revise simple O of I/O),
judgingmoose (revise simple I/O, simple if-else),
timeloop (revise simple I/O, simple for-loop),
mia (revise simple function, another if-else),
treasurehunt (revise (2D character) array, (recursive) function)

Optional Week -02 challenges, not discussed:
asciiaddition, bossbattle, glitchbot, hissingmicrophone, and numberfun.

Optional Week -01 challenges, not discussed:
Trial PS0 (another 10 'random' problem from Kattis)
Not Started Trial PS0
not graded
Out: Tue, 08 Jan 19, 08.00am
01,
14-18 Jan
Not Started 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:
marswindow (revise loop; modulo operation),
princesspeach (1D Boolean array; duplicates possible),

Reminder: Read old CS1020/E lecture note on algorithm analysis
before Lecture 02a

Steven is away
~Thu, 17 Jan-Sun, 20 Jan 2019 for a family event
No CS2040C class is affected
Not Started Trial PS0, continued
Live demo during intro lecture
02,
21-25 Jan
D01: Introduction,
(your Lab allocation only final by Week 03)
Review demo code so far
Live solve some other Trial PS0 problems

Started early
due to CNY week later
Mon evening of Week 04
is for CNY Reunion Dinner
02a. Analysis of Algorithms
(old CS1020/E lecture note on this topic will be digitised later)
Kattis problems discussed:
princesspeach (re-coded, NEW: C++ class (overkill actually), C++ STL vector),
autori (NEW: C++ string, C++ istringstream),
zamka (review: function),
Live speed test demo

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:
mjehuric (bubble sort simulation),
lineup (NEW: C++ STL sort, reverse),
sortofsorting (NEW: custom comparator, C++ STL stable_sort)

Reminder: Read ALL sorting e-Lecture slides before Lecture 03a
T01: Introduction,
OOP (basic),
Live problem solving,
Analysis,
tut01.pdf

Started early
due to CNY week later
Trial PS0
"due": Wed, 23 Jan 19, 07.59am
not graded

PS1: Sorting Problems
Out: Wed, 23 Jan 19, 08.00am
At https://nus.kattis.com
03,
28 Jan-
01 Feb
D02: Quick Re-introduction,
OOP review (List ADT/ListVector)
C++ STL (algorithm, vector),
Implement some of these,
A sorting challenge,
VA OQ demo (sorting),
PS1 Discussion (algorithmic)
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
T02: Sorting Application(s),
Sorting, mini experiment,
ADT Introduction,
List ADT (array/vector),
PS1 Discussion
tut02.pdf
PS1, continued
04,
04-08 Feb
No Lab

CNY Reunion Dinner
Affects most 3-6pm classes
No Tue+Wed Lecture

CNY Week
CNY Day 1 on Tue, 05 Feb
CNY Day 2 on Wed, 06 Feb
Thu/Fri Tut Only

Converted to
OPTIONAL+ONLINE
consultation slots
Post CNY hangover
PS1
Due: Sat, 09 Feb 19, 07.59am
(1.5+1+0.5 = 3%)

PS2: LL Problems
Out: Sat, 09 Feb 19, 08.00am
05,
11-15 Feb
D03: PS1 Quick Debrief,
C++ STL (list),
C++ STL (stack/queue/deque),
VA OQ demo (sorting,list)
PS2 Discussion (algorithmic)

Midterm test is
up to end of D03
05a. 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:
evenup (NEW: C++ stack and its usage)
integerlists (NEW: C++ list/deque, use both sides)

05b. 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

Happy Valentine's Day
(this Thu)
T03: List ADT,
Linked List Review,
Stack/Queue/Deque ADT,
Applications,
PS2 Discussion
tut03.pdf

Midterm test is
up to end of T03
PS2, continued
06,
18-22 Feb
D04: C++ STL (priority_queue),
Max-Min conversion,
BinaryHeapDemo (p)review,
Mock Midterm Test 1: throwns
(use Stack for its LIFO behavior,
int wrap around)
Mock Midterm Test 2: froshweek

06a. Midterm Test (15%)
During our Tuesday lecture time (12.05-1.35pm, 90m)
Before recess week, to avoid fighting with other modules on Week 07
Material: Up to Week 05 D03+T03, i.e. Linked List applications
We will totally skip Priority Queue questions
Venue: I3-AUD ['A'..'L'] (137) + COM1-02-06/SR1 ['M'..'Z'] (133)
Open book (no restriction), just no electronic devices...
There is one question that you can probably prepare in advance...
Past Papers:
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 (our paper).

06b. 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)
T04: Midterm Test
Preparation (for 1 Tue AM group 08) or
Solutions (for the rest),
Basic PQ ADT
tut04.pdf

PS2
Due: Sat, 23 Feb 19, 07.59am
(1+1+1 = 3%)

PS3: PQ/Table Problems
Out: Sat, 23 Feb 19, 08.00am
Recess Week, 23 Feb-03 Mar 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 midterm test to be scheduled during recess week
Update on 28 Feb: 268/269 students were present and the only missing student was AWOL, so no make-up midterm test.
07,
04-08 Mar
D05: PS2 Debrief (short),
PS3 Discussion (short),
VisuAlgo OQ demo (heap), quick run,
Mock PE1: rationalsequence2
(observe pattern from vertex to;
reverse path (e.g. with stack/LIFO);
'extension' of numbertree)
07a. Table ADT part 1: Hash Table
C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap
Kattis problems discussed:
oddmanout (assume G = 100 000 codes; map code to f; find only code with f == 1),
whatdoesthefoxsay (assume there are 10 000 animals; string hashing)

07b. More Hashing
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
PS3, continued
08,
11-15 Mar
D06: C++ STL (unordered_map) (short),
C++ STL (unordered_set) (optional),
VisuAlgo OQ demo (hashtable), quick run,
Mock PE2: cd
08a. Table ADT part 2: Binary Search Tree (until slide 11)
C++ STLs: set, map, multiset, multimap,
BST Online Quiz (medium),
Kattis problem discussed:
baconeggsandspam (assume n = 5 000 customers)

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
PS3
Due: Sat, 16 Mar 19, 07.59am
(1.5+1.5+0 = 3%)

PS4: Table Problems
Out: Sat, 16 Mar 19, 08.00am
09,
18-22 Mar
D07: PS3 Debrief (short),
PS4 Discussion (short),
C++ STL (map) (short),
C++ STL (multimap, set, multiset) (optional),
VA OQ demo (bst,avl), quick run
Mock PE3: compoundwords
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.cpp, UVa00469.cpp, and bfs.cpp at GitHub repo of CPbook website,
Kattis problem discussed:
reachableroads (DFS introduction, count #CC)

Singapore National Olympiad in Informatics (NOI 2019)
is on 22-23 March 2019 (the weekend of this week)
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
PS4, continued
10,
25-29 Mar
D08: Mock PE4: wheresmyinternet
Full (almost) one hour (~45m)
"Half" PE simulation
10a. 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)

Practical Exam (12%)
Timing: Tue, 26 Mar 2019, 6.30-8.30pm SGT (2 hours)
Venue: Almost all PLs, totalling ≥ 269 seats/PCs/laptops.
10 Booked Labs (6-9pm, to give buffer time before/after PE):
COM1-B-PL1 (capacity 44)
COM1-B-PL2 (capacity 46)
COM1-B-PL3 (capacity 25)
COM1-B-PL4 (capacity 25)
COM1-B-PL5 (capacity 23)
COM1-01-PL6 (capacity 31)
COM1-01-14/ESTL1 (capacity 24)
COM1-01-13/ESTL2 (capacity 24)
I3-03-39/WsLab1 (capacity 24)
I3-03-38/WsLab2 (capacity 24)
Total: 290 (2 spares per lab)

Lecture 10b on Wed, 27 Mar 2019 8-9am is cancelled
(we are too tired)
T08: Graph DS Review,
Graph DS Conversion Exercise,
Some Graph Properties Discussion,
Graph Modeling exercise 1,
DFS/BFS Review
tut08.pdf
PS4
Due: Sat, 30 Mar 19, 07.59am
(1.5+1.5+0 = 3%)

PS5: Graph Problems
Out: Sat, 30 Mar 19, 08.00am
11,
01-05 Apr
D09: PS4 Debrief (short),
PS5 Discussion (short),
VA OQ demo (graphds), quick run
PE upsolve
Special Class 11a by Jin Zhe
Steven will be in Porto, Portugal
for the entire of this Week 11 due to ICPC World Finals 2019

11a. Live Solve by TA - PQs/Tables/Trees (Heap/bBST)/Graphs
List of selected problems:
builddeps (toposort demo),
brexit (happening or not?),
conformity (mock PE S2 17/18),

Lecture 11b on Wed, 03 Apr 2019 8-9am is cancelled...
T09: DFS/BFS advanced stuffs,
Cycle, Toposort++, (Floodfill/CC),
Modeling exercise 2 (time permitting),
tut09.pdf
PS5, continued
12,
08-12 Apr
D10: VA OQ demo (dfsbfs), quick run
Tips for OQ preparation
(students need to self practice on sssp module),
Class Photo (for momento),
Mock Final Exam: grid,
PS5 last minute discussion (offline)

(Participation Marks Given, 3%)
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)
horror (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 Wednesday
T10: Bellman Ford's, BFS, and
Original Dijkstra's Review,
Modeling exercises 3,
Class Photo (for Friday classes),
tut10.pdf

(Participation Marks Given, 3%)
PS5
Due: Sat, 13 Apr 19, 07.59am
(1.5+1.5+0 = 3%)
13,
15-19 Apr
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
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 on Wed, 17 Apr 2019 8-9am is cancelled too :O...
T11: Final paper preparation,
Class Photo,
tut11.pdf

Good Friday this Week
No Friday Class

No more PS
Study Week, 20-26 Apr 2019
Makeup/remedial Practical Exam is on Tuesday, 23 April 2019, 12-2pm SGT
Venue: PL2 + PL4 (extra 1) + PL1 (extra 2)

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


NUS Online Teaching Feedback System closes on Friday of Study Week

Collection of almost all? past papers @ Kattis.
Last consultation slots on Fri, 03 May 2019, 11am-2.30pm and 4.30-6.00pm at COM1-B-03 Active Learning Lab (max capacity 40 people).
Final Assessment (40%)
Date and Time: Sat, 04 May 2019, 1-3PM
Venue: MPSH1-B

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 very big (269), 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 Tuesday, 01 Jan 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 7 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 7 students who solve all problems of PS1, the first graded PS of CS2040/C
  4. I am a List Master (#): Given to the first 7 students who solve all problems of PS2
  5. Potential TA: (slightly updated): Given to everyone who score ≥ 90.0 points in the Midterm Test: You survived all those intellectual challenges...
  6. Scheduling Master (#): Given to the first 7 students who solve all problems of PS3, including the not graded PS3C
  7. Mapping Master (#): Given to the first 7 students who solve all problems of PS4, including the not graded PS4C
  8. Competitive Programmer to be (#): Given to (up to) first 7*3 = 21 students who can solve all PE problems under that stressful environment
  9. Graph Master (#): Given to the first 7 students who solve all problems of PS5, including the not graded PS5C
  10. 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
  11. 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
  12. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 250.0 or more Kattis points at open.kattis during the execution of CS2040/C in S2 AY18/19 (closed one day before final assessment) (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)