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.

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

  1. Steven has just taught the first version of CS2040/C in S1 of this AY2017/18, seemingly "okay", but we will see how S1 students have to say about the flipped classroom, machine-teach-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.00)
    Jan-May 18
    (n=~90??/~150??)
    > 50%??%
    Aug-Nov 17
    (n=25+?/37)
    65%+?
    Module feedback 4.000 target (will be revised after seeing S1 score) 4.000? (hopefully 'okay-ish', 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 'okay-ish', 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:00-11:00 COM1-0203 (20) 05 Ranald Lam Yun Shao
    Tue, 16:00-17:00 COM1-0203 (20) 06 Ranald Lam Yun Shao (those staying outside campus shall choose 06 than 07 to avoid evening rush hour)
    Tue, 17:00-18:00 COM1-0203 (20) 07 Ranald Lam Yun Shao (late afternoon timing, preferably taken by those staying in campus :O)
    Thu, 09:00-10:00 COM1-0201 (20) 01A TBC (if low enrollment due to potential clash with CS2100 lecture, 1A+1B will be 'merged')
    Thu, 09:00-10:00 COM1-0203 (20) 01B TBC (must be different than 01A, same timing, but and depends on enrollment)
    Thu, 10:00-11:00 COM1-0201 (20) 02 TBC
    Thu, 11:00-12:00 COM1-0201 (20) 03 TBC
    Thu, 12:00-13:00 COM1-0201 (20) 04 TBC
    1. Ranald Lam Yun Shao (3 groups on Tuesday, cannot do 01A/01B, clash with his own module: CS2100 lecture)
    2. Melvin Tan Jun Keong (2 groups, timing TBC)
    3. I need one more Tutorial TA, hunting...; those with A-/A/A+ in CS2010/2020/2040/C, please come forward and apply

    Laboratory Teaching Assistants (7 laboratory sessions):

    Date and Time (sort key)
    (no 10:00-11:00 slot)
    Room (Capacity) Group Number
    (group number
    is not sequential
    )
    Lab TA
    Fri, 09:00-10:00 COM1-B112 (35) 01 Boo Kai Hsien (99%), early morning class, preferably for those staying in campus :O
    Fri, 11:00-12:00 COM1-B110 (20) 03 Boo Kai Hsien (99%)
    Fri, 11:00-12:00 COM1-0120 (20) 06 TBC (parallel lab, same timing with 03, different Lab TA!)
    Fri, 12:00-13:00 COM1-B110 (20) 04 TBC
    Fri, 12:00-13:00 COM1-0120 (20) 07 TBC (parallel lab, same timing with 04, different Lab TA!)
    Fri, 13:00-14:00 COM1-B110 (20) 05 TBC
    Fri, 14:00-15:00 COM1-B110 (20) 02 TBC
    1. Hoang Duong (likely 2 groups; need replacement for Week05/CNY week)
    2. Boo Kai Hsien (2 groups for now)
    3. Sidhant Bansal (likely 2 groups, TBC)

    Btw, this is a starting NUSMODS link for you to plan your S2 (around) CS2040C :O.

  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 (TBC), 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 expected to be large (~150).
Q: Will this module be graded using Bell curve?
A: For S2 version (~150 students), obviously yes...
Q: I am from CS1010S/other modules that do not use C++, should I pick up C++ on my own during this December 2017?
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.
Q: What Integrated Development Environment (IDE) that we will use in CS2040C?
A: The choice of IDE is entirely up to you.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my Competitive Programming book, the 3.17th 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 ~2700+ 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 debateable) 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 as CS1020/2010 are closed). The first experiment was conducted with 37 students in S1 and Steven has a feeling that 'it works' (this statement shall be updated after seeing CS2040C S1 official teaching feedback result by mid Jan 2018).
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. 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%
  2. Changing PS deadline to Saturday morning instead of Thursday evening to give slightly more time for students to complete them
  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 many 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. All others are planned to be kept constant as in S1 version as Steven wants to know whether flipped classroom strategy that 'seems to work in S1 with smaller class' can be scaled up to ~150 students (4x bigger)...

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.

News

Date News

Lesson Plan

