This course introduces students to the design and implementation of fundamental data structures and algorithms. The course 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 course is C++ (as of 2022, we still use C++17, pick up as much as possibly via self-learn from this site: learncpp.com).
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 Prof Roger Zimmermann and A/Prof Tan Sun Teck — nor CS2040S — contact Dr Chong Ket Fah) in S1 AY 2022/23 (Aug-Nov 2022). Steven already had enough experiences teaching CS2040/C/S course in previous half decade (many times, all course ratings are above NUS SoC average). This S1, there is a major change where the majority of 200-about 50 pax = 150 other pax of Computer Engineering (CEG) students from August 2021 intake will take CS2040C in their sem 3 (S1 AY 2022/23 - this semester).
There are a few exchange students as exchange programme has restarted in 2022.
Some other facts:
| Rating (out of 5.0) |
Aug-Nov 22 (n=162/206) 79% ▲ |
Jan-May 22 (n=101/131) 77% ▲ |
Aug-Dec 21 (n=49/69) 71% ▼ |
Jan-May 21 (n=158/253) 62% ▲ |
Aug-Dec 20 (n=60/115) 52% ▼ |
Aug-Dec 19 (n=56/96) 58% ▲ |
|---|---|---|---|---|---|---|
| Course feedback (SoC avg ~3.9) | 4.2 == (more than target) | 4.2 == (+Alan) | 4.2 == | 4.2 ▲ (+Alan) | 3.8 ▼ (C-19+IOI 20) | 4.0 == |
| Course difficulty (SoC avg ~3.8) | 4.3 ▲ (wah, increases) | 4.2 == (hm, still high) | 4.2 ▲ | 3.9 ▼ (easiest) | 4.6 ▲ (C-19+IOI 20) | 4.2 ▲ |
| Steven's teaching (SoC avg ~4.2) | 4.5 ▲ (more than target) | 4.3 ▼ (+Alan) | 4.5 ▲ | 4.4 ▲ (+Alan) | 4.3 ▼ (C-19+IOI 20) | 4.4 ▲ |
| Date, Time | Live Session (Venue) (#Stu/#Cap) | No | Tutor |
|---|---|---|---|
| 1/Mon, 1000-1200 | COM1-0120 (PL6) (25/28) | 02 | ayaze |
| 1/Mon, 1200-1400 | COM1-0120 (PL6) (28/28...) | 03 | dZhei |
| 1/Mon, 1400-1600 | COM1-0120 (PL6) (29/28...) | 04 | RezwanArefin01 |
| 1/Mon, 1600-1800 | COM1-0120 (PL6) (12/28) | 05 | T1duS |
| 2/Tue, 1000-1200 | COM1-0120 (PL6) (26/28) | 06 | rama_pang |
| 2/Tue, 1200-1400 | COM1-0120 (PL6) (29/28...) | 07 | athin |
| 2/Tue, 1400-1600 | COM1-0120 (PL6) (28/28) | 08 | Berted |
| 2/Tue, 1600-1800 | COM1-0120 (PL6) (29/28...) | 09 | jialin |
| 3/Wed, 2000-2100 (1h consultation slot) |
Zoom Recurring Link (free and easy) | - | jialin |
| 3/Wed, 2200-2300 (1h consultation slot) |
Class Discord Study Room 2 - T1duS (online, free and easy) | - | T1duS |
| 4/Thu, 2000-2100 (1h consultation slot) |
Zoom Recurring Link (free and easy) | - | RezwanArefin01 |
| 4/Thu, 2100-2200 (1h consultation slot) |
Class Discord Study Room 1 - dZhei (online, free and easy) | - | dZhei |
| 5/Fri, 1000-1100 (1h consultation slot) |
Zoom Recurring Link (free and easy) | - | ayaze |
| 5/Fri, 1300-1400 (1h consultation slot) |
NUS ICPC lab COM1-02-15 (onsite, free and easy) | - | Berted |
| 5/Fri, 1500-1700 (the only 2h consultation slot) |
Zoom Recurring Link (free and easy) | - | athin |
| 5/Fri, 2000-2100 (1h consultation slot) |
Zoom Recurring Link (free and easy, PS deadlines last minute help) | - | rama_pang |
List of TAs:
This is what you will learn if you take CS2040/C/S taught by Steven:
If you have any important questions regarding this course, 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 AY 2022/23 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
| Date | News |
|---|
| Week | Tutorial+Lab Combo | Lecture | Interesting Problem Set |
|---|---|---|---|
| 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 | |||
|
-02/-01, Bef Mon, 08 Aug |
Not Started |
Not started, but please revise your CS1010 (Steven assumes that all? of you have taken or exempted from this course/its variants) Register at Kattis (use full name as in Matric card), read C++ specific instructions @ Kattis, pick up basic C++ by yourself via learncpp.com, and solve the selected optional Online Judge (OJ) Problem Set 0 (PS0) by yourself (CS1010 level): (solving many 'trivial problems' from this set ---trackable by Steven, indirectly tells Steven about your CS1010 rough grade) |
PS0: Easy C++/coding challenges (18 Jul-10 Aug) obviously not graded |
|
01, 08-12 Aug |
Not Started |
Singapore National Day on Tue, 09 August 2022 CS2040C first lecture is not affected But Steven is in Yogyakarta, Indonesia, for IOI 2022 Thus both Lectures on Week 01 were online but live 01a. Course Admin, (Re-)Introduction to C++ Setting the tone for a flipped classroom plus mostly ONSITE course PS: *Except* for Wed, 10 Aug 2022 AM, as Steven is physically at Yogyakarta this day VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open) Basic C/C++ review/new feature introduction Kattis problem(s) discussed today: socialdistancing2 (introducing C++ std::vector/Boolean array) 01b. (Re-)Introduction to C++ (continued) Kattis problem(s) discussed today: vectorfunctions (more about C++ functions (const, &) and std::vector) rankproblem (a new List ADT task; iota; std::vector insert and erase operations) Reminder: Read summary on algorithm analysis (Slide 6 to 6-11) before Lecture 02a |
PS0 Due: Wed, 10 Aug 22, 11.59am (0%) PS1: Basic C++ This is now graded Out: Wed, 10 Aug 22, 12.00nn Mentioned at the end of the first lecture |
|
02, 15-19 Aug |
Not Started But there will be one optional session for official PS1 Discussion (algorithmic) after Lecture 02b (same Zoom link), but not recorded and this is done on purpose |
02a. Analysis of Algorithms (Slide 6 to 6-11) Live SpeedTest.cpp | py | java demo (measure runtime, count # of operations, vs asymptotic analysis) Kattis problem(s) discussed today: rankproblem (NEW: recoded using C++ class) thanos (Analysis: exponential growth, logarithmic steps) Reminder: Read sorting e-Lecture slides (Slide 1 to 9-3) before Lecture 02b 02b. Sorting (Slide 1 to 9-3) C++ STL algorithm: std::sort, std::stable_sort Kattis problem(s) discussed today: mjehuric (bubble sort simulation), height (insertion sort simulation), sortofsorting (NEW: custom comparator, C++ STL std::stable_sort vs std::sort) PS: stay back if you are still struggling with PS1 Last flipped classroom reminder: Read ALL sorting e-Lecture slides before Lecture 03a |
PS1 Due: Sat, 20 Aug 22, 07.59am (1%) PS2: Sorting-related Problems Out: Sat, 20 Aug 22, 08.00am |
|
03, 22-26 Aug |
(e-)Consultation starts Review demo code so far, focusing on C++ STL (algorithm, std::vector, std::string) T01+L01: tut01.pdf Introduction, OOP review (List ADT/ListArray) Analysis, Hands-on, PS1 Debrief (short), PS2 Discussion (algorithmic) |
03a. Sorting (until end) O(N log N) sorting algorithms: Merge and (Randomized) Quick Sort See the details at SortingDemo.cpp | py | java Special-purpose O(N) sorting algorithms: Counting and Radix Sort Other topics of sorting e-Lecture Sorting Online Quiz (medium) 03b. List ADT: (Singly) LL (Slide 1 to 3-22) Introducting List ADT, (resizeable) array implementation, and SLL implementation SLLDemo.cpp | py | java C++ STLs: std::forward_list (an SLL), std::list (a DLL) |
PS2, continued |
|
04, 29 Aug-02 Sep |
T02+L02: tut02.pdf Sorting Application(s), Sorting, mini experiment, ADT re-introduction, List ADT (array vs std::vector), VA OQ demo (sorting), Hands-on, PS2 Discussion (algorithmic) |
04a. Stack/Queue/Deque ADT (DLL) (until end) Focus on Stack, Queue, DLL, Deque Showing the implementations of MyStack and MyQueue (extension of SLLDemo) Plus a few other LL technicalities C++ STLs: std::stack, std::queue, std::deque (actually not a DLL) Linked List Online Quiz (medium) Kattis problem(s) discussed today: circuitmath (classic postfix evalution; use a stack/LIFO) 04b. Priority Queue (PQ) ADT: Binary Heap (Slide 1-6) Introducing PQ ADT Introducing basic Binary Heap structure and its Insert+ExtractMax operations |
PS2 Due: Sat, 03 Sep 22, 07.59am (3%) PS3: List-related Problems Out: Sat, 03 Sep 22, 08.00am |
|
05, 05-09 Sep |
T03+L03: tut03.pdf List/Stack/Queue/Deque ADT, Linked List, mini experiment, Applications PS2 Debrief (short), C++ STL (std::list/std::stack/std::queue/std::deque), VA OQ demo (list), PS3 Discussion (algorithmic) |
05a. Priority Queue (PQ) (until end) Discussing other PQ ADT details and Binary Heap implementation BinaryHeapDemo.cpp | py | java C++ STL: std::priority_queue, std::partial_sort See priority_queue.cpp at GitHub repo of CPbook website Binary Heap Online Quiz (medium) Kattis problem(s) discussed today: rationalsequence3 (stack/LIFO and binary heap indexing) 05b. Mock Practical Exam 1 Material: C++/Arrays/Vectors/Sorting/List/simpler PQ (60 minutes with commentary; 2nd hour up to you) A preparation for Midterm Quiz or future Practical Exam Kattis problem(s) discussed today: babypanda (think backwards; logarithmic) gearchanging (sort gear ratios and check change of cadence) heap (reinvent the wheel: BinaryHeapDemo.cpp or std::priority_queue) |
PS3, continued |
|
06, 12-16 Sep |
T04+L04: tut04.pdf PQ ADT Binary Heap, Additional ADT PQ Operations, C++ STL (std::priority_queue), Max-Min conversion, VA OQ demo (heap), PS3 last Discussion (algorithmic), Hands-on 1, Hands-on 2 |
06a. Table ADT part 1: Hash Table (Slide 1 to 6-2; then 10 to 10-3) Table ADT and DAT Basic Hashing Concepts One Collision Resolution Technique: CA (SC) first Hash Table Online Quiz (easy) HashTableDemo.cpp | py | java (all use SC) C++ STLs: std::unordered_set, std::unordered_map, ums, umm See unordered_map_unordered_set.cpp at GitHub repo of CPbook website Kattis problem(s) discussed today: proofs (a simple table ADT task; to showcase our own HashTableDemo.cpp) 06b. Hash Table, Continued (Slide 7 to 9-3; then Slide 11 until end) More Collision Resolution Techniques: OA (LP, QP, and DH) Comparing OA: DH with CA: SC Other technicalities of Hash Table Hash Table Online Quiz (medium) |
PS3 Due: Sat, 17 Sep 22, 07.59am (3%) PS4: PQ/HashTable-related Problems Out: Sat, 17 Sep 22, 08.00am |
|
Recess Week, 17-25 Sep 2022 We can take a break this week :) But if possible, read UFDS e-Lecture slides by yourself first... |
|||
|
07, 26-30 Sep |
T05+L05: tut05.pdf Table ADT 1 - unordered, Basic hashing concepts, Hash Table issues, PS3 Debrief (short), C++ STL (um and us, plus optional umm/ums), VA OQ demo (hashtable), PS4 Discussion (algorithmic) We will skip the hands-on session today so that we have time for Midterm Quiz QnA |
We will split the class (now of size 207) into two halves. Look at your own full name as displayed in Canvas. 108 students ['Ae Shintaro'..'Muthya Narayanachary Akhil'] go to LT15. (invigilator: @rama_pang). 99 students ['Nam Sangjun'..'Zhu Jingxi'] go to LT18. (invigilator: @RezwanArefin01). Students at LT18 group but wrongly appear at LT15 will be ask to 'run to LT18...' First 15m: VisuAlgo Online Quiz 1 (5%) Bring your own laptop that can run at least 15 minutes on battery power. (we do not provide any spare laptop). (we provide 5 power extension bars in each LT --- only for emergency cases). 207 pax will be divided into 3 staggered groups to balance server load: [10.02-10.17am, 10.03-10.18am, 10.04-10.19am]. Material: /sorting, /list, /heap, and a few 'new' questions. FAQ 1: Your VA OQ grouping is *not* the same as your LT15 vs LT18. So check your time window at VA OQ system carefully (login and see). FAQ 2: Review the first few slides of 04ab.List2-Heap.pptx for the setup. Short 5-10m break Aiming to start the next segment at 10.30am. Next 60m: Midterm Quiz (9%) Approx time window: [10.30am-11.30am] Just a few short and essay questions No more giveaway questions (the questions are either tricky or hard) You can continue using your laptop (airplane mode) as it is 'open laptop' (e.g., you want to test code your answer, thereby turning midterm into PE) But if you don't need it, you can use any printed stuff ('open book') (but we don't encourage you to kill trees..., using laptop as 'book' is better) Material: Up to PQ (L05ab on Week 05 + T04+L04 on Week 06) FAQ: Hash Table is NOT INCLUDED, all questions can be answered without hash table Midterm Test Past Papers (recent 3 AYs only): AY 2019/20: S1-midterm.pdf, S2-midterm.pdf (Dr Alan, N/A), AY 2020/21: S1-midterm.pdf, S2-midterm.pdf (Dr Alan + myself, N/A), AY 2021/22: S1-midterm.pdf, S2-midterm.pdf (myself + Dr Alan), AY 2022/23: S1-midterm.pdf (our paper). 07b. Union-Find Disjoint Sets (all slides) Live Quick Recap with VisuAlgo See unionfind_ds.cpp at GitHub repo of CPbook website Kattis problem(s) discussed today: tildes (basic UFDS task) PS: UFDS will be reused in Connected Component (CC) and MST topics |
PS4, continued |
|
08, 03-07 Oct |
T06+L06: tut06.pdf Midterm Quiz Review, UFDS Review, VA OQ demo (ufds), Hands-on, PS4 Discussion (algorithmic) |
08a. Table ADT part 2: BST + AVL Tree (until end) BST concepts and basic BST operations QnA about AVL Tree concepts 08b. Balanced BST Applications BST (only) Online Quiz (medium) BST+AVL Online Quiz (hard; need to clear pre-req) BSTDemo.cpp | py | java and AVLDemo.cpp | java C++ STLs: std::set, std::map, std::multiset, std::multimap See map_set.cpp at GitHub repo of CPbook website Kattis problem(s) discussed today: kattissquest (multiple DS implementation exercise) |
PS4 Due: Sat, 08 Oct 22, 07.59am (3%) PS5: Heavy DS Problems Out: Sat, 08 Oct 22, 08.00am |
|
09, 10-14 Oct |
T07+L07: tut07.pdf Table ADT 2 - ordered, BST/AVL advanced stuffs: Select and Rank, PQ ADT alternative implementation, Comparison with Table ADT 1: unordered vs ordered, C++ STL (map and set; plus optional mm/ms), PS4 Debrief (short), VA OQ demo (bst or avl (need to clear pre-req)) Hands-on, PS5 Discussion (algorithmic) |
09a. Graph DS Implementations of graph DS and its applications Graph DS Online Quiz (medium), No built-in C++ STL container | Python standard library | Java API, See graph_ds.cpp at GitHub repo of CPbook website, Kattis problem(s) discussed today: weakvertices (Adjacency Matrix demo) 09a. Graph Traversal (Slide 1 to 6-4) Early discussion of the basic forms of two basic Graph Traversal algorithms: DFS and BFS Kattis problem(s) discussed today: builddeps (Adjacency List of Strings) |
PS5, continued |
|
10, 17-21 Oct |
T08+L08: tut08.pdf Graph DS Review, Some Graph Properties Discussion, Graph DS Conversion Exercise, DFS/BFS Review, UFDS Revisited, Custom graph DS implementation review, VA OQ demo (graphds,dfsbfs), Hands-on, PS5 Discussion (algorithmic) |
10a. Graph Traversal (Slide 7 to 7-11) Recap of Graph Traversal algorithms Focus on DFS/BFS applications (we skip slide 8-12, out of CS2040/C/S scope) DFS/BFS Online Quiz (medium) No built-in C++ STL algorithm | Python standard library | Java API, See dfs_cc.cpp, UVa00469.cpp, and bfs.cpp at GitHub repo of CPbook website, Kattis problem(s) discussed today: reachableroads (DFS (/BFS) introduction, count #CC) builddeps (toposort demo) runningmom (AL of strings; DFS; back edge detection) 10b. Mock Practical Exam 2 Material: Everything so far, from Week 01 until Week 10a: Graph Traversal (only first 45 minutes have commentary) Kattis problem(s) discussed today: hotsprings (sort and analyze) coursescheduling (combo DS) skyislands (simple DFS/BFS) Fri, 21 Oct 2022 is chosen as NUS well being day S1 AY 2022/23 No CS2040C class is affected NUS Online Teaching Feedback opens this Fri But this timing is too early for our course... You can wait until you have done PE + VA OQ 2 |
PS5 Due: Sat, 22 Oct 22, 07.59am (3%) PS6: SSSP+MST Problems Out: Sat, 22 Oct 22, 08.00am |
|
Those (2 pax) who miss Midterm Quiz on Week 07 due to VALID reasons (valid Medical Certificate; representing NUS for an official event; bereavement of immediate family member) do make up midterm quiz on Week 10. Note that there is no more make up of make up :O... |
|||
|
11, 24-28 Oct |
T09+L09: tut09.pdf DFS/BFS advanced stuffs: Cycle Detection, Toposort++, Floodfill/CC, Modeling exercise (time permitting), PS5 Debrief (short), VA OQ demo (dfsbfs,sssp), Tips for VA OQ 2 next week, Past PE Reviews |
Diwali Public Holiday is on Mon, 24 Oct 2022 CS2040C Monday classes are affected. See the arrangement outlined in T09+L09: tut09.pdf. 11a. SSSP Problem (Slide 1 to end) Review of basic SSSP problem QnA on BFS algorithm for unweighted SSSP QnA on Dijkstra's algorithm (the original form first) SSSP Online Quiz (medium) See bfs.cpp (again) and dijkstra.cpp at GitHub repo of CPbook website 11b. Practical Exam (15%) Timing: Thu, 27 Oct 2022, 6.00-8.00pm (120m) That is, our usual Thu (e-Lecture) slot is cancelled we will do PE from 6.00pm and continues until 8.00pm. (venue restrictions at other timeslots). 67 students ['Ae Shintaro'..'Justin Soh Jun Hao'] go to LT16. (invigilator: @dZhei). 73 students ['Keane Chan Xing Zhao'..'Ryuji Kow Jie Si'] go to LT17. (invigilator: @Berted). 67 students ['Samuel Tan Sze Wee'..'Zhu Jingxi'] go to LT18. (invigilator: Marc Phua). Material: Week 01 until Week 10b. It is an Open Internet PE. |
PS6, continued |
|
12, 31 Oct-04 Nov |
T10+L10: tut10.pdf BFS/Dijkstra's review Modeling exercises (continued), VA OQ demo (ufds,hashtable,bst,graphds,dfsbfs,sssp), Hands-on, PS6 Discussion (algorithmic) (short PE debrief by TA) |
12a. MST Problem (Slide 1 to end) Review of basic MST problem QnA on Kruskal's and Prim's algorithms Mix and Match of various data structures/algorithms covered so far Kattis problem(s) discussed today: cats (MST application) Onsite class photo at LT15 as momento 11.22-11.42am or 11.23-11.43am: VisuAlgo Online Quiz 2 (12%) must be onsite at LT15 to have valid VA OQ 2 grade (MC/COVID+ moved to make-up VA OQ 2 on 16 Nov) bring your own laptop visualgo.net/tests page must be full screen throughout the test all topics, including SSSP MST is not included (for final later) 12b. SSSP+MST Extras QnA on Bellman-Ford algorithm QnA on Modification of Dijkstra's algorithm QnA on other special cases of SSSP problem Other MST variants |
PS6, continued |
|
13, 07-11 Nov |
T11+L11: tut11.pdf Bellman-Ford + Modified Dijsktra Review MST Review (2 algorithms), Final paper preparation (from any past paper), VA OQ demo (mst), Hands-on, PS6 Last Discussion (algorithmic) Class Photo (for momento) Tutorial Participation Marks given (3%) |
Steven is at Dhaka, Bangladesh, for ICPC World Finals 2021 (that has been postponed until this week, 06-11 Nov 2022) a short recording of the last lecture 13a has been released (hard to do live at 8-10am Dhaka time) 13a. The Last Lecture (e-Lecture) Course wrap-up et al: Undoing all the illegal C++ coding techniques, Semester summary, Review of what can be done better for future iterations, Advertisement of future (algorithm) modules: CS3233 or CS3230 → CS4234 Advertisement for part-time TA jobs (A-/A/A+ only), Ending: a few Final Assessment Tips. Lecture 13b is cancelled It is the ICPC World Finals 2021 date |
PS6 Due: Thu, 10 Nov 22, 07.59am (3%) |
|
Study Week, 12-18 Nov 2022 Make-up (or Remedial) Practical Exam Timing: Wed, 16 Nov 2022 (10.00am-12.00noon, 120m) Venue: SR@LT19 (next to LT19) Details only given to those who are invited. Make-up VisuAlgo Online Quiz 2 Venue: SR@LT19 too Timing: Wed, 16 Nov 2022 (12.15-12.35noon, 20m) (only for those with MC/COVID+ on 2 Nov) Final Assessment Consultations (per request) Final Assessment Past Papers (recent 3 AYs only): AY 2019/20: S1-final.pdf, S2-final.pdf (Dr Alan, N/A), AY 2020/21: S1-final.pdf, S2-final.pdf (Dr Alan+myself), AY 2021/22: S1-final.pdf, S2-final.pdf (most recent past paper), Final Preparation Tracker at nus.kattis AY 2022/23: S1-final.pdf (our paper). NUS Online Teaching Feedback System closes on Friday of Study Week |
|||
|
Final Assessment (40%) Date and Time: Sat, 26 Nov 2022, 1-3pm Venue: MPSH2-B 39% MCQs (very tricky); 15% easy essay; 46% differentiator questions |
|||
Steven uses a small-scale gamification system in his version of CS2040/C/S 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 large (more than 200), only students with at least one achievement will be listed below (so the list is not the full class roster).
| No | Student Name | Achievements |
|---|