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)
Sorting Online Quiz (medium), C++ STL algorithm
Focus on the harder content of sorting e-Lecture and sorting Online Quiz

PS: Hari Raya Haji, Fri, 01 Sep 2017
No Friday class
04,
04-08 Sep
04a. List ADT: Linked List
Linked List Online Quiz (easy), C++ STLs: list
Focus on the harder content of SLL; can already touch Stack ADT in future lecture 4a


04b. Stack, Queue, Deque ADTs: Linked List variants
Linked List Online Quiz (medium), C++ STLs: stack, queue, deque
Focus on Stack, Queue, DLL, Deque and a few other small technicalities of Linked List
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
Preparation for Midterm Test tomorrow
Up to Week 06 T04, i.e. Priority Queue
Review of simple proofs
Kattis problems discussed: TBA


06b. Midterm Test (15%)
During our Friday lecture time
Before recess week, to avoid fighting with other modules on Week 07
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), C++ STLs: unordered_set, unordered_map

07b. More Hashing
Hash Table Online Quiz (medium), C++ STLs: unordered_multiset, unordered_multimap
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), AVLDemo.cpp, C++ STLs: set, multiset, map, multimap
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

09b. Graph Traversal: Depth-First Search and Breadth-First Search + Simple Applications
DFS/BFS Online Quiz (easy), DFSBFSDemo.cpp, No built-in C++ STL algorithm
10,
23-27 Oct
10a. Graph Traversal continued
DFS/BFS Online Quiz (medium)

10b. Single-Source Shortest Paths (SSSP) Problem: Bellman Ford's, BFS
SSSP Online Quiz (easy), BellmanFordDemo.cpp, No built-in C++ STL algorithm
11,
30 Oct-
03 Nov
11a. SSSP continued: Dijkstra's (2 versions), On Tree, On DAG
SSSP Online Quiz (medium), DijkstraDemo.cpp, No built-in C++ STL algorithm

11b. Practical Exam (9%)
Timing: During our 12.05-1.25pm (80m) lecture slot
Venue: Likely COM1-B-PL2 (capacity 46)
We can do this as current class size (41) is ≤ 46

12,
06-10 Nov
12a. Application 2 - Trees and Graphs
Steven will depart to ACM ICPC Jakarta 2017, 10-11-12-13 Nov 2017

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 concepts,
Floyd Warshall's/APSP,
Final Preparation,
Class Photo,
(Participation Marks Given, 3%)
tut11.pdf (TBA), tut11-ans.pdf (TBA)

13b. Application 3 - Mix and Match, Last Lecture
Study Week, 18-24 Nov 2017
Consultation Slots: TBA
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: TBA

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 highest scorers in the Midterm Test: you survived all those intellectual challenges...
  9. [PS3-to-be-renamed] Master (#): Given to the first 7 students who solve all subtasks of PS3
  10. [PS4-to-be-renamed] Master (#): Given to the first 7 students who solve all subtasks of PS4
  11. [PS5-to-be-renamed] Master (#): Given to the first 7 students who solve all subtasks of PS5
  12. 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