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=88+??/173)
    > 50%??%
    Aug-Dec 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, 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 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 are highlighted with khaki color, current week is highlighted with light green color, 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
HashTableDemo.cpp (TBA),
Kattis problem discussed: TBA (reason)

07b. More Hashing
Hash Table Online Quiz,
C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap
Kattis problem discussed: cd (reason)
08,
12-16 Mar
08a. Table ADT part 2: Binary Search Tree
BSTDemo.cpp
Kattis problem discussed: TBA (reason)

08b. Adelson-Velskii Landis (AVL) Tree
BST Online Quiz (medium, including AVL),
C++ STLs: set, map, multiset, multimap,
AVLDemo.cpp,
Kattis problem discussed: compoundwords (reason)
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

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,


09c. We are more likely to use make up Lecture slot
on Saturday, 24 March 2018, 5-6.30pm @ LT15 due to
Good Friday public holiday next week so that
I can slow down the discussion of graph topics...

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

No Lecture on Friday

Good Friday followed by Easter Sunday this Week

11,
02-06 Apr
11a. 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

11b. Application 2 - Tables/Trees (Heap/bBST)/Graphs
Mock Practical Exam :O:
Kattis problems discussed (will be changed, this is S1 list): kitten, wheresmyinternet, grid


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)
Open book (no restriction)
We will use strict PE setup (no public Internet access)
There will be two?? tasks, based on what we have discussed in the past 11 weeks
12,
09-13 Apr
12a. 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

12b. Application 3 - 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: 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: TBA
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 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. PS3 Marksman (#): Given to the first 7 students who 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 students who can solve all PS4 subtasks with just one submission each
  12. Competitive Programmer to be: Given to the first 7 students who can solve all PE subtasks
  13. Taxi Driver (#): Given to the first 7 students who solve all subtasks of PS5
  14. PS5 Marksman (#): Given to the first 7 students who can solve all PS5 subtasks with just one submission each
  15. 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)
  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
  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 (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