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 ~100 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 are 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.
Some other facts:
Rating (out of 5.0) (SoC avg ~4.1) |
Aug-Dec 19 (n≥48+??/96) ≥50.0+% |
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 18 Sep 2019, finally all 98 students have official tutorial group:
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/17) | 09 | Matthew |
4/Thu, 1000-1100 | COM1-0120 (19/19) | 03 | StevenW |
4/Thu, 1100-1200 | COM1-0120 (17/17) | 04 | StevenW |
4/Thu, 1400-1500 | COM1-0120 (17/17) | 07 | KWei Heng |
4/Thu, 1500-1600 | COM1-0120 (14/17) | 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-0208 (17/17) | 01 | Matthew |
Latest info as of 24 Sep 2019, finally all 98 students have official lab group:
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 (18/20) | 01 | Kane |
1200-1300 | COM1-0120 (20/20) | 05 | Shantanu |
1300-1400 | COM1-0120 (22/22) | 06 | Shantanu |
1400-1500 | COM1-0120 (18/20) | 07 | Aaryam |
1500-1600 | COM1-0120 (20/20) | 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 |
---|
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 (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 (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) Kattis problem discussed: joinstrings (NEW: list concatenation via std::list (splice); or others) |
T01: Introduction, OOP (basic), Analysis, PS1 Discussion (up to 60 points), tut01.pdf |
L01: Quick Intro, Review demo code so far, focusing on OOP review (List ADT/ListVector) C++ STL (algorithm, vector, string), A sorting challenge, PS1 Discussion (algorithmic) |
PS1, continued |
04, 02-06 Sep |
04a. Stack/Queue/Deque ADT (DLL) (until end) SLLDemo.cpp Then 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, non 100 points subtasks, optional in PS2 later) 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 re-introduction, List ADT (array vs vector), PS1 Discussion (up to 100 points), tut02.pdf |
L02: Quick Re-introduction, VA OQ demo (sorting,list), PS1 last minute discussion, Hands-on: gearchanging (about sorting fractions) |
PS1 Due: Sat, 07 Sep 19, 07.59am (3%) PS2: List-related Problems Out: Sat, 07 Sep 19, 08.00am B: teque is optional and not graded. |
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) 05b. Mock Practical Exam 1 Material: C++/Arrays/Vectors/Sorting (but 45 minutes only) Kattis problems discussed: pivot (O(n^2) TLE; O(n log n) difficult; O(n) easy) froshweek (O(n^2) TLE again; O(n log n) possible) |
T03: List ADT, Linked List Review, Stack/Queue/Deque ADT, One application, PS2 Discussion (up to 60 points), tut03.pdf |
L03: PS1 Quick Debrief, C++ STL (list/stack/queue/deque), VA OQ demo (heap), PS2 Discussion (algorithmic) Hands-on: throwns (about LL/variant) |
PS2, continued |
06, 16-20 Sep |
06a. Practical Exam 1 (7%) During our Wed, 18 Sep 2019 lecture time (10.05am-11.35am, 90m) Material: Up to Week 03 L03a + Week 04 T02+L02 i.e. Basic C++, Time Complexity, and Sorting only Venue: Our lecture venue (I3-AUD), attendance is compulsory Open book, bring your own laptop :O Configure your laptop to compile C++ (-std=gnu++17) code offline If you don't have laptop :O, or your laptop is broken...; borrow someone else's or take (harder) re-PE1 @ PL2 on 25 Sep Do NOT use online IDE (or share your work online using any means) As plagiarism checkings are done at server side Tips: The first few who manage to get (close to) 200/200 should apply "every man (woman) for himself (herself)" strategy by keeping your work private until 11.35am as we will definitely pairwise compare subsequent ACs with yours 06b. Midterm Quiz (8%) During our Thu, 19 Sep 2019 lecture time (17.02pm-17.42pm, 40m) Material: Up to Week 04 L04a + Week 05 T03+L03, i.e. Basic C++ (comprehension), Time Complexity, Sorting, and Linked List Venue: Our lecture venue (I3-AUD) Open book (no restriction), theory only :O but NO electronic device (insane level questions if I allow Open Internet) No C++ coding question (but C++ code can be given in the question) Format: MCQ, Fill in the Blanks, and Short Answers The last question is a "feedback" question that you can pre-compute Steven is especially interested to gather feedback about Open Internet PE1 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, CS2040C-2019-20-S1-midterm-medium.pdf (our paper). |
T04: Midterm Quiz Preparation or Solutions (depends on timing), Basic PQ ADT tut04.pdf |
L04: PE1 Upsolve Lab TA will show a detailed walkthrough of nus.basicprogramming1 (CS1010 mass review) and at least 79 points of of nus.magicsequence (on how to be faster than std::sort) |
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 this week :) Unless..., if you happen to also organize/participate in this event But if possible, read Hash Table and BST e-Lecture slides by yourself first... PS: Those who miss PE1 and/or Midterm Quiz due to VALID reasons (valid Medical Certificate; representing NUS for an official event; bereavement of immediate family member) and those who want to retake (especially bottom 44 students) can take make-up/remedial PE1+midterm quiz: Make up/Remedial Practical Exam 1, Wed, 25 Sep 2019 (10.00am-12.00pm, 120m, venue: COM1-B-PL2; capacity: 46; (replacement 8+7 = 15%; I take the best of the two)) Material: Now up to Week 06 stuffs, i.e. Priority Queue is now included (review PE1+Midterm Quiz on Week 06 too), and clearly harder than the original PE1+Midterm Quiz combo... Note that there is no more make up of make up :O... |
||||
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; at open.kattis only for now), 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 |
L05: PS2 Debrief (short), C++ STL (priority_queue), Max-Min conversion, PS3 Discussion (short), Hands-on: canvas (greedy simulation with 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 (hashtable,bst,avl), Hands-on: baconeggsandspam (simple 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/BFS 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: traveltheskies ('challenging' graph DS) |
PS4, continued |
10, 21-25 Oct |
10a. Mock Practical Exam 2 Material: Everything so far, from Week 01 until Graph Traversal Kattis problems discussed: gold (implicit 2D grid graph; modified traversal), knigsoftheforest (sort by year; PQ simulation), brexit (deferred to Thursday; happening or not?). 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: brexit (kind of topological sorting; modified Kahn's algorithm), 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: daceydice (interesting 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 and a few NUS students (none from this class) have competed in ICPC Asia Jakarta 2019, Fri 25 Oct (AM) - Tue, 29 Oct 2019 (PM) No CS2040C class is affected. NUS team Send Bobs to Alice won the contest. 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 |
11a. This 2h lecture is cancelled so that students can prepare for PE2 tonight Practical Exam 2 (12%) Timing: Wed, 30 Oct 2019, 6.30-8.30pm Venues with total capacity ≥ 96: COM1-B-PL2 (capacity 46; for 42 who attended re-PE1) COM1-B-PL4 (capacity 25; for 21 who scored ≤ 123 in PE1 but no re-PE1) COM1-B-PL1 (capacity 44; for the other 33 students) Open Internet but full invigilation setup 11b. 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; optimized to O(k*E)) knightjump (BFS demo; implicit graph again) |
T09: DFS/BFS advanced stuffs, Cycle, Toposort++, (Floodfill/CC), Modeling exercise 2 (time permitting), (or PE2 preperation for TG09), tut09.pdf |
L09: PS4 Debrief (short), PS5 Discussion (short), PE2 upsolve (if possible, /ads and /clinic full) |
PS5, continued |
12, 04-08 Nov |
12a. SSSP continued: Dijkstra's (2 versions and implementation) No built-in C++ STL algorithm, See dijkstra.cpp at GitHub repo of CPbook website, SSSP Online Quiz (medium) Kattis problem discussed: shortestpath1 (that Dijkstra's implementation is easy; both versions) flowerytrails (Dijkstra's (any version) and DFS/BFS to traverse the shortest path(s)) 12b. SSSP continued: On Tree, On DAG, applications Kattis problems discussed (past paper): detour (SDSP, traversal on modified graph) NUS Online Teaching Feedback System opens this Friday |
T10: Bellman Ford's, BFS, and Original Dijkstra's Review, Modeling exercises 3, tut10.pdf (Participation Marks Given, 3%) |
L10: VA OQ demo (sssp) Tips for OQ preparation Class Photo (for momento), Hands-on: texassummers (SSSP+output shortest path) PS5 last minute discussion (offline) (Participation Marks Given, 3%) |
PS5, continued |
13, 11-15 Nov |
13a. This 2h lecture will be just 1h because Steven has important CS4234 mini project evaluation at 12-2pm 13a. Optional Lecture: MST Prim's algorithm only (Priority Queue++) 13b. Last Lecture Semester summary, Review of what can be done better for future iterations, Advertisement of future (algorithm) modules, Ending: a few Final Assessment Tips. |
T11: Final paper preparation, Class Photo, tut11.pdf |
D11: VA Online Quiz (12%) (URL: https://visualgo.net/training, click 'CS2040C Quiz') Time: 25+5m, 19+2 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 new Q20+Q21 that cannot be prepared by anyone |
PS5 Due: Mon, 11 Nov 19, 07.59am (+48 hours extension) (3%) |
Study Week, 18-22 Nov 2019 Make up/Remedial Practical Exam 2, Wed, 20 Nov 2019 (10.00am-12.00pm, 120m) Venue: PL2 Final Assessment Consultations (per request) Collection of Past Paper Last Questions 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, CS2040C-2019-20-S1-final.pdf (our paper), NUS Online Teaching Feedback System closes on Friday of Study Week |
||||
Final Assessment (40%) Date and Time: Wed, 04 Dec 2019, 09-11AM Venue: SPORTS & RECREATION CENTRE, MULTI-PURPOSE SPORTS HALL 5 New: I have MCQs this time to reduce my grading load a bit (CS4234 exam on Tue, 03 Dec 2019 and I have to submit marks by 09 Dec)... |
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 |
---|