Week Lecture, 2x1.5 hours/week
Every Thursday 17.00-18.30 and
Every Friday 17.00-18.30 (TBC)
from Wk01
Venue: LT15
Cells with course material that have not been updated are highlighted with pink color, past classes are highlighted with khaki color, current week is highlighted with light green color, future classes are not highlighted
0, Bef
18 Jan
Not started, but please revise
your CS1010 & CS1231
(Steven assumes that majority of you
have taken this module in S1 AY2017/18)
01,
15-19 Jan
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
02,
22-26 Jan
02a. Analysis of Algorithms
Kattis problems discussed: (several previous problems), register
Reminder: Read sorting e-Lecture 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
03,
29 Jan-
02 Feb
03a. Sorting (second half)
Focus on the harder content of sorting e-Lecture and sorting Online Quiz
Sorting Online Quiz (medium),
C++ STL algorithm

03b. Application 1 - Arrays/Vectors+Sorting
Kattis problems discussed: TBA, TBA
04,
05-09 Feb
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
05,
12-16 Feb
05a. Review of Graphs and Trees (until 6-4)
CS1231 happens to be not a pre-req 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 (Fri-Sat) of this Week 05
06,
19-23 Feb
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)
Recess Week, 24 Feb-04 Mar 2018
We can take a break this week :)
07,
05-09 Mar
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
08,
12-16 Mar
08a. Table ADT part 2: Binary Search Tree
BST Online Quiz (easy, BST only),
BSTDemo.cpp


08b. Adelson-Velskii Landis (AVL) Tree
BST Online Quiz (medium, including AVL),
C++ STLs: set, map, multiset, multimap,
AVLDemo.cpp,
Kattis problem discussed: compoundwords
09,
19-23 Mar
09a. Graph Data Structures + Simple Applications
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

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,
10,
26-30 Mar
10a. Graph Traversal continued
(we skip slide 8-12, out of CS2040C scope)
DFS/BFS Online Quiz (medium)
Kattis problems discussed: reachableroads, runningmom

10b. Single-Source Shortest Paths (SSSP) Problem: Bellman Ford's, BFS
SSSP Online Quiz (easy),
No built-in C++ STL algorithm,
see ch4_06_bellman_ford.cpp in ch4.zip of CPbook website,
Kattis problem discussed: hidingplaces
11,
02-06 Apr
11a. SSSP continued: Dijkstra's (2 versions), On Tree, On DAG
SSSP Online Quiz (medium),
No built-in 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
12,
09-13 Apr
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...
13,
16-20 Apr
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
Study Week, 21-27 Apr 2018
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: TBA
Venue: TBA
This year paper (S2 AY 2017/18) is OBVIOUSLY NOT AVAILABLE YET :O....

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)

  1. I Say Hi: Given to students who reply Steven's welcome email -- survey about CS background (sent on ???, ?? January 2018??); It will help Steven in refining the second iteration of this module (closed after the first lecture)
  2. In FB: Given to students who are already in CS2040C FB group (closed after tutorial 01)
  3. In VisuAlgo: Given to students who already have trackable VisuAlgo account (closed after tutorial 01)
  4. Kiasu (#): Given to the first 7 students who solve all subtasks of PS0, albeit that it is 'optional' and 'not graded'
  5. Balance Master (#): Given to the first 7 students who solve all subtasks of PS1, the first graded PS of CS2040C, including that 0-point subtask C
  6. Guessing Master (#): Given to the first 7 students who solve all subtasks of PS2, including that 0-point subtask D
  7. Potential TA: Given to top 7 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. Naming Master (#): Given to the first 7 students who solve all subtasks of PS4, including that 0-point subtask C and D
  10. PS4 Marksman (#): Given to the first 7 students who can solve all PS4 subtasks with just one submission each
  11. Competitive Programmer to be: Given to the first student who solves all PE subtasks
  12. Taxi Driver (#): Given to the first 7 students who solve all subtasks of PS5
  13. PS5 Marksman (#): Given to the first 7 students who can solve all PS5 subtasks with just one submission each
  14. Chow-Yuan-Bin Award (#): Given to the top 7 students who scored the highest (and if ties, by fastest submission time) in CS2040C final online quiz using machine: VisuAlgo (before the actual Final Assessment set by a human)
  15. 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
Student Name