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, hash tables, binary heaps, binary search trees, and graphs), searching and sorting algorithms, basic analysis of algorithms, and basic object-oriented 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.

Course Registration

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 case-by-case 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:

  1. Steven has just taught the first version of CS2040/C in S1 of this AY2017/18, which was rather successful. Steven uses flipped classroom, machine-teach-(and-auto-test)-students, and in-class live discussion of (hard)er problems.
  2. Steven has 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)
    Jan-May 18
    (n=145/173)
    84%
    Aug-Dec 17
    (n=28/37)
    76%
    Module feedback 4.3 (5x larger class) 4.4 (above CS dept average :)
    Module difficulty 4.0 (5x larger class) 4.1 (harder than CS dept average :O)
    Steven's teaching 4.5 (5x larger class) 4.7 (Thanks God :)

    Tutorial Teaching Assistants (10 tutorial sessions, sorted chronologically):

    Date, Time COM1 Room (#Stu) No Tutor
    Tue, 09-10 0203-SR6 (20) 08 Steven
    Tue, 10-11 0203-SR6 (14) 05 Ranald
    Tue, 16-17 0203-SR6 (20) 06 Ranald
    Tue, 17-18 0203-SR6 (21) 07 Ranald
    Thu, 09-10 0210-SR10 (28) 01 Phuc
    Thu, 10-11 0201-SR5 (17) 02 Phuc
    Thu, 11-12 0201-SR5 (19) 03 Melvin
    Thu, 12-13 0201-SR5 (16) 04 Melvin
    Thu, 12-13 0203-SR6 (08) 09 Phuc
    Thu, 13-14 0201-SR5 (10) 10 Melvin
    1. Dr Steven Halim (1 group, the first one, as weekly benchmark); consultation hour: Friday, 2-4pm @ his office (COM1-03-37)
    2. Ranald Lam Yun Shao (the other 3 groups on Tuesday; also CS2040C TA in S1; will disappear on Week 06 for IOI 2018 Winter Meeting (Steven will step in)); consultation hour: Tuesday, 11am-1pm @ ACM ICPC Lab (COM1-02-15, opposite SoC UG office)
    3. Melvin Tan Jun Keong (3 groups on Thursday; previous CS1020E TA under Steven; consultation hour: Wednesday, 4-6pm @ COM1-02-Lobby Area)
    4. Le Minh Phuc (the other 3 groups on Thursday; previous CS2010 TA under Dr Zhao Jin; consultation hour: Monday, 10am-12pm @ COM1-02-Lobby Area)

    Laboratory Teaching Assistants (9 laboratory sessions, sorted chronologically):

    Date, Time COM1 Room (#Stu) No Lab TA
    Fri, 09-10 B112-PL1 (28) 01 JunAn+Duong
    Fri, 09-10 B110-PL5 (17) 02 Chris
    Fri, 10-11 B110-PL5 (20) 09 Chris
    Fri, 11-12 B110-PL5 (20) 03 Chris
    Fri, 11-12 0120-PL6 (19) 06 Duong
    Fri, 12-13 B110-PL5 (18) 04 Sidhant
    Fri, 12-13 0120-PL6 (21) 07 JunAn
    Fri, 13-14 B110-PL5 (19) 05 Sidhant
    Fri, 13-14 0120-PL6 (11) 08 JunAn
    1. (Chris) Boo Kai Hsien (3 groups)
    2. Tan Jun An (3 groups, but will only grade 2 groups)
    3. Sidhant Bansal (2 groups)
    4. Hoang Duong (1 group + grading of another 1 group; also CS2040C Lab TA in S1; away on Friday of Week05/CNY week (but it is a PH anyway))
  4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
  5. Have you passed (or exempted from) CS1231 (esp for Y1S1 students)? It is strongly recommended. Consider taking it first and do CS2040/C later if you can. Anyway, Steven will do a quick review of the important (very small) parts of CS1231 in the middle of CS2040C.
  6. Have you taken CS1020/CS1020E/CS2010/CS2020? You cannot take CS2040C 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 CS2040C in S1 or S2 (both 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 CS2040C?
A: Yes, once only, at Week 11, nearing the end of the semester, after sufficient practices in Lab Demos and PSes. This time (S2), we will use full controlled PE setup as the class size is large. The timing will be on Friday night so that I can book the entire PLs in COM1-Basement (PL1-2-3-4-5) plus PL6 in COM1-level 1...
Q: Will this module be graded using Bell curve?
A: For S2 version (~173 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 2017/early January 2018?
A: Yes, that is a 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 CS2040C?
A: The choice of IDE is entirely up to you. But note that we will have Practical Exam (PE) on Week 11, so try to be familiar with the (C++) programming tools what we have in our various PLs.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my Competitive Programming book, the 3.17b 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 ~2750+ problems in that book (CP3.17b) 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: I don't think so, as this is a level-2 core module. CS2040C 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 AY2017/18 freshmen who are going to take the S2 version, I believe that most of you have just cleared CS1010/its variants in S1, so this CS2040C is not S/U-able if you choose to do CS2040C as per normal timeline, i.e. in Y1S2.
Q: I heard from my friend/senior that this CS2040C is a flipped classroom module?
A: You heard that correctly. Steven is working hard at the background to 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 2x1.5h (effective 2x75m = 150m 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 experiment was conducted with 37 students in S1 and it seems to be rather successful.
Q: What are the potential changes that you will apply to CS2040C in S2 compared to S1 version (that I heard from my friend/senior)?
A: These are the potential changes:
  1. Changing PS deadline to Saturday morning instead of Thursday evening to give slightly more time for students to complete them
  2. Reducing VA OQ (all machine, ceiling effect frequently observed) percentage from 15% down to 12% and raising PE (human creativity in action, normal distribution) percentage from 9% up to 12%
  3. Adding a few interesting new questions in VA question bank to reduce the ceiling effect in VA OQ component
  4. Enhancing various VA e-Lecture slides so that Steven receives even less 'basic' question than the already low number in S1, including adding a few more example code and self-check MCQs for earlier e-Lectures
  5. To minimize boredom of re-solving the same set of Kattis exercise problems, Steven intends to change some example problems compared to what he solved live in S1
  6. Ending the class by Week 12, as Steven is totally not available on Week 13 for an all important ACM ICPC World Finals 2018...
  7. As there will not be any lecture on Week 13, Steven will start the class 'online' a bit during Week -1...
  8. All others are planned to be kept roughly constant as in S1 version as Steven wants to know whether flipped classroom strategy that was proven to work in S1 with a smaller class can be scaled up to ~173 students (~4.7x bigger)...

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.

News

Date News

Lesson Plan

Week Lecture, 2x1.5 hours/week
Every Thursday 17.00-18.30 and
Every Friday 17.00-18.30
from Wk01
Venue: LT15
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
15 Jan
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)
01,
15-19 Jan
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)
02,
22-26 Jan
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 e-Lecture slides before Lecture 02b
At least until slide 8-3, preferably more

02b. Sorting (first half until slide 8-3)
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)
03,
29 Jan-
02 Feb
03a. Sorting (second half, until end)
Focus on the harder content of sorting e-Lecture and sorting Online Quiz,
Sorting Online Quiz (medium)

03b. List ADT: Linked List, Stack ADT (until slide 4-7)
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)
04,
05-09 Feb
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)
05,
12-16 Feb
No Lecture on Thursday (CNY Reunion Dinner) :O
That lecture slot will be converted into Steven's consultation slot @ LT15
Reserved for ~20+ non-Chinese sounding names in CS2040C IVLE class roster

