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, hash tables, binary heaps, binary search trees, and graphs), searching and sorting algorithms, basic analysis of algorithms, and basic objectoriented programming concepts.
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.
This is the second time CS2040/C is offered (the first one was in S1 of this AY2017/18, which was rather successful). Steven is currently planning to use 90% similar setup as with the S1 version, with only a few local changes after studying the teaching feedback of the S1 version.
The quota of this class for S2 AY2017/18 was initially predicted at 150 students by early Dec 2017 but is subsequently revised to be 220 students by early Jan 2018. After CORS round 3B ends and a few casebycase appeals later, we are currently at 173 students. There are about 120+ CEG students and about 30+ InfoSec students (first ~10 have took my CS2040C in S1) who are expected to take this module in S2. The rest are minor/second major/exchange students. This is far larger than 37 students in S1.
Note: The old CS1020 and CS2010 will still remain in AY2017/2018 (will continually having smaller sizes in future semesters) but will only be applicable for older cohort only (freshmen cohort in AY2017/2018 onwards will have to go through CS2040/C route).
Some other facts:
Rating (out of 5.0) 
JanMay 18 (n=120+/173) > 70% 
AugDec 17 (n=28/37) 76% 

Module feedback  Target: 4.3+ (maintain)  4.4 (above CS dept average :) 
Module difficulty  Target: 4.0 (lower this by a bit)  4.1 (harder than CS dept average :O) 
Steven's teaching  Target: 4.5+ (maintain)  4.7 (Thanks God :) 
Tutorial Teaching Assistants (10 tutorial sessions, sorted chronologically):
Date, Time  COM1 Room (#Stu)  No  Tutor 

Tue, 0910  0203SR6 (20)  08  Steven 
Tue, 1011  0203SR6 (14)  05  Ranald 
Tue, 1617  0203SR6 (20)  06  Ranald 
Tue, 1718  0203SR6 (21)  07  Ranald 
Thu, 0910  0210SR10 (28)  01  Phuc 
Thu, 1011  0201SR5 (17)  02  Phuc 
Thu, 1112  0201SR5 (19)  03  Melvin 
Thu, 1213  0201SR5 (16)  04  Melvin 
Thu, 1213  0203SR6 (08)  09  Phuc 
Thu, 1314  0201SR5 (10)  10  Melvin 
Laboratory Teaching Assistants (9 laboratory sessions, sorted chronologically):
Date, Time  COM1 Room (#Stu)  No  Lab TA 

Fri, 0910  B112PL1 (28)  01  JunAn+Duong 
Fri, 0910  B110PL5 (17)  02  Chris 
Fri, 1011  B110PL5 (20)  09  Chris 
Fri, 1112  B110PL5 (20)  03  Chris 
Fri, 1112  0120PL6 (19)  06  Duong 
Fri, 1213  B110PL5 (18)  04  Sidhant 
Fri, 1213  0120PL6 (21)  07  JunAn 
Fri, 1314  B110PL5 (19)  05  Sidhant 
Fri, 1314  0120PL6 (11)  08  JunAn 
This is what you will learn if you take CS2040C in S1 or S2 (both taught by Steven):
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.
Note: This course registration section will not be prominent from Week 1 of S2 AY 2017/2018 onwards (after CORS Round 3B). This behavior is normal. You can view it again by scrolling to the top of this page.
Date  News 

Week  Tutorial, 1 hour/week On Tuesday or Thursday From Wk03 
Lecture, 2x1.5 hours/week Every Thursday 17.0018.30 and Every Friday 17.0018.30 from Wk01 Venue: LT15 
Lab Demo, 1 hour/week Every Friday from Wk02 (we will have to skip Friday of Wk05) 


02/01, Bef 15 Jan 
Not Started 
Not started, but please revise your CS1010 (Steven assumes that all? of you have taken this module/its variants) & maybe also CS1231 (Steven assumes that some? of you have taken this module) 
Not Started  
01, 1519 Jan 
Not Started 
01a. Course Admin, Introduction to C++ Setting the tone for a flipped classroom module, VisuAlgo + Mooshak + this Private IVLE + Kattis/UVa Basic C++ review using a few Kattis problems: statistics (revise I/O, control flow: repetition, selection), treasurehunt (revise (2D character) array, (recursive) function). 01b. Introduction to C++ (continued) Basic C++ review/new feature introduction using a few Kattis problems: zamka (review: function), bookingaroom (NEW: C++ class, C++ STL vector), autori (NEW: C++ string, C++ istringstream) 
Not Started  
02, 2226 Jan 
Not Started 
02a. Analysis of Algorithms (old CS1020/E lecture note on this topic will be digitised later) Kattis problems discussed: (several previous problems, with analysis) Reminder: Read sorting eLecture slides before Lecture 02b At least until slide 83, preferably more 02b. Sorting (first half until slide 83) C++ STL algorithm: sort, stable_sort Live discussion of a few easier sorting problems @ Kattis: mjehuric (bubble sort simulation), lineup (sort ascending or descending?, NEW: C++ STL sort), sortofsorting (NEW: custom comparator, C++ STL stable_sort) 
D01: Introduction, C++ STL (algorithm, vector), C++ string, Review C++ code so far Started early due to CNY and Good Friday 

03, 29 Jan 02 Feb 
T01: Introduction, C++ OOP (basic), Analysis, Sorting (part 1) tut01.pdf, tut01ans.pdf (just see Ranald's) 
03a. Sorting (second half, until end) Focus on the harder content of sorting eLecture and sorting Online Quiz, Sorting Online Quiz (medium) 03b. List ADT: Linked List, Stack ADT (until slide 47) Focus on the harder content of SLL; intro to Stack ADT, C++ STLs: forward_list (an SLL), list (a DLL), stack Kattis problem discussed: evenup (NEW: C++ std::stack and its usage) 
D02: C++ OOP Review List ADT (vector), We implement this, One sorting challenge, VisuAlgo OQ demo (sorting), PS1 Preview 

04, 0509 Feb 
T02: Sorting (part 2), One Application, ADT Introduction List ADT (array/vector), tut02.pdf, tut02ans.pdf (just see Ranald's) 
04a. Queue, Deque ADTs: Linked List variants (until end) Focus on Queue, DLL, Deque and a few other small technicalities of Linked List, Linked List Online Quiz (medium), C++ STLs: queue, deque (actually not a DLL), Kattis problem discussed: integerlists (NEW: C++ std::list/deque, use both sides) 04b. Priority Queue (PQ) ADT: Binary Heap C++ STL: priority_queue, partial_sort, Kattis problem discussed: numbertree (reversed Binary Heap indexing, NEW: << bit shift operator), Binary Heap Online Quiz (medium) 
D03: C++ STL (list), C++ STL (stack/queue/deque), PS2 Preview, Implementation Demo (PS2 D/partial), VisuAlgo OQ demo (list) 

05, 1216 Feb 
T03: List ADT, Linked List Review, Stack/Queue/Deque ADT, Applications tut03.pdf, tut03ans.pdf (just see Ranald's) Midterm test is up to end of T03 
No Lecture on Thursday (CNY Reunion Dinner) :O That lecture slot will be converted into Steven's consultation slot @ LT15 Reserved for ~20+ nonChinese sounding names in CS2040C IVLE class roster No Lecture on Friday (CNY PH Day 1) Happy Valentine's Day (Wed) and Happy CNY (FriSat) of this Week 05 
No Lab CNY 

06, 1923 Feb 
T04: Midterm Test Preparation, Priority Queue ADT, tut04.pdf, tut04ans.pdf (just see Ranald's) Phuc is away on Monday and Ranald is away for IOI 2018 Winter Meeting (entire Week 06) Steven takes over 
06a. Application 1  C++/Arrays/Vectors/Sorting/Lists Mock Midterm Test :O, can be a major wake up call..., This is a kind of CS2040C Week 0104 review, Kattis problems discussed: greedilyincreasing (cpp/growing list/vector), synchronizinglists (sort/binary search/remapping), server (FIFO/queue/or just onthefly computation) 06b. Midterm Test (15%) During our Friday lecture time (5.056.05pm) Before recess week, to avoid fighting with other modules on Week 07 Material: Up to Week 05 T03, i.e. Linked List applications Open book (no restriction), just no electronic devices... For the question paper and modal answer (see IVLE after test) Venue: ~Half (those attending Thursday tutorial groups: 01+02+03+04+09+10) at LT15 ~Half (those attending Tuesday tutorial groups: 08+05+06+07) at LT19 Past Paper: CS2040C201718S1midtermmedium.pdf (PS: 22 Sep 2017 was a Friday). 
D04: PS1 debrief, C++ STL (priority_queue), MaxMin conversion, Demo on solving UVa 01203, Midterm test preparation 

We can take a break (again :O) this week :) But if possible, read Hash Table and BST eLecture slides by yourself first... 

07, 0509 Mar 
T05: Midterm Test Debrief, Deeper Binary Heap stuffs, tut05.pdf, tut05ans.pdf (just see Ranald's) 
07a. Table ADT part 1: Hash Table C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap Kattis problem discussed: oddmanout (assume G = 100 000 invitation codes; map code to frequency; find frequency 1) 07b. More Hashing HashTableDemo.cpp, Hash Table Online Quiz, Kattis problem discussed: whatdoesthefoxsay (assume there are 10 000 animals/words/sounds; string hashing) 
D05: PS2 debrief (short), BinaryHeapDemo.cpp, PS3 discussion, VisuAlgo OQ demo (heap), C++ STL (unordered_map, short), C++ STL (unordered_set, short), Mock PE 1: cd (if unordered, we need Hash Table) 

08, 1216 Mar 
T06: Table ADT 1  unordered, Hashing concepts, Hash Table issues, tut06.pdf, tut06ans.pdf (just see Ranald's) 
08a. Table ADT part 2: Binary Search Tree C++ STLs: set, map, multiset, multimap, Kattis problem discussed: baconeggsandspam (assume n = 5 000 customers) 08b. AdelsonVelskii Landis (AVL) Tree BST Online Quiz (medium, including AVL), BSTDemo.cpp and AVLDemo.cpp, No Kattis live problem solving as this lecture is a bit technical 
D06: C++ STL (set, map, short), Indexing demo, VisuAlgo OQ demo (hashtable), Mock PE 2: compoundwords (use set to help), 

09, 1923 Mar 
T07: Table ADT 2  ordered, BST/AVL advanced stuffs, PQ ADT alternative implementation, Comparison with Table ADT 1, unordered vs ordered tut07.pdf, tut07ans.pdf (just see Ranald's) 
09a. Graph Data Structures + Simple Applications CS1231 happens to be not a prereq of CS2040C, so I will play safe by reviewing a bit of CS1231 (graph topic) first, Graph DS Online Quiz (medium), No builtin C++ STL container, see ch2_07_graph_ds.cpp in ch2.zip of CPbook website, Kattis problem discussed: flyingsafely (for a 30s jawdropping moment) 09b. Graph Traversal: DFS/BFS + Simple Applications DFS/BFS Online Quiz (easy), No builtin C++ STL algorithm see ch4_01_dfs.cpp, ch4_02_UVa00469.cpp, and ch4_04_bfs.cpp in ch4.zip of CPbook website, No Kattis live problem solving, deferred to Lecture 09c slot. 09c. Application 2  Everything so far Date and Time: Saturday, 24 March 2018, 9am2pm @ home/online Due to CNY PH on Week 05 and Good Friday PH on Week 10 See details at this Facebook post. Kattis problem discussed: 09.00am09.58am, classy (sort, string parsing, 'encode'), 10.03am10.51am, throwns (stack, int hash/wrap around), 11.00am11.42am, rationalsequence2 (binary heap (tree) path indexing, stack/LIFO), 11.53am12.50pm, bard (Table ADT or 2D array; loops), 01.00pm01.45pm, wheresmyinternet (graph DS+traversal, connected components). 
D07: PS3 debrief, PS4 discussion, Graph DS conversions (one example), VisuAlgo OQ demo (bst/avl, graphds), Mock PE 3: PE S1 Q1 (minmax PQ; multiset) 

10, 2630 Mar 
T08: Some Graph Properties, (CS1231 short review), Conversion exercises, Modeling exercise 1, DFS/BFS Review tut08.pdf, tut08ans.pdf (just see Ranald's) 
10a. Graph Traversal continued (just slide 7) (we skip slide 812, out of CS2040C scope) Graph DS + DFS/BFS Online Quiz (medium) Kattis problems discussed: reachableroads (DFS, count #CC), runningmom (AL of strings; DFS; back edge detection) No Lecture on Friday (replaced by Lecture 09c slot above) Good Friday followed by Easter Sunday this Week 
No Lab Good Friday 

11, 0206 Apr 
T09: DFS/BFS advanced stuffs, Cycle, Floodfill, Toposort++, Modeling exercise 2, tut09.pdf, tut09ans.pdf (just see Ranald's) 
11a. SingleSource Shortest Paths (SSSP) Problem: Bellman Ford's, BFS No builtin C++ STL algorithm, see ch4_06_bellman_ford.cpp in ch4.zip of CPbook website, Kattis problem discussed: hidingplaces (BFS demo; implicit graph demo) 11b. Application 3 (Mock PE 5)  Tables/Trees (Heap/bBST)/Graphs Last Mock Practical Exam :O: Kattis problem discussed: conformity (< 3 pointer previously, map of set to int frequencies), 11c. Practical Exam (12%) Timing: Friday, 06 April 2018, 79pm SGT Venue: PL123456 :O, totalling 190 seats/PCs (so that we can accommodate ~173 people) Students will be allowed to enter PL at 6.50pm to do these (it takes time): 1). login to Windows desktop (with a special PE account), and We will use strict PE setup (no public Internet access) 2). open a web browser (URL: http://algorithmic.comp.nus.edu.sg/~mooshak) With Mooshak, Steven will auto start PE at 7pm sharp and end PE at 9pm sharp Open book (no restriction, BRING DICTIONARY if you are not native English speaker) There will be two trivial tasks, based on what we have discussed in the past 10 weeks (up to DFS/BFS) Other PE related announcements can be found at this Facebook post 
D08: PS4 debrief, PS5 discussion, VisuAlgo OQ demo run (all) Mock PE 4: PE S1 Q2 (2D grid; floodfill), (TA may give extra exercise(s)) 

12, 0913 Apr 
T10: BFS, Bellman Ford's, Dijkstra's Review, Modeling exercises 3, tut10.pdf, tut10ans.pdf (just see Ranald's) 
12a. SSSP continued: Dijkstra's (original version+implementation) Kattis problem discussed: shortestpath1 (that Dijkstra's implementation is easy) No builtin C++ STL algorithm, see ch4_05_dijkstra.cpp in ch4.zip of CPbook website, SSSP Online Quiz (hard), (last preparation for VisuAlgo Online Quiz tomorrow morning), 12b. SSSP continued: Modified Dijkstra's, On Tree, On DAG, Last Lecture Kattis problems discussed: shortestpath1 (modified Dijkstra's implementation) getshorty (preview of log(a*b*c) to log(a)+log(b)+log(c) transformation) Closed with a few minutes of semester summary, followed with review of what can be done better for future iterations... 
D09: 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 may add a few questions in VA OQ system for S2 OQ 

13, 1620 Apr 
T11: Harder SSSP, FW/APSP, Final preparation, Class Photo, tut11.pdf, tut11ans.pdf (just see Ranald's) (Participation Marks Given, 3%) Steven is away for ACM ICPC World Finals 2018 Ranald takes over 
NO LECTURE AT ALL THIS WEEK Steven and three NUS ACM ICPC members (team DomiNUS) went to Beijing to represent NUS for ACM ICPC World Finals 2018 
D10: PE debrief, OQ debrief, PS5 debrief, Final preparation, Class Photo. (Participation Marks Given, 3%) 

Make up (+Remedial) PE on Tue, 24 Apr 2018, 10am12pm for those scoring < 6 in the actual PE Final Assessment Consultations (per request) Written Quiz 2 Past Papers (from other relevant modules, notice that the syllabus have changed!): CS2010201112S1WQ2medium.pdf, CS2010201213S1WQ2medium.pdf, CS2010201314S1WQ2medium.pdf, CS2010201415S1WQ2medium.pdf, CS2010201516S1WQ2medium.pdf. Final Assessment Past Papers (from other relevant modules, notice that the syllabus have changed!): CS2010201112S1final.pdf, CS2010201213S1final.pdf, CS2010201314S1final.pdf, CS2010201415S1final.pdf, CS2010201516S1final.pdf. Final Assessment Past Papers: CS2040C201718S1final.pdf. 

Date and Time: Thu, 10 May 2018, EV (near last day of exam period... again...) This is technically almost one month after the last lecture on Friday, 13 April 2018... Venue: MPSH5 (apparently together with the bigger 250+ students of CS2040) This year paper (S2 AY 2017/18) is OBVIOUSLY NOT AVAILABLE YET :O.... 
Steven uses a smallscale gamification system in his version of CS2040C 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).
Only students with at least one achievement will be listed below (so the list is not the full class roster).
Student Name 
