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 first time CS2040/C is offered after the CS1020+CS2010 combination in the past six years. Thus there is no comparable reference yet other than the fact that this module is "CS1020+CS2010 but without the basic form of recursion (shifted downwards to CS1010), without advanced form of Java/C++/OOP stuffs (shifted sideways to CS2030), without MST and the last part of old CS2010/DP (both shifted upwards to CS3230)". Also, CS2040/C is a subset of the no longer available CS2020.
The quota of this class for S1 AY2017/2018 is 80 students. But ~120 CEG students, ~40 InfoSec students, and ~40 minor/second major students are expected to take this module across S1 or S2 in AY 2017/2018. So that is ~(120+40+40) ~= 200 students across 2 semesters, with more students in S2 than in S1 so I am expecting 80 vs 120 in S1 vs S2... After Week 02, the class size for Sem1 is just 40 students, exactly half of the expected 80, with the only 'correct' projection is the number of senior students who are taking CS2040C for minor/second major (about ~25).
The old CS1020 and CS2010 will still remain in AY2017/2018 (still have normal size this S1 but will have 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:
Tutorial Teaching Assistant (2 tutorial sessions @ COM10230, every Monday, 1415 or 1516):
Laboratory Teaching Assistant (2 laboratory sessions @ COM1B112, every Friday 0910 or 1011):
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 S1 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 Every Monday from Wk03, 1415 or 1516 Venue: COM10203 Ranald's Consultation: Mon 910 Venue: COM1215 (ACM ICPC Lab) 
Lecture, 2x1.5 hours/week Every Thursday 1617.30 and Every Friday 1213.30 from Wk01 Venue: COM10212 (SR3) 
Lab Demo, 1 hour/week Every Friday from Wk03, 910 or 1011 Venue: COM1B112 


0, Bef 14 Aug 
Not Started 
Note 1: Steven visited Tehran, Iran for IOI 2017 (27 Jul05 Aug 2017) Note 2: National Day, Wed, 09 Aug 2017 Not started, but please revise your CS1010 & CS1231 (if you have took this module) 
Not Started  
01, 1418 Aug 
Not Started 
01a. Introduction, Course Admin VisuAlgo + Mooshak + this Private IVLE + Kattis/UVa Basic C++ review: I/O, control flow: repetition, selection Kattis problems discussed: hello, timeloop, eligibility 01b. Introduction to C++ (new format) Basic C++ review (continued): array, function, simple class, C++ STL vector Kattis problems discussed: statistics, zamka, bookingaroom 
Not Started  
02, 2125 Aug 
Not Started 
02a. Analysis of Algorithms (new format) Basic C++ review (continued): string (stream) Kattis problem discussed: autori Analysis of simple C++ programs that use simple arrays/vectors Kattis problems discussed: (several previous problems), register Reminder 1: There is D01 tomorrow morning (Friday, 25 Aug) Reminder 2: 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 
D01: Introduction, C++ STL (algorithm, vector) C++ string Review C++ code so far 

03, 28 Aug 01 Sep 
T01: Introduction, C++ OOP (basic), Analysis, Sorting (part 1) tut01.pdf, tut01ans.pdf (see IVLE) 
03a. Sorting (second half) Focus on the harder content of sorting eLecture and sorting Online Quiz Sorting Online Quiz (medium), C++ STL algorithm PS: Hari Raya Haji, Fri, 01 Sep 2017 No Friday class 
MOVE UPWARDS to Week02 (confirmed, so we start coding from Week02) PS: Hari Raya Haji, Fri, 01 Sep 2017 No Friday class today 

04, 0408 Sep 
T02: Sorting (part 2), One Application, ADT Introduction List ADT (array/vector), tut02.pdf, tut02ans.pdf (see IVLE) 
04a. List ADT: Linked List Focus on the harder content of SLL; can already touch Stack ADT in future lecture 4a Linked List Online Quiz (easy), C++ STL: list 04b. Stack, Queue, Deque ADTs: Linked List variants Focus on Stack, Queue, DLL, Deque and a few other small technicalities of Linked List Linked List Online Quiz (medium), C++ STLs: stack, queue, deque Kattis problem discussed: evenup 
D02: C++ OOP Review List ADT (vector), We implement this, One sorting challenge, PS1 debrief, VisuAlgo OQ demo (sorting) 

05, 1115 Sep 
T03: List ADT, Linked List Review, Stack/Queue/Deque ADT, Applications tut03.pdf, tut03ans.pdf (see IVLE) 
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 
D03: C++ STL (list), C++ STL (stack/queue/deque), Implementation Demo (PS2 D), VisuAlgo OQ demo (list) 

06, 1822 Sep 
T04: CS1231 Review, Priority Queue ADT, Midterm Test Preparation, tut04.pdf, tut04ans.pdf (see IVLE) 
06a. Application 1  Arrays/Vectors+Sorting+Lists+PQ Mock Midterm Test :O Kattis problems discussed: 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 IVLE) 
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, 0206 Oct 
T05: Midterm Test Debrief, Deeper Binary Heap stuffs, tut05.pdf, 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, 0913 Oct 
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 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, 1620 Oct 
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) 
PS: Deepavali, 18 Oct 2017 (Wed) 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, 2327 Oct 
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, 30 Oct 03 Nov 
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 (9%) Timing: During our 12.001.30pm (90m) lecture slot Venue: COM1BPL2 (capacity 46) We can do this as current class size (37) is ≤ 46 You are allowed to use your own laptop (or use what we have at PL2 PCs) There are two tasks, based on what we have discussed in the past 11 weeks To minimize coding stress, Steven will only upload easiest test case per task (full test cases for problem A+B will still be setup at problem C+D though) More detailed judging will be done post PE 
D09: Mock PE 2, By solving ?? in << 23 minutes (TA may give extra exercise(s)) 

12, 0610 Nov 
T10: BFS, Bellman Ford's, Dijkstra's Review, Modeling exercises 3, tut10.pdf, tut10ans.pdf (just see Ranald's) 
12a. Application 2  Trees and Graphs Mock final assessment 1: Kattis problems discussed: kitten, wheresmyinternet, grid Steven+Ranald++ departed to ACM ICPC Jakarta 2017 on Friday 10 Nov 2017 morning 12b. Cancelled Steven is away for ACM ICPC Jakarta 2017, 10111213 Nov 2017 
D10: PE debrief, PS5 debrief, VisuAlgo OQ demo (sssp), Class Photo. (Participation Marks Given, 3%) 

13, 1317 Nov 
Cancelled T11 is moved to Lecture 13a timing Ranald is part of NUS ACM ICPC team 1 We only reached Changi by 2.30pm this day :O 
13a is T11 as Steven will disappear for this :O (timing clash) Ranald will run T11 in this Lecture 13a slot. T11: Harder SSSP, FW/APSP, Final, Class Photo, (Participation Marks Given, 3%) tut11.pdf, tut11ans.pdf (just see Ranald's) 13b. Application 3  Mix and Match, Last Lecture Mock Final Assessment 2: Kattis problems discussed: rationalsequence2, visualgo. Closed with a few minutes of semester summary, followed with review of what can be done better for future iterations... 
D11: VA Online Quiz (15%) (URL: https://visualgo.net/training, click 'CS2040C Quiz') Time: 35m, 20 random (may luck be with you) questions All topics in CS2040C 

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. 

Date and Time: Wed, 06 Dec 2017, EV Venue: COM10206 (SR1) This year paper (S1 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 
