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

  1. Steven has taught similar modules: CS2020 once (2011), CS2010 six times (2011-2016), and CS1020E once (2016).
  2. Teaching staffs:
    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used very extensively in this module.

    Tutorial Teaching Assistant (2 tutorial sessions @ COM1-0230, every Monday, 14-15 or 15-16):

    1. Ranald Lam Yun Shao (TG1 and TG2, plus Mon 9-10 consultation slot at ACM ICPC Lab, COM1-02-15)

    Laboratory Teaching Assistant (2 laboratory sessions @ COM1-B112, every Friday 09-10 or 10-11):

    1. Hoang Duong (LG1 and LG2)
  3. Have you passed (or exempted from) CS1010? You have to...
  4. Have you passed (or exempted from) CS1231? 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 (small) parts of CS1231 in the middle of CS2040C.
  5. 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.
Q: Will this module be graded using Bell curve?
A: If there are > 40 students in this expected smaller class in S1, I will have to use Bell curve system :O... With 36 students (as of 13 August 2017), I say that a weaker form of Bell curve system can be used.
Q: I am from CS1010S/other modules that do not use C++, should I pick up C++ on my own during this mid May-end July holiday?
A: Yes, that is a good idea. We will only review basic C++ in the first few weeks of this module.
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 ~2500+ problems in that book 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 freshmen 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.

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.

News

Date News

Lesson Plan

Week Lecture, 2x1.5 hours/week
Every Thursday 16-17.30 and
Every Friday 12-13.30
from Wk01
Venue: COM1-0212 (SR3)
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
14 Aug 		Note 1: Steven visited Tehran, Iran for IOI 2017 (27 Jul-05 Aug 2017)
Note 2: National Day, Wed, 09 Aug 2017

Not started, but please revise
your CS1010 & CS1231 (if you have took this module)
01,
14-18 Aug 		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
02,
21-25 Aug 		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 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,
28 Aug-
01 Sep 		03a. Sorting (second half)
Focus on the harder content of sorting e-Lecture and sorting Online Quiz
Sorting Online Quiz (medium),
C++ STL algorithm
PS: Hari Raya Haji, Fri, 01 Sep 2017
No Friday class
04,
04-08 Sep 		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
05,
11-15 Sep 		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
06,
18-22 Sep 		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)
Recess Week, 23 Sep-01 Oct 2017
We can take a break this week :)
07,
02-06 Oct 		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,
09-13 Oct 		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,
16-20 Oct 		PS: Deepavali, 18 Oct 2017 (Wed)

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,
23-27 Oct 		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,
30 Oct-
03 Nov 		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 (9%)
Timing: During our 12.00-1.30pm (90m) lecture slot
Venue: COM1-B-PL2 (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
12,
06-10 Nov 		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, 10-11-12-13 Nov 2017
13,
13-17 Nov 		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, tut11-ans.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...
Study Week, 18-24 Nov 2017
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 (40%)
Date and Time: Wed, 06 Dec 2017, EV
Venue: COM1-02-06 (SR1)
This year paper (S1 AY 2017/18) can be seen at IVLE Workbin.

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. Round (2A/3A): Given to (senior) students who appear after CORS Round 2A, bringing the class size from the tiny 17 to a respectable 38, then for a few more in 3A (peak = 42 students; final = 37 students)
  2. I Say Hi: Given to students who reply Steven's second welcome email -- survey about CS background (sent on Sunday, 13 August 2017, 5.40pm); It will help Steven in planning the first iteration of this module (closed after the first lecture)
  3. In FB: Given to students who are already in CS2040C FB group (closed after tutorial 01)
  4. In VisuAlgo: Given to students who already have trackable VisuAlgo account (closed after tutorial 01)
  5. Kiasu (#): Given to the first 7 students who solve all subtasks of PS0, albeit that it is 'optional' and 'not graded'
  6. 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
  7. Guessing Master (#): Given to the first 7 students who solve all subtasks of PS2, including that 0-point subtask D
  8. Potential TA: Given to top 7 6 highest scorers in the Midterm Test who actually scored greater than 80 points: you survived all those intellectual challenges...
  9. Scheduling Master (#): Given to the first 7 students who solve all subtasks of PS3, including that 0-point subtask D
  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 student who solves 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
Student Name