CS2040C - Data Structures and Algorithms (C++)

Introduction

This module introduces students to the design and implementation of fundamental data structures and algorithsm. 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 CS2020.

The quota of this class for S1 AY2017/2018 is XX students (TBC, likely just 2 digits). 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... I will update this part once I know more details.

The old CS1020 and CS2010 will still remain in AY2017/2018 (expected smaller sizes) 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.

    Good Quality Tutorial Teaching Assistants (2 is enough for up to 4 tutorial sessions, @ COM1-0230, every Monday, 14-15, 15-16, 16-17, or 17-18):

    1. Ranald Lam Yun Shao (TG?+TG?)
    2. Li Er Lu Lawrence (TG?+TG?)

    Laboratory Teaching Assistants (2 is enough for up to 4 laboratory sessions @ COM1-0120/PL6, every Tuesday, 10-11, 11-12, 12-13, or 13-14):

    1. Boo Kai Hsien (LG?+LG?)
    2. Hoang Duong (LG?+LG?)
  3. Have you passed (or exempted from) CS1010? You have to...
  4. Have you passed (or exempted from) CS1231? It is very 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 or 12, nearing the end of the semester, after sufficient practices in Lab Demos and PSes (TBC).
Q: Will this module be graded using Bell curve?
A: If there are > 40 students (most likely) in this expected smaller class in S1, I will have to use Bell curve system :O...
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 2000+ 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

The CS2040C syllabus will be delivered over 13 weeks.
The weekly lesson plan of Week X is typically as follows:

  1. Give yourself about 2-hours/week to self-study as much as you can from VisuAlgo about the designated topic and attempt the e-Lecture questions first (flipped classroom),
  2. Attempt and then actively participate on one 1-hour (effective 45 minutes) tutorial slot of past week X-1 topic on Monday to improve student's understanding of CS2040C material,
  3. Listen and participate during one 1-hour (effective 45 minutes) demonstration lab session of past week X-1 topic on Tuesday to improve student's "code comprehension" skills.
  4. During the 2x1.5-hour = 3 hours in-class "lecture" on Thursday and Friday, we will roughly do: 5m (buffer) + 40m (fast in class review of the more difficult parts of the designated topics) + 5m (break) + 30m (applications) + 10m (buffer),
  5. Attempt a ~two-weeks Problem Set (PS), approximately 3 hours of work per week on average.

Then, repeat this throughout the semester :).

Week Lecture, 2x1.5 hours/week
Every Thursday 16-17.30 and
Every Friday 12-13.30
from Wk01
Venue: LT19
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
PS: 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 + this Private IVLE + Mooshak (TBC)

01b. Introduction to C++.pdf
C++ STL vector
02,
21-25 Aug
02a. Analysis of Algorithms (Basic)
Analysis of simple C++ programs that use simple arrays/vectors


02b. Sorting (first half)
Sorting Online Quiz (easy), C++ STL algorithm
03,
28 Aug-
01 Sep
03a. Sorting (second half)
Sorting Online Quiz (medium), C++ STL algorithm

PS1: Hari Raya Haji, Fri, 01 Sep 2017
No Friday class

PS2: NUS ACM ICPC Selection Contest, Sat, 02 Sep 2017
04,
04-08 Sep
04a. List ADT: Linked List
Linked List Online Quiz (easy), C++ STLs: list

04b. Stack, Queue, Deque ADTs: Linked List variants
Linked List Online Quiz (medium), C++ STLs: stack, queue, deque
05,
11-15 Sep
05a. Review of Trees, Graphs, Simple Proofs
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), BinaryHeapDemo.java, C++ STL priority_queue
06,
18-22 Sep
06a. Application 1 - Arrays/Vectors+Sorting+Lists
Preparation for Midterm Test, up to Week 05 Lab Demo

06b. Midterm Test (15% TBC)
Before recess week, to avoid fighting with other modules on Week 07
PS2 due: Thu, 14 Sep 2017, 4.00pm (2% TBC)

PS3: PQ ADT-TBA
Released: Fri, 15 Sep 2017, 1.30pm
Recess Week, 23 Sep-01 Oct 2017
Consultation Slots: TBA
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. Buffer Slot
12,
06-10 Nov
12a. Practical Exam (10%)
Timing TBC


12b. 99% Cancelled
Steven is likely away for ACM ICPC Jakarta 2017, 10-11-12-13 Nov 2017
13,
13-17 Nov
13a. Application 2 - Trees and Graphs
Steven should be back from ACM ICPC Jakarta 2017, 10-11-12-13 Nov 2017

13b. Application 3 - Mix and Match, Last Lecture
Study Week, 18-24 Nov 2017
Consultation Slots: TBA
Final Assessment (40%)
Date and Time: TBA
Venue: TBA

Class Roster

Content TBA as I do not know the students who will take CS2040C in Sem1 AY2017/2018 yet.