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, binary heaps, hash tables, binary search trees, and graphs), searching and sorting algorithms, basic analysis of algorithms, and very basic object-oriented programming concepts (more details of OOP are in CS2030).
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.
Steven teaches CS2040C (NOT CS2040 — contact Dr Chong Ket Fah nor CS2040S — contact Dr Soh Soon Hong, Harold) in S1 AY19/20 (Aug-Nov 2019). Steven already had enough experiences teaching CS2040/C module in previous 2 AYs (4x :O; 3 very successful, 1 "average"). There will only be a few local changes for Aug-Nov 2019 edition.
The max number of students for S1 AY19/20 (Aug-Nov 2019) is set at most 200 @ ModReg, but we are realistically looking at just ~90 students. This number is (much) higher than "only" 37 students in S1 AY 17/18 (2 AYs ago) and also a bit higher than 73 students in S1 AY18/19 (1 AY ago, taught by Assoc Prof Gary Tan). The students should be minor/second major students, some freshmen from CEG and InfoSec AY19/20 students who are exempted from CS1010 (and a few from AY18/19 :O), a few exchange students, and a few Poly Preparatory Programme students.
Known information as of Friday, 02 August 2019 (71 students), updated on Tuesday, 13 August 2019 (76 students), updated again on Tuesday, 20 August 2019 (91 students officially enrolled according to Luminus class roster):
Some other facts:
Rating (out of 5.0) (SoC avg ~4.1) |
Aug-Dec 19 (n=??/~80?) ??+% |
Jan-May 19 (n=144/269) 54% |
Jun-Aug 18 (n=33/38) 87% |
Jan-May 18 (n=145/173) 84% |
Aug-Dec 17 (n=28/37) 76% |
---|---|---|---|---|---|
Module feedback | Target return to 4.2? | 4.0 ▼ (v large class) | 4.4 ▲ (S1 level) | 4.3 ▼ (large class) | 4.4 (> avg :) |
Module difficulty | Target stay at 4.0? | 4.0 ▼ (easiest) | 4.2 ▲ (Sp Sem) | 4.0 ▼ (easiest) | 4.1 (> avg :O) |
Steven's teaching | Target return to 4.4? | 4.2 ▼ (v large class) | 4.8 ▲ (Thx God :) | 4.5 ▼ (large class) | 4.7 (> avg :) |
Latest info as of 20 Aug 2019, setup for 91 students:
Tutorial Teaching Assistants (6 tutorial sessions + 4 additional consultation (2-hours) sessions, sorted chronologically):
Most tutorial sessions are between Wed lecture and before Thu lectures.
One Friday tutorial session is after both Wed+Thu lectures (so will know some answers already, your choice).
Date, Time | COM1 Room (#Stu/#Cap) | No | Tutor |
---|---|---|---|
2/Tue, 1400-1600 (consultation slot) |
COM1-02-15 (NUS ICPC Lab) |
- | StevenW |
3/Wed, 1400-1600 (consultation slot, after Wed lecture) |
COM1-02-Lobby Area (find Matthew near Steven's LEGO-ified poster) |
- | Matthew |
3/Wed, 1600-1700 | COM1-0120 (14/16) | 09 | Matthew |
4/Thu, 1000-1100 | COM1-0120 (11/16) | 03 | StevenW |
4/Thu, 1100-1200 | COM1-0120 (14/16) | 04 | StevenW |
4/Thu, 1400-1500 | COM1-0120 (13/16) | 07 | KWei Heng |
4/Thu, 1500-1600 | COM1-0120 (12/16) | 08 | KWei Heng |
4/Thu, 1615-1700 + 1745-1830 (consultation slot) |
i3-Aud (Bef/Aft Thu Lecture) |
- | Dr StevenH |
5/Fri, 1000-1200 (consultation slot) |
COM1-02-Lobby Area (find KWei Heng near Steven's LEGO-ified poster) |
- | KWei Heng |
5/Fri, 1200-1300 | COM1-0120 (14/16) | 01 | Matthew |
Latest info as of 20 Aug 2019, setup for 91 students:
Laboratory Teaching Assistants (5 laboratory sessions, sorted chronologically):
All Lab sessions are on Friday.
We will do lots of hands-on (i.e. real coding of various data structures and algorithms) during these lab sessions.
Date, Time | COM1 Room (#Stu/#Cap) | No | Lab TA |
---|---|---|---|
0800-0900 | COM1-0120 (12/19) | 01 | Kane |
1200-1300 | COM1-0120 (16/19) | 05 | Shantanu |
1300-1400 | COM1-0120 (16/19) | 06 | Shantanu |
1400-1500 | COM1-0120 (16/19) | 07 | Aaryam |
1500-1600 | COM1-0120 (16/19) | 08 | Aaryam |
This is what you will learn if you take CS2040/C taught by Steven:
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.
Note: This course registration section will not be prominent from Week 1 of S1 AY19/20 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
Date | News |
---|
The S1 AY19/20 timetable below is still tentative, especially those that are highlighted with pink color.
Week | Lecture, 2+1h/session Every Wed 10am-12pm and Every Thu 5-6pm I3-AUD, from Wk01 |
Tutorial, 1h/session Wed/Thu/Fri 6 slots From Wk03 |
Lab, 1h/session Every Fri 5 slots From Wk03 |
Interesting Problem Set @ Home Every ~Two Weeks ~6++ hours/set From Wk02 |
---|---|---|---|---|
Cells with course material that have not been updated are highlighted with pink color, past classes more than one week ago are hidden so that we can focus on the current and future classes, but you can restore them by clicking 'Show Past' button above, future classes are not highlighted | ||||
-03/-02/-01, Bef Mon, 12 Aug |
Not started, but please revise your CS1010 (Steven assumes that all? of you have taken or exempted from this module/its variants) Register at Kattis, read C++ specific instructions @ Kattis, and solve these optional OJ problems by yourself (CS1010 level): Optional Week -01 (29 Jul-02 Aug) very easy C++/coding challenges: Week -01 (10 'easiest' problems in Kattis system) Optional Week 00 (05-09 Aug) easy C++/coding challenges: Week 00 (another 9 'easy' problems in Kattis system) |
Not Started | Not Started | Not Started |
01, 12-16 Aug |
Hari Raya Haji is on Sun, 11 Aug 2019 The following Mon, 12 Aug 2019 is a Public Holiday No CS2040C class is affected. 01a. Course Admin, (Re-)Introduction to C++ Setting the tone for a flipped classroom module VisuAlgo + this Private IVLE + Kattis (NUS) + Kattis (open) Basic C/C++ review/new feature introduction Kattis problems discussed: statistics (revise I/O, control flow: repetition, implicit selection) 01b. (Re-)Introduction to C++ (continued) Kattis problems discussed: quickbrownfox (1D Boolean array; duplicates possible; NEW: C++ STL vector, C++ class (overkill actually)), Reminder: Read old CS1020/E lecture note on algorithm analysis before Lecture 02a |
Not Started | Not Started |
Trial PS0 not graded Out: Wed, 14 Aug 19, 18.00pm Showcased during second lecture |
02, 19-23 Aug |
02a. Analysis of Algorithms (old CS1020/E lecture note on this topic will be digitised later) (Kattis) problems discussed: autori (NEW: C++ string, C++ istringstream), filip (NEW for S1 AY19/20; review: function), Live speedtest.cpp demo lineup (NEW: C++ STL sort, reverse), Reminder: Read sorting e-Lecture slides before Lecture 02b At least until slide 8-3, preferably more 02b. Sorting (until slide 8-3) C++ STL algorithm: sort, stable_sort Kattis problems discussed: height (NEW for S1 AY19/20: insertion sort simulation), sortofsorting (NEW: custom comparator, C++ STL stable_sort) Reminder: Read ALL sorting e-Lecture slides before Lecture 03a |
Not Started | Not Started |
Trial PS0 "due": Sat, 24 Aug 19, 07.59am not graded PS1: Sorting-related Problems Out: Sat, 24 Aug 19, 08.00am |
03, 26-30 Aug |
03a. Sorting (until end) Focus on the harder content of sorting e-Lecture SortingDemo.cpp Sorting Online Quiz (medium) 03b. List ADT: (Single) LL (until slide 3-22) Introduction of List ADT and SLL operations C++ STLs: forward_list (an SLL), list (a DLL) SLLDemo.cpp Kattis problems discussed: joinstrings (NEW for S1 AY19/20) |
T01: Introduction, OOP (basic), Live problem solving, Analysis, tut01.pdf (Link TBA) |
L01: Quick Intro, Review demo code so far, focusing on OOP review (List ADT/ListVector) C++ STL (algorithm, vector, string), PS1 Discussion (algorithmic) |
PS1, continued |
04, 02-06 Sep |
04a. Stack/Queue/Deque ADT (DLL) (until end) Focus on Stack, Queue, DLL, Deque Plus a few other LL technicalities C++ STLs: stack, queue, deque (actually not a DLL) Linked List Online Quiz (medium) Kattis problems discussed: thegrandadventure (NEW for S1 AY19/20; NEW: C++ stack and its usage) teque (NEW for S1 19/20, use two deques; NEW: C++ list/deque) 04b. Priority Queue (PQ) ADT: Binary Heap (until slide 6) Review of basic ideas of PQ ADT and basic Binary Heap structure C++ STL: priority_queue, partial_sort, See priority_queue.cpp at GitHub repo of CPbook website |
T02: Sorting Application(s), Sorting, mini experiment, ADT Introduction, List ADT (array/vector), PS1 Discussion tut02.pdf (Link TBA) |
L02: Quick Re-introduction, VA OQ demo (sorting), Hands-on: ??? (something sorting) |
PS1 Due: Sat, 07 Sep 19, 07.59am (3%) PS2: List-related Problems Out: Sat, 07 Sep 19, 08.00am |
05, 09-13 Sep |
05a. Priority Queue (PQ) (until end) BinaryHeapDemo.cpp Binary Heap Online Quiz (medium) Kattis problems discussed: numbertree (for a short wow moment) froshweek (for another wow moment) 05b. Mock Practical Exam 1 - C++/Arrays/Vectors/Sorting Kattis problems discussed: TBA |
T03: List ADT, Linked List Review, Stack/Queue/Deque ADT, Applications, PS2 Discussion tut03.pdf (Link TBA) |
L03: PS1 Quick Debrief, C++ STL (list/stack/queue/deque), , VA OQ demo (list) PS2 Discussion (algorithmic) Hands-on: ??? (something LL) |
PS2, continued |
06, 16-20 Sep |
06a. Practical Exam 1 (7%) During our Wed lecture time (10.05am-11.35am, 90m) Material: Up to Week 03 L03a + Week 04 D02+T02, i.e. Basic C++ and Sorting only Venue: Our lecture venue (I3-AUD) Open book, bring your own laptop :O 06b. Midterm Quiz (8%) During our Thu lecture time (17.05pm-17.35pm, 30m) Material: Up to Week 04 L04a + Week 05 D03+T03, i.e. Basic C++, Sorting, and Linked List Venue: Our lecture venue (I3-AUD) Open book (no restriction), theory only :O Format: T/F, MCQ, and/or Short Answers Past Papers (different format): CS2040C-2017-18-S1-midterm-medium.pdf, CS2040C-2017-18-S2-midterm-medium.pdf, CS2040-2017-18-S4-midterm-hard.pdf, CS2040C-2018-19-S1-midterm-medium.pdf (Prof Gary), CS2040C-2018-19-S2-midterm-medium.pdf, |
T04: Midterm Test Preparation or Solutions (depends on timing), Basic PQ ADT tut04.pdf (Link TBA) |
L04: PE1 Upsolve |
PS2 Due: Sat, 21 Sep 19, 07.59am (3%) PS3: PQ/Table-related Problems Out: Sat, 21 Sep 19, 08.00am |
Recess Week, 21-29 Sep 2019 We can take a break (again :O) this week :) But if possible, read Hash Table and BST e-Lecture slides by yourself first... PS: Those who miss midterm test due to VALID reasons (representing NUS for an official event; valid Medical Certificate; bereavement of immediate family member) can take make-up PE1 and/or midterm quiz to be scheduled during recess week |
||||
07, 30 Sep-04 Oct |
07a. Table ADT part 1: Hash Table C++ STLs: unordered_set, unordered_map, unordered_multiset, unordered_multimap Kattis problems discussed: competitivearcadebasketball (NEW for S1 AY19/20), whatdoesthefoxsay (assume there are 10 000 animals; string hashing) 07b. More Hashing See unordered_map_unordered_set.cpp at GitHub repo of CPbook website, HashTableDemo.cpp Hash Table Online Quiz (medium) No Kattis live problem solving as this lecture is a bit technical |
T05: More Binary Heap, More ADT PQ Operations, Midtest Review tut05.pdf (Link TBA) |
L05: PS2 Debrief (short), PS3 Discussion (short), VA OQ demo (heap,hashtable), C++ STL (priority_queue), Max-Min conversion, Hands-on: ??? (something PQ) |
PS3, continued |
08, 07-11 Oct |
08a. Table ADT part 2: Binary Search Tree (until slide 11) C++ STLs: set, map, multiset, multimap, BST Online Quiz (medium), Kattis problem discussed: kattissquest (NEW for S1 AY19/20 ) 08b. Adelson-Velskii Landis (AVL) Tree AVL Tree Online Quiz (medium), See map_set.cpp at GitHub repo of CPbook website, BSTDemo.cpp, AVLDemo.cpp, No Kattis live problem solving as this lecture is a bit technical |
T06: Table ADT 1 - unordered, Hashing concepts, Hash Table issues, tut06.pdf |
L06: C++ STL (unordered_map) (short), C++ STL (unordered_set) (optional), C++ STL (map) (short), C++ STL (multimap, set, multiset) (optional), VA OQ demo (bst,avl) Hands-on: ??? (something Table ADT) |
PS3 Due: Sat, 12 Oct 19, 07.59am (3%) PS4: Table-related Problems Out: Sat, 12 Oct 19, 08.00am |
09, 14-18 Oct |
09a. Graph DS + Applications Graph DS Online Quiz (medium), No built-in C++ STL container, See graph_ds.cpp at GitHub repo of CPbook website, Kattis problem discussed: flyingsafely (for a 30s jaw-dropping moment) 09b. Graph Traversal + Simple Applications (until slide 5-8) DFS/BFS Online Quiz (easy), No built-in C++ STL algorithm, See dfs_cc.cpp, UVa00469.cpp, and bfs.cpp at GitHub repo of CPbook website, Kattis problem discussed: reachableroads (DFS introduction, count #CC) |
T07: Table ADT 2 - ordered, BST/AVL advanced stuffs: Select and Rank, PQ ADT alternative implementation, Comparison with Table ADT 1, unordered vs ordered, tut07.pdf |
L07: PS3 Debrief (short), PS4 Discussion (short), VA OQ demo (graphds) Hands-on: ??? (something graph DS) |
PS4, continued |
10, 21-25 Oct |
10a. Live Solve - PQs/Tables/Trees (Heap/bBST)/Graphs List of selected problems: abinitio (NEW for S1 AY19/20; graph data structures manipulation) builddeps (toposort demo), brexit (happening or not?), conformity (mock PE S2 17/18), detour (?), 10b. Graph Traversal continued (until slide 7-11) (we skip slide 8-12, out of CS2040/C scope) DFS/BFS Online Quiz (medium) Kattis problems discussed: reachableroads (BFS this time, count #CC), countingstars (floodfill, DFS, count #CC), runningmom (AL of strings; DFS; back edge detection) |
T08: Graph DS Review, Graph DS Conversion Exercise, Some Graph Properties Discussion, Graph Modeling exercise 1, DFS/BFS Review tut08.pdf |
L08: VA OQ demo (dfsbfs) Hands-on: ??? (something graph traversal) |
PS4 Due: Sat, 26 Oct 19, 07.59am (3%) PS5: Graph-related Problems Out: Sat, 26 Oct 19, 08.00am |
ICPC Asia Jakarta 2019 Steven will bring a few NUS students to compete in ICPC Asia Jakarta 2019, Fri 25 Oct - Mon, 28 Oct 2019 No CS2040C class is affected. Diwali is on Sun, 27 Oct 2019 The following Mon, 28 Oct 2019 is a Public Holiday No CS2040C class is affected. |
||||
11, 28 Oct-01 Nov |
Lecture plan this week TBC Practical Exam 2 (12%) Timing: ???, ?? Oct 2019, TBA Venue: Likely PL2+PL4, especially if total students ≤ 71 COM1-B-PL2 (capacity 46) COM1-B-PL4 (capacity 25) TBC: COM1-B-PL1 (capacity 44) |
T09: DFS/BFS advanced stuffs, Cycle, Toposort++, (Floodfill/CC), Modeling exercise 2 (time permitting), tut09.pdf |
L09: PS4 Debrief (short), PS5 Discussion (short), PE2 upsolve |
PS5, continued |
12, 04-08 Nov |
12a. Single-Source Shortest Paths (SSSP) Problem: Bellman Ford's, BFS No built-in C++ STL algorithm, See bellman_ford.cpp at GitHub repo of CPbook website, Kattis problem discussed: shortestpath1 (that Bellman Ford's will TLE) knightjump (NEW for S1 AY19/20; BFS demo; implicit graph demo) 12b. SSSP continued: Dijkstra's (original version+implementation) Kattis problem discussed: shortestpath1 (that Dijkstra's implementation is easy) No built-in C++ STL algorithm, See dijkstra.cpp at GitHub repo of CPbook website, SSSP Online Quiz (medium) NUS Online Teaching Feedback System opens this Friday |
T10: Bellman Ford's, BFS, and Original Dijkstra's Review, Modeling exercises 3, Class Photo, tut10.pdf (Participation Marks Given, 3%) |
L10: VA OQ demo (sssp) Tips for OQ preparation (students need to self practice on sssp module), Class Photo (for momento), Hands-on: ???, (something SSSP) PS5 last minute discussion (offline) (Participation Marks Given, 3%) |
PS5 Due: Sat, 09 Nov 19, 07.59am (3%) |
13, 11-15 Nov |
13a. SSSP continued: Modified Dijkstra's, On Tree, On DAG, Final Exam Tips, Last Lecture Kattis problems discussed: shortestpath1 (modified Dijkstra's implementation) flowerytrails (Dijkstra's (any version) and DFS/BFS to traverse the shortest path(s)) Closed with a few minutes of semester summary, followed with review of what can be done better for future iterations... Lecture 13b will be a buffer slot... |
D11: VA Online Quiz (12%) (URL: https://visualgo.net/training, click 'CS2040C Quiz') Time: 30m, 19+1 random hard (may luck be with you) questions All topics in CS2040C Student can do one more random round if the first one is not 19/19 But to prevent abuse, we will only take the latest score :O PS: Steven add a bunch of new Q20 that cannot be prepared by anyone |
T11: Final paper preparation, Class Photo, tut11.pdf |
No more PS |
Study Week, 18-22 Nov 2019 Makeup/remedial Practical Exam, if any, will be during reading week for some students only Venue: TBA Final Assessment Consultations (per request) Final Assessment Past Papers: CS2040C-2017-18-S1-final.pdf, CS2040C-2017-18-S2-final.pdf, CS2040-2017-18-S4-final.pdf, CS2040C-2018-19-S1-final.pdf (Prof Gary), CS2040C-2018-19-S2-final.pdf, NUS Online Teaching Feedback System closes on Friday of Study Week |
||||
Final Assessment (40%) Date and Time: Wed, 04 Dec 2019, 09-11AM Venue: TBA |
Steven uses a small-scale gamification system in his version of CS2040/C 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).
As the class size is big (~90), only students with at least one achievement will be listed below (so the list is not the full class roster).
No | Student Name | Achievements |
---|