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 Java.
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 no longer teaches CS2040C from the recent S2 AY 2022/23 and perhaps for many AYs ahead.
Steven now teaches CS2040S in S1 AY 2023/24 (Aug-Nov 2023). 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 AY 2023/24, the main change is Steven is switching from CS2040C (C++, now a 'smaller cohort') to CS2040S (Java, only for CS students in SoC).
Some other facts:
| Rating (out of 5.0) |
Aug-Nov 23 (n=???/200?) ??% |
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% ▼ |
|---|---|---|---|---|---|---|
| Course feedback (SoC avg ~3.8) | Target 4.2 | 4.2 == | 4.2 == (+Alan) | 4.2 == | 4.2 ▲ (+Alan) | 3.8 ▼ (C-19+IOI 20) |
| Course difficulty (SoC avg ~3.8) | Target 4.1 (let's lower this) | 4.3 ▲ | 4.2 == (high) | 4.2 ▲ | 3.9 ▼ (easiest) | 4.6 ▲ (C-19+IOI 20) |
| Steven's teaching (SoC avg ~4.1) | Target 4.3 | 4.5 ▲ | 4.3 ▼ (+Alan) | 4.5 ▲ | 4.4 ▲ (+Alan) | 4.3 ▼ (C-19+IOI 20) |
Update on 05 Jun 2023
Steven is now recruiting (part-time) TAs for next sem...
The list below are the eight two-hours tut+lab combo on Mondays and the candidates who have applied so far (application window is until 30 June 2023).
There will be a few other time slots for consultation slots (but this time, we will roster a few common slots instead of each TA has a specific consultation slot).
| Date, Time | Live Session (Venue) (#Stu/#Cap) | No | Tutor |
|---|---|---|---|
| 1/Mon, 1000-1200 | COM1-B109 (PL2) (??/30-35?) | 01 | [most likely a full-time/special TA] |
| 1/Mon, 1000-1200 | COM1-B108 (PL3) (??/24) | 02 | ?? |
| 1/Mon, 1200-1400 | COM1-B109 (PL2) (??/30-35?) | 03 | [most likely a full-time/special TA] |
| 1/Mon, 1200-1400 | COM1-B108 (PL3) (??/24) | 04 | ?? |
| 1/Mon, 1400-1600 | COM1-B108 (PL3) (??/24) | 05 | ?? |
| 1/Mon, 1400-1600 | COM1-B111 (PL4) (??/24) | 06 | ?? |
| 1/Mon, 1600-1800 | COM1-B108 (PL3) (??/24) | 07 | ?? |
| 1/Mon, 1600-1800 | COM1-B111 (PL4) (??/24) | 08 | ?? |
List of TA applications (currently in alphabetical order):
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 dcssh at nus edu sg. 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, 14 Aug |
Not Started |
Not started, but please revise your CS1010/equivalent 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 Java specific instructions @ Kattis, pick up basic Java by yourself, and solve the selected optional Online Judge (OJ) Problem Set 0 (PS0) by yourself (CS1010/equivalent level): (solving many 'trivial problems' from this set ---trackable by Steven, indirectly tells Steven about your CS1010/equivalent rough grade) Singapore National Day on Wed, 09 August 2023 This time, CS2040S first lecture is not affected |
PS0: Easy Java/coding challenges (02-16 Aug) already graded to speed up registration admins |
|
01, 14-18 Aug |
Not Started |
01a. Course Admin, (Re-)Introduction to Java Setting the tone for a flipped classroom plus all ONSITE course VisuAlgo + this Private Canvas + Kattis (NUS) + Kattis (open) Basic Java review/new feature introduction Kattis problem(s) discussed today: TBC (something trivial) 01b. (Re-)Introduction to Java (continued) Kattis problem(s) discussed today: TBC (something involving basic OOP) Reminder: Read summary on algorithm analysis (Slide 1 to 9-3) before Lecture 02a |
PS0 Due: Wed, 16 Aug 23, 11.29am (1%) PS1: Basic Java Out: Wed, 16 Aug 23, 11.30am Mentioned at the end of the first lecture |
|
02, 21-25 Aug |
Not Started |
02a. Analysis of Algorithms (Slide 6 to 9-3) Live SpeedTest.cpp | py | java demo (measure runtime, count # of operations, vs asymptotic analysis) Fast review of O(N^2) sorting algorithms Kattis problem(s) discussed today: TBC Reminder: Read sorting e-Lecture slides (Slide 1 to 11-11) before Lecture 02b 02b. Sorting (Slide 1 to 11-11) O(N log N) sorting algorithm: Merge Sort Java Collections.sort Kattis problem(s) discussed today: TBC Last flipped classroom reminder: Read ALL sorting e-Lecture slides before Lecture 03a Steven probably departs to Europe right after this lecture (TBC). |
PS1 Due: Sat, 26 Aug 23, 07.59am (2%) PS2: Sorting-related Problems Out: Sat, 26 Aug 23, 08.00am |
|
03, 28 Aug-01 Sep |
(e-)Consultation starts Review demo code so far, focusing on Java API (Collections, ArrayList, String) T01+L01: tut01.pdf Introduction, OOP review (List ADT/ListArray) Analysis, Hands-on, PS1 Debrief (short), PS2 Discussion (algorithmic) |
Steven will be in Szeged, Hungary, for IOI 2023 (28 Aug-04 Sep 2023) Steven plan to record this week's lectures. 03a. Sorting (until end) Another O(N log N) sorting algorithm: (Randomized) Quick Sort See the details at SortingDemo.cpp | py | java Special-purpose O(N) sorting algorithm: Counting Sort (Only) Other topics of sorting e-Lecture Sorting Online Quiz (medium) 03b. Mock Practical Exam 1 Material: Java/ArrayLists/Sorting (Steven will record his live-(re-)solving attempt) A preparation for Midterm Quiz or future Practical Exam Kattis problem(s) discussed today: TBC |
PS2, continued |
|
04, 04-08 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. List ADT: (Singly) LL/Stack/Queue (Slide 1 to 5-6) Introducting List ADT, (resizeable) array implementation, and SLL implementation Stack and Queue ADTs Showing the implementations of MyStack and MyQueue (extension of SLLDemo) SLLDemo.cpp | py | java Java LinkedList and Stack classes and Java Queue interface Stack and Queue in their (resize-able) Array implementations (TBA) 04b. Deque ADT (DLL) (until end) DLL and Deque ADT Plus a few other LL technicalities Java Deque interface Linked List Online Quiz (medium) Kattis problem(s) discussed today: TBC |
PS2 Due: Sat, 09 Sep 23, 07.59am (2%) PS3: List+PQ Problems Out: Sat, 09 Sep 23, 08.00am |
|
05, 11-15 Sep |
T03+L03: tut03.pdf List/Stack/Queue/Deque ADT, Linked List, mini experiment, Applications PS2 Debrief (short), Java LinkedList/Stack/Queue/Deque, VA OQ demo (list), PS3 Discussion (algorithmic) |
05a. Priority Queue (PQ) ADT: Binary Heap (Slide 1 to 8-3) Introducing PQ ADT Introducing basic Binary Heap structure and its Insert+ExtractMax operations Discussing other PQ ADT details and Binary Heap implementation BinaryHeapDemo.cpp | py | java 05b. Priority Queue (PQ) (until end) See priority_queue.cpp | py | java at GitHub repo of CPbook website Java PriorityQueue class Binary Heap Online Quiz (medium) Kattis problem(s) discussed today: TBC |
PS3, continued |
|
06, 18-22 Sep |
T04+L04: tut04.pdf PQ ADT Binary Heap, Additional ADT PQ Operations, Java PriorityQueue, Max-Min conversion, VA OQ demo (heap), PS3 last Discussion (algorithmic), We will skip the hands-on session today so that we have time for Midterm Quiz QnA |
First 15m: VisuAlgo Online Quiz 1 (6%) Approx time window: [10.02am-10.17am] (15 minutes). Bring your own laptop that can run at least 15 minutes on battery power. (we do not provide any spare laptop). Material: /sorting, /list, /heap (1 Q), and a few 'new' questions. Short Break Next 70m: Midterm Quiz (11%) Approx time window: [10.25am-11.35am] (70 minutes). A few short questions (close-ended) and one (hard) essay question No more giveaway questions (the questions are either tricky or hard) There will be a few blank boxes, which will be given 1 mark if left blank, but 0 if answered (even a single character) and declared (very) wrong Material: Up to PQ (L05ab on Week 05 + T04+L04 on Week 06) Midterm Test Past Papers (recent 3 AYs only): 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, [I didn't teach CS2040C in S2], AY 2023/24: S1-midterm.pdf (will be our paper, easy, I promise). 06b. Union-Find Disjoint Sets (all slides) Live Quick Recap with VisuAlgo See unionfind_ds.cpp | py | java at GitHub repo of CPbook website Kattis problem(s) discussed today: TBC PS: UFDS will be reused in Connected Component (CC) and MST topics |
PS3 Due: Sat, 23 Sep 23, 07.59am (2%) PS4: Hash Table+UFDS Problems Out: Sat, 23 Sep 23, 08.00am |
|
Recess Week, 23 Sep-01 Oct 2023 You can take a break this week :) Steven (and full-time TA?) will grade your Midterm Quiz during this period But if possible, read Hash Table e-Lecture slides by yourself first... |
|||
|
07, 02-06 Oct |
T05+L05: tut05.pdf Midterm Quiz Review, UFDS Review, VA OQ demo (ufds), Hands-on 1, Hands-on 2 |
07a. Table ADT part 1: Hash Table (Slide 1 to 7-11; then 10 to 10-3) Table ADT and DAT Basic Hashing Concepts One Collision Resolution Technique: OA (LP) Another Collision Resolution Technique: CA (SC) Hash Table Online Quiz (easy) HashTableDemo.cpp | py | java (all use SC) Java HashSet/HashMap/Hashtable classes See unordered_map_unordered_set.cpp | py | java at GitHub repo of CPbook website Kattis problem(s) discussed today: TBC 07b. Hash Table, Continued (Slide 8 to 9-3; then Slide 11 until end) More Collision Resolution Techniques: OA (QP and DH) Comparing OA: DH with CA: SC Other technicalities of Hash Table Hash Table Online Quiz (medium) |
PS4, continued |
|
08, 09-13 Oct |
T06+L06: tut06.pdf Table ADT 1 - unordered, Basic hashing concepts, Hash Table issues, PS3 Debrief (short), Java HashSet/HashMap/HashTable, VA OQ demo (hashtable), PS4 Discussion (algorithmic) |
08a. Table ADT part 2: BST + AVL Tree (until end) BST concepts and basic BST operations NEW: The multiset idea BSTDemo.cpp | py | java BST (only) Online Quiz (medium) QnA about AVL Tree concepts 08b. Balanced BST Applications BST+AVL Online Quiz (hard; need to clear pre-req) AVLDemo.cpp | (no py yet) | java Java TreeSet/TreeMap classes See map_set.cpp | (no built-in py) | java at GitHub repo of CPbook website Kattis problem(s) discussed today: TBC |
PS4 Due: Sat, 14 Oct 23, 07.59am (2%) PS5: Heavy DS Problems Out: Sat, 14 Oct 23, 08.00am |
|
09, 16-20 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, Java TreeSet/TreeMap, 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 | py | java at GitHub repo of CPbook website, Kattis problem(s) discussed today: TBC Last 15m: VisuAlgo Online Quiz 2 (6%) Approx time window: [11.20am-11.35am] (15 minutes). Bring your own laptop that can run at least 15 minutes on battery power. (we do not provide any spare laptop). Material: /heap (again), /ufds, /hashtable, /bst, and a few 'new' questions. 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: TBC |
PS5, continued |
|
10, 23-27 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 | py | java, UVa00469.cpp | py | java, and bfs.cpp | bfs.py | java at GitHub repo of CPbook website, Kattis problem(s) discussed today: TBC 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: TBC 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 3 |
PS5 Due: Sat, 28 Oct 23, 07.59am (2%) PS6: SSSP+MST Problems Out: Sat, 28 Oct 23, 08.00am |
|
Make-up time window Those who miss VisuAlgo Online Quiz 1 on Week 06 and/or 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 on Week 10 (details TBC). Note that there is no more make up of make up :O... |
|||
|
11, 30 Oct-03 Nov |
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 |
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 dijkstra.cpp | py | java at GitHub repo of CPbook website 11b. Practical Exam (15%) Timing: TBC. Not going to be fully Open-Internet... (Generative AI tools make this scary) All other details TBC. |
PS6, continued |
|
12, 06-10 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) Class Photo (for momento) Tutorial Participation Marks given (3%) |
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: TBC Onsite class photo as momento Last 15m: VisuAlgo Online Quiz 3 (6%) Approx time window: [11.20am-11.35am] (15 minutes). Bring your own laptop that can run at least 15 minutes on battery power. (we do not provide any spare laptop). Material: all CS2040S topics excluding /mst. 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 Fri, 10 Nov 2023 is chosen as NUS well-being day S1 AY 2023/24 No CS2040S class is affected (for Week 12) |
PS6, continued |
|
13, 13-17 Nov |
Sun, 12 Nov 2023 is Deepavali PH Thus, Mon, 13 Nov 2023 is also a PH CS2040S last tutorial is cancelled /mst will be asked in final as an 'easy Q' |
Steven will be in Sharm El-Sheikh, Egypt, for combo ICPC World Finals 2022+2023 (12-17 Nov 2023) Steven plans to record the last summary lecture Lecture 13a is cancelled It is the projected ICPC World Finals 2022+23 date 13b. The Last Lecture (e-Lecture) Course wrap-up et al: Undoing all the illegal Java coding techniques, Semester summary, Review of what can be done better for future iterations, Advertisement of future (algorithm) courses: CS3233 or CS3230 → CS4234 Advertisement for part-time TA jobs (A-/A/A+ only), Ending: a few Final Assessment Tips. |
PS6 Due: Thu, 17 Nov 23, 07.59am (2%) |
|
Study Week, 18-24 Nov 2023 Make-up (or Remedial) Practical Exam Timing: TBC All other details TBC. Final Assessment Past Papers (recent 3 AYs only): 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), AY 2022/23: S1-final.pdf, [I didn't teach CS2040C in S2], Final Preparation Tracker at nus.kattis AY 2023/24: S1-final.pdf (will be our paper). NUS Online Teaching Feedback System closes on Friday of Study Week |
|||
|
Final Assessment (40%) Date and Time: ???, ?? Nov 2023, ?-?pm Venue: TBA 45% MCQs (very tricky); 25% easy short questions; 30% 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 (approximately 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 |
|---|