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.
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). It seems to be rather successful (to be confirmed after seeing the first teaching feedback) so Steven is currently planning to use 90% similar setup as with the S1 version, with only a few local changes after seeing the teaching feedback of the S1 version.
The quota of this class for S2 AY2017/18 is 150 students. There are about 100+ CEG students who are expected to take this module in S2. There will be ~50 other InfoSec+minor/second major students to make up the expected total of 150 students, far larger than 37 students in S1. We will see how the class roster ends up by early January 2018.
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.00) 
JanMay 18 (n=~90??/~150??) > 50%??% 
AugNov 17 (n=25+?/37) 65%+? 

Module feedback  4.000 target (will be revised after seeing S1 score)  4.000? (hopefully 'okayish', let's see) 
Module difficulty  3.900 target (will be revised after seeing S1 score)  3.900? (hopefully 'not that hard', let's see) 
Steven's teaching  4.400 target (will be revised after seeing S1 score)  4.400? (hopefully 'okayish', let's see) 
Tutorial Teaching Assistants (8 tutorial sessions prepared so far, but 01A+01B may be merged...):
Date and Time (sort key)  Room (Capacity)  Group Number  Tutorial TA 

Tue, 10:0011:00  COM10203 (20)  05  Ranald Lam Yun Shao 
Tue, 16:0017:00  COM10203 (20)  06  Ranald Lam Yun Shao (those staying outside campus shall choose 06 than 07 to avoid evening rush hour) 
Tue, 17:0018:00  COM10203 (20)  07  Ranald Lam Yun Shao (late afternoon timing, preferably taken by those staying in campus :O) 
Thu, 09:0010:00  COM10201 (20)  01A  TBC (if low enrollment due to potential clash with CS2100 lecture, 1A+1B will be 'merged') 
Thu, 09:0010:00  COM10203 (20)  01B  TBC (must be different than 01A, same timing, but and depends on enrollment) 
Thu, 10:0011:00  COM10201 (20)  02  TBC 
Thu, 11:0012:00  COM10201 (20)  03  TBC 
Thu, 12:0013:00  COM10201 (20)  04  TBC 
Laboratory Teaching Assistants (7 laboratory sessions):
Date and Time (sort key) (no 10:0011:00 slot) 
Room (Capacity)  Group Number (group number is not sequential) 
Lab TA 

Fri, 09:0010:00  COM1B112 (35)  01  Boo Kai Hsien (99%), early morning class, preferably for those staying in campus :O 
Fri, 11:0012:00  COM1B110 (20)  03  Boo Kai Hsien (99%) 
Fri, 11:0012:00  COM10120 (20)  06  TBC (parallel lab, same timing with 03, different Lab TA!) 
Fri, 12:0013:00  COM1B110 (20)  04  TBC 
Fri, 12:0013:00  COM10120 (20)  07  TBC (parallel lab, same timing with 04, different Lab TA!) 
Fri, 13:0014:00  COM1B110 (20)  05  TBC 
Fri, 14:0015:00  COM1B110 (20)  02  TBC 
Btw, this is a starting NUSMODS link for you to plan your S2 (around) CS2040C :O.
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 first lecture). This behavior is normal. You can view it again by scrolling to the top of this page.
Date  News 

Week  Tutorial, 1 hour/week  Lecture, 2x1.5 hours/week Every Thursday 17.0018.30 and Every Friday 17.0018.30 (TBC) from Wk01 Venue: LT15 
Lab Demo, 1 hour/week Every Friday from Wk03 


0, Bef 18 Jan 
Not Started 
Not started, but please revise your CS1010 & CS1231 (Steven assumes that majority of you have taken this module in S1 AY2017/18) 
Not Started  
01, 1519 Jan 
Not Started 
01a. Introduction, Course Admin VisuAlgo + Mooshak + this Private IVLE + Kattis/UVa Basic C++ review: I/O, control flow: repetition, selection, array Kattis problems discussed: statistics, TBA, TBA. 01b. Introduction to C++ (live demo format) Basic C++ review (continued): function, simple class, string (stream) C++ STL vector Kattis problems discussed: zamka, bookingaroom, autori 
Not Started  
02, 2226 Jan 
Not Started 
02a. Analysis of Algorithms Kattis problems discussed: (several previous problems), register Reminder: Read sorting eLecture slides before coming to Lecture 2b 02b. Sorting (first half) Sorting Online Quiz (easy), C++ STL algorithm: sort, stable_sort Kattis problems discussed: mjehuric, cups, sortofsorting 
Not Started  
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) Focus on the harder content of sorting eLecture and sorting Online Quiz Sorting Online Quiz (medium), C++ STL algorithm 03b. Application 1  Arrays/Vectors+Sorting Kattis problems discussed: TBA, TBA 
D01: Introduction, C++ STL (algorithm, vector) C++ string Review C++ code so far 