No Lecture on Friday (CNY PH Day 1)

Happy Valentine's Day (Wed) and
Happy CNY (Fri-Sat) of this Week 05
06,
19-23 Feb
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 01-04 review,
Kattis problems discussed:
greedilyincreasing (cpp/growing list/vector),
synchronizinglists (sort/binary search/re-mapping),
server (FIFO/queue/or just on-the-fly computation)

06b. Midterm Test (15%)
During our Friday lecture time (5.05-6.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:
CS2040C-2017-18-S1-midterm-medium.pdf (PS: 22 Sep 2017 was a Friday).
Recess Week, 24 Feb-04 Mar 2018
We can take a break (again :O) this week :)
But if possible, read Hash Table and BST e-Lecture slides by yourself first...
07,
05-09 Mar
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)
08,
12-16 Mar
08a. Table ADT part 2: Binary Search Tree
C++ STLs: set, map, multiset, multimap,
Kattis problem discussed:
baconeggsandspam (assume n = 5 000 customers)

08b. Adelson-Velskii 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
09,
19-23 Mar
09a. Graph Data Structures + Simple Applications
CS1231 happens to be not a pre-req of CS2040C,
so I will play safe by reviewing a bit of CS1231 (graph topic) first,
Graph DS Online Quiz (medium),
No built-in C++ STL container,
see ch2_07_graph_ds.cpp in ch2.zip of CPbook website,
Kattis problem discussed:
flyingsafely (for a 30s jaw-dropping moment)

09b. Graph Traversal: DFS/BFS + Simple Applications
DFS/BFS Online Quiz (easy),
No built-in 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, 9am-2pm @ 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.00am-09.58am, classy (sort, string parsing, 'encode'),
10.03am-10.51am, throwns (stack, int hash/wrap around),
11.00am-11.42am, rationalsequence2 (binary heap (tree) path indexing, stack/LIFO),
11.53am-12.50pm, bard (Table ADT or 2D array; loops),
01.00pm-01.45pm, wheresmyinternet (graph DS+traversal, connected components).
10,
26-30 Mar
10a. Graph Traversal continued (just slide 7)
(we skip slide 8-12, 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

11,
02-06 Apr
11a. Single-Source Shortest Paths (SSSP) Problem: Bellman Ford's, BFS
No built-in 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, 7-9pm SGT
Venue: PL1-2-3-4-5-6 :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
12,
09-13 Apr
12a. SSSP continued: Dijkstra's (original version+implementation)
Kattis problem discussed:
shortestpath1 (that Dijkstra's implementation is easy)
No built-in 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...
13,
16-20 Apr
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
Study Week, 21-27 Apr 2018
Make up (+Remedial) PE on Tue, 24 Apr 2018, 10am-12pm 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!):
CS2010-2011-12-S1-WQ2-medium.pdf, CS2010-2012-13-S1-WQ2-medium.pdf, CS2010-2013-14-S1-WQ2-medium.pdf, CS2010-2014-15-S1-WQ2-medium.pdf, CS2010-2015-16-S1-WQ2-medium.pdf.
Final Assessment Past Papers (from other relevant modules, notice that the syllabus have changed!):
CS2010-2011-12-S1-final.pdf, CS2010-2012-13-S1-final.pdf, CS2010-2013-14-S1-final.pdf, CS2010-2014-15-S1-final.pdf, CS2010-2015-16-S1-final.pdf.
Final Assessment Past Papers:
CS2040C-2017-18-S1-final.pdf.
Final Assessment (40%)
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....

Partial Class Roster

Steven uses a small-scale 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).

  1. I Say Hi: Given to first 7 students who reply Steven's welcome email -- (sent on Wed, 03 Jan 2018); Any early feedback will help Steven in refining the preparation of the second iteration of this module --- First 7 email replies are received by 08 Jan 2018
  2. Kiasu (#): Given to the first 7 students who solve all subtasks of PS0, albeit that it is 'optional' and 'not graded'
  3. Balance Master (#): Given to the first 7 students who solve all subtasks of PS1, the first graded PS of CS2040C, including that 0.5-point subtask C
  4. PS1 Marksman (#): Given to the first 7 (eventually only 2) students who can solve all PS1 subtasks with just one submission each
  5. Guessing Master (#): Given to the first 7 students who solve all subtasks of PS2, including that 0.5-point subtask D
  6. PS2 Marksman (#): Given to the first 7 students who can solve all PS2 subtasks with just one submission each
  7. Potential TA: Given to top 8 (got two joint-7s) highest scorers in the Midterm Test: You survived all those intellectual challenges...
  8. Scheduling Master (#): Given to the first 7 students who solve all subtasks of PS3, including that 0-point subtask D
  9. PS3 Marksman (#): Given to nobody :(.... nobody can solve all PS3 subtasks with just one submission each
  10. Naming Master (#): Given to the first 7 students who solve all subtasks of PS4, including that 0-point subtask C and D
  11. PS4 Marksman (#): Given to the first 7 (eventually only 1) students who can solve all PS4 subtasks with just one submission each
  12. Taxi Driver (#): Given to the first 7 students who solve all subtasks of PS5
  13. Competitive Programmer to be (#): Given to the first 7 (eventually only 5) students who can solve all PE subtasks under that VERY stressful 1h.15m time limit and mostly with slow/missing Mooshak Online Judge... Not many students are expected to be able to do so...
  14. 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 CS2040C final Online Quiz using machine: VisuAlgo (before the actual Final Assessment set by a human)
  15. PS5 Marksman (#): Given to the first 7 (eventually only 4) students who can solve all PS5 subtasks with just one submission each
  16. Nowhere to Hide (Reason): Given to students who already remembered by Steven; These students can choose to hide their matric cards during CS2040C official assessments and Steven will allow them to do so; PS: It will be very hard to remember all ~173 names for this S2 version - tracking stopped on Monday, 23 April 2018
  17. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 200.0 Kattis points or higher at some point during the execution of CS2040C in S2 AY 2017/18 - tracking stopped on Monday, 23 April 2018 (submitting all my AC demo code will only give you about ~50.0 free Kattis points so you must have done a lot more extra homework than necessary; PS: This is my account)
Student Name