04, 0509 Feb 
T02: Sorting (part 2), One Application, ADT Introduction List ADT (array/vector), tut02.pdf, tut02ans.pdf (just see Ranald's) 
04a. List ADT: Linked List, Stack ADT Focus on the harder content of SLL; intro to Stack ADT Linked List Online Quiz (easy), C++ STLs: list, stack Kattis problem discussed: evenup 04b. Queue, Deque ADTs: Linked List variants Focus on Queue, DLL, Deque and a few other small technicalities of Linked List Linked List Online Quiz (medium), C++ STLs: queue, deque Kattis problem discussed: TBA 
D02: C++ OOP Review List ADT (vector), We implement this, One sorting challenge, PS1 debrief, VisuAlgo OQ demo (sorting) 

05, 1216 Feb 
T03: List ADT, Linked List Review, Stack/Queue/Deque ADT, Applications tut03.pdf, tut03ans.pdf (juset see Ranald's) 
05a. Review of Graphs and Trees (until 64) CS1231 happens to be not a prereq of CS2040C, so I will play safe 05b. Priority Queue (PQ) ADT: Binary Heap Binary Heap Online Quiz (medium), C++ STL: priority_queue Happy Valentine's Day (Wed) and Happy CNY (FriSat) of this Week 05 
D03: C++ STL (list), C++ STL (stack/queue/deque), Implementation Demo (PS2 D), VisuAlgo OQ demo (list) 

06, 1923 Feb 
T04: CS1231 Review, Priority Queue ADT, Midterm Test Preparation, tut04.pdf, tut04ans.pdf (just see Ranald's) 
06a. Application 2  Lists+PQ Mock Midterm Test :O Kattis problems discussed (maybe changed): server, pivot, numbertree 06b. Midterm Test (15%) During our Friday lecture time Before recess week, to avoid fighting with other modules on Week 07 Material: Up to Week 06 T04, i.e. Priority Queue For the question paper and modal answer (see IVL after test) 
D04: PS2 debrief C++ STL (priority_queue), MaxMin conversion, BinaryHeapDemo (in C++), Demo on solving UVa 1203, Midterm test preparation 

We can take a break this week :) 

07, 0509 Mar 
T05: Midterm Test Debrief, Deeper Binary Heap stuffs, tut05.pdf (TBA), tut05ans.pdf (just see Ranald's) 
07a. Table ADT part 1: Hash Table Hash Table Online Quiz (easy) 07b. More Hashing Hash Table Online Quiz (medium), C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap Kattis problem discussed: cd 
D05: PS3 discussion, C++ STL (unordered_map), C++ STL (unordered_set), VisuAlgo OQ demo (heap), 

08, 1216 Mar 
T06: Table ADT 1  unordered, Hashing concepts, Hash Table issues, tut06.pdf (TBA), tut06ans.pdf (just see Ranald's) 
08a. Table ADT part 2: Binary Search Tree BST Online Quiz (easy, BST only), BSTDemo.cpp 08b. AdelsonVelskii Landis (AVL) Tree BST Online Quiz (medium, including AVL), C++ STLs: set, map, multiset, multimap, AVLDemo.cpp, Kattis problem discussed: compoundwords 
D06: PS3 debrief, C++ STL (set, map), Indexing demo, Demo on Solving this, this, or ?? 

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 (TBA), tut07ans.pdf (just see Ranald's) 
09a. Graph Data Structures + Simple Applications 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 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, 
D07: PS4 discussion, VisuAlgo OQ demo (hashtable, bst/avl), Graph DS review, Graph DS conversions, 

10, 2630 Mar 
T08:
Some Graph Properties, Conversion exercises, Modeling exercise 1, DFS/BFS Review tut08.pdf, tut08ans.pdf (just see Ranald's) 
10a. Graph Traversal continued (we skip slide 812, out of CS2040C scope) DFS/BFS Online Quiz (medium) Kattis problems discussed: reachableroads, runningmom 10b. SingleSource Shortest Paths (SSSP) Problem: Bellman Ford's, BFS SSSP Online Quiz (easy), No builtin C++ STL algorithm, see ch4_06_bellman_ford.cpp in ch4.zip of CPbook website, Kattis problem discussed: hidingplaces 
D08: PS4 debrief, VisuAlgo OQ demo (graphds, dfsbfs), Mock PE 1, By solving this in << 23 minutes 

11, 0206 Apr 
T09: DFS/BFS advanced stuffs, Cycle, Floodfill, Bipartite, Toposort++, Modeling exercise 2, tut09.pdf, tut09ans.pdf (just see Ranald's) 
11a. SSSP continued: Dijkstra's (2 versions), On Tree, On DAG SSSP Online Quiz (medium), No builtin C++ STL algorithm, see ch4_05_dijkstra.cpp in ch4.zip of CPbook website, Kattis problem discussed: shortestpath1 11b. Practical Exam (12%) Timing: TBC Venue: Several PLs (so that we can accommodate ~150 people) We will use strict PE setup There will be two tasks, based on what we have discussed in the past 11 weeks 
D09: Mock PE 2, By solving ?? in << 23 minutes (TA may give extra exercise(s)) VisuAlgo OQ demo (sssp) 

12, 0913 Apr 
T10: BFS, Bellman Ford's, Dijkstra's Review, Modeling exercises 3, tut10.pdf, tut10ans.pdf (just see Ranald's) 
12a. Application 3  Trees and Graphs Mock Final Assessment 1: Kattis problems discussed (maybe changed): kitten, wheresmyinternet, grid 12b. Application 4  Mix and Match, Last Lecture Mock Final Assessment 2: Kattis problems discussed (maybe changed): rationalsequence2, visualgo. Closed with a few minutes of semester summary, followed with review of what can be done better for future iterations... 
D10: VA Online Quiz (12%) (URL: https://visualgo.net/training, click 'CS2040C Quiz') Time: 35m, 20 random (may luck be with you) questions All topics in CS2040C Steven may enhance VA OQ system for S2 version 

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

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: TBA Venue: TBA 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)
Tut  Lab  Student Name 
