CS2040S - Data Structures and Algorithms (Java)

Introduction

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, trees, and graphs), searching and sorting algorithms, and basic analysis of algorithms.

The programming language used for this course is Java.

We use very basic object-oriented programming concepts in various data structures implementations, e.g., Stack class inherits LinkedList class (more details of OOP are in CS2030).

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

Prof Halim is focusing on SoC Computer Science (CS) cohort since S2 AY 2022/23 - present.
That's it, if you are a SoC CS student, you may encounter Prof Halim in CS2040S S1 and/or CS3230 S1.
If you reach this page because you are looking for CS2040/C information, Prof Halim doesn't teach those version now, contact Dr Chong Ket Fah Prof Roger/Sanka/Anandha (CS2040) or Prof Alan (CS2040C).

Some facts:

1. Prof Halim has implemented flipped classroom (a type of blended learning) techniques, employing machine-teach-(and-auto-test)-students-on-basic-stuffs, along with in-class live discussion of more challenging problems in his CS2040/C/S classes. From AY 2017/18 until the present, he has received teaching feedback ratings from 4.2 (slightly above average) to 4.8 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.455 (very good).
2. Apart from teaching CS2040/C/S on multiple occassions from 2017 to the present, Prof Halim has also taught similar courses that are variants of the current version of CS2040/C/S, namely CS2020 once (2011), CS2010 six times (2011-2016), CS1020E once (2016), and IT5003 (2020-present).
3. Teaching staffs:
   Associate Professor Steven Halim, the key man behind VisuAlgo, a tool that will be extensively utilized in this course.
   The primary goal for this S1 AY2024/25 is for Prof Halim to survive teaching three (two are large) courses at the same time (CS2040S - 161 pax; IT5003 - 33 pax (small); CS3230 - 435 pax; totalling up to 629 pax).
   One key way to do that is to align CS2040S as close as possible to its subset course IT5003.
   
   

   Rating (out of 5.0)	Aug-Nov 24 (n≥58/161) ≥36%	Aug-Nov 23 (n=90/128) 70% ▼	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 lvl 2000 ~3.9)	4.2 (tgt)	4.2 ==	4.2 ==	4.2 == (+Alan)	4.2 ==	4.2 ▲ (+Alan)	3.8 ▼ (C-19+IOI 20)
   Course difficulty (SoC avg lvl 2000 ~3.8)	[4.0..4.1] (tgt)	4.3 ==	4.3 ▲	4.2 == (high)	4.2 ▲	3.9 ▼ (easiest)	4.6 ▲ (C-19+IOI 20)
   Prof Halim's teaching (SoC avg lvl 2000 ~4.2)	[4.3..4.4] (tgt)	4.4 ▼	4.5 ▲	4.3 ▼ (+Alan)	4.5 ▲	4.4 ▲ (+Alan)	4.3 ▼ (C-19+IOI 20)

   TAs:
   

   Date, Time	Live Session (Venue) (#Stu/#Cap)	No	TA
   1/Mon, 1000-1200	COM1-B109 (PL2) (22/22)	01	@pisciprehender
   1/Mon, 1000-1200	COM1-B108 (PL3) (22/22)	02	@saddle196883
   1/Mon, 1200-1400	COM1-B109 (PL2) (21/21)	03	@chiralcentre
   1/Mon, 1200-1400	COM1-B108 (PL3) (22/22)	04	@ernest__
   1/Mon, 1400-1600	COM1-B108 (PL3) (19/21)	05	@sandyk_sk
   1/Mon, 1400-1600	COM1-B111 (PL4) (19/21)	06	@chronal_02
   1/Mon, 1600-1800	COM1-B108 (PL3) (20/21)	07	@json.c
   1/Mon, 1600-1800	COM1-B111 (PL4) (16/21)	08	@ahzong
   5/Fri, 1900-2100 2100-2300	Zoom Recurring Link (free and easy)	-	various TAs

   List of TAs (ordered using Lab Group Number):

   1. @pisciprehender, Zhang Puyu (peak rating: 4.9/CS1010)
   2. @saddle196883, Timothy Wan Kai Yang (peak rating: 4.8/CS2040S)
   3. @chiralcentre, Ryan Tan Wei Jie (peak rating: 4.9/CS2040S)
   4. @ernest__, Ernest Ng Zi Xuan (peak rating: 4.6/CS2040S+CS2040C)
   5. @sandyk_sk, Sandy Kristian Waluyo (IMO 22 Bronze, new NUS TA)
   6. @chronal_02, Winston Leonard Prayonggo (peak rating: 4.9/CS2040S)
   7. @json.c, Jason Christopher (peak rating: 5.0/CS2040S)
   8. @ahzong, Chong Chin Herng (peak rating: 4.9/CS1231S)
   9. Special full-time TA for Week 02-04 only: @dustbinnnnnn, Ng Tzer Bin
   10. Special part-time TA for grading midterm+final only: Ivan Chew Teck Meng
   11. PE Setting Only: Muhammad Ayaz Dzulfikar
4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
5. For CS2040S, have you passed CS1231 (or its variants)? You have to...
6. Have you taken CS1020/CS1020E/CS2010/CS2020? You cannot take CS2040/C/S if you have taken similar/older course(s) that have huge degree of overlap with this course.

Syllabus

This is what you will learn if you take CS2040/C/S taught by Prof Halim, compare it with the subset IT5003 version:

• Part 0: A quick review of CS1101S/CS1010/variants - Programming Methodology
• Part 1: Algorithms using the simplest Linear Data Structure:
  1. Simple algorithms involving (Resize-able) Array/Java ArrayList (some are Complete Search, a.k.a., Brute Force)
  2. Various Sorting algorithms (DnC) and a few simple (Greedy) algorithms that are applicable after sorting the data
• Part 2: Various Linear Data Structures (DSes):
  1. List Abstract Data Structure (ADT)
  2. Stack, Queue, and Deque ADTs in their Linked List implementations
  3. Stack and Queue in their (resize-able/circular) Array implementations
• Part 3: Various (Non-)Linear Data Structures (DSes):
  1. Priority Queue (PQ) ADT, its Binary Heap implementation (DnC), and Greedy algorithm with PQ (Greedy)
  2. Table/Map (ADT) part 1 (unordered) and its Hash Table implementation (DnC)
  3. Disjoint Sets ADT and its Union-Find Disjoint Sets implementation (DnC)
  4. Table/Map (ADT) part 2 (ordered) and its Binary Search Tree (BST) implementation, inclusive of the balanced BST version: Adelson-Velskii Landis (AVL) Tree (DnC)
  5. Graph DS: Adjacency Matrix/Adjacency List/Edge List/Implicit Graph
• Part 4: Algorithms for Graph Problems:
  1. Graph Traversal (BF): Depth-First Search (DFS), Breadth-First Search (BFS), and various application scenarios (Complete Search)
  2. Single-Source Shortest Paths (SSSP): Bellman-Ford algorithm (DP), Dijkstra's algorithm (two versions, Greedy), various special cases and various application scenarios, e.g., Shortest Paths on unweighted graph (BFS), Tree (BFS/DFS), DAG (DP), Line Graph, Complete Graph
  3. Minimum Spanning Tree (MST): Kruskal's or Prim's algorithms (both are Greedy), various special cases and various application scenarios
• Part 5: Beyond polynomial-time algorithms: Short introduction to the theory of NP-completeness (preview of CS3230)
• Throughought this course:
  1. More advanced data structures and algorithms design and analysis (compared to Programming Methodology, but not as advanced as CS3230)
  2. Various trade-offs situations
  3. Real-life problem solving skills (Complete Search/Brute Force/BF, Divide and Conquer/DnC, Greedy, and Dynamic Programming/DP)
  4. Recursive thinking
  5. Proper implementation (more emphasis) of (some) data structures and algorithms in Java with (lesser emphasis) their Java API version at the end

Course Registration Additional FAQ

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.

Q: Will there be a Practical Exam (PE) for your version of CS2040/C/S?

A: Yes, there will be a Practical Exam (PE) held once, specifically on Week 10, covering all topics up to just before the graph data structure. However, due to the availability of generative AI tools like ChatGPT, Prof Halim is no longer feels comfortable conducting an Open Internet PE (and also not allowed to). Instead, the plan is to implement onsite proctoring with some form of Internet firewall. The specific details are yet to be confirmed.

Q: PE sounds scary... Will there be a make up PE if I am sick/underperform...?

A: Yes. Prof Halim is aware that many students are still at learning stage. Those who are absent from the official ones for valid reason (clash with another official NUS course, Medical Certificate (MC), Bereavement of immediate family member, representing NUS for official event) and a few bottom X (TBC) students will be invited for the make up PE sometime during study week.

Q: Will this course be graded using Bell curve?

A: CS2040S has much more than 40 students each semester. Bell curve system will obviously be used.

Q: I am from CS1101S (subset of JavaScript)/CS1010S or CS1010E (Python)/other modules that do not use Java, should I pick up Java on my own during this May-June-July 2024 University Holiday?

A: Yes, that is a very good idea. We will only review basic Java in the first few weeks of this course and then Prof Halim will encourage you to self-learn Java along the way.

Q: What Integrated Development Environment (IDE) that we will use in your version of CS2040/C/S?

A: The choice of IDE is "up to you but", but do check what Java-related IDEs are available in our PLs.

Q: Do I have to buy any textbook for this course?

A: Generally, no. But my CS3233 textbook: Competitive Programming book: CP4, Book 1 (get a copy legally from lulu.com (eBook) or lulu.com (physical, need shipping from overseas)) 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 ~3900+ problems in that book, near impossible to solve them all in just one semester.

Q: Can I S/U this course if I am a freshman when I take this course?

A: No, as this is a level-2 core course. CS2040/C/S has CS1010 as pre-requisite and according to Registrar's Office: "The S/U option will apply to all Level 1000 courses (with or without pre-requisites) and Level 2000 courses without other NUS courses as pre-requisites, unless otherwise stipulated by the Faculties/Departments.". So factor this information when taking this course.

Q: I heard from my friend/senior that your version of CS2040/C/S is a flipped classroom course?

A: You heard that correctly. Prof Halim and his FYP students are working hard at the background to continuously improve his 24/7 electronic clone, VisuAlgo, to be able to explain basic data structures and algorithms concepts covered in CS2040/C/S as clear as possible to first timer (and to automatically test students about these basic concepts). This will free the precious 2+1h (effective 95+45m = 140m per week to discuss the harder/deeper part of the syllabus and to do live demonstration of how those data structures and algorithms can be used to solve (real life, but sometimes fictional) programming problem. This will also help Prof Halim to scale himself (one person) to handle much larger algorithm class (CS2040/C/S are projected to be as big as of now (over 1000 students per batch) in future AYs as NUS SoC freshmen intake remains at high level — but Prof Halim feels the student intake number will plateau soon).

Q: What are the potential changes that you will apply to CS2040/C/S in S1 AY 2024/25 compared to your many earlier runs of this course?

A: NUS @ Kattis is still used. Prof Halim only plan to change these variables this time (all others are planned to be kept roughly constant):

1. From S1 AY24/25, IT5003 (Python) also starts from Week 01. That course only has 2 hours Wednesday night lecture per week instead of 2+1 = 3 hours and will end by Week 12 instead of Week 13. Prof Halim is planning to make the two courses 'as close' as possible to reduce his own workload, i.e., by synchronizing almost all Wed morning (10am-12nn XYa lecture in CS2040S) and Wed evening (6.30-8.30pm XY lecture in IT5003) to be as identical as possible. CS2040S 'extra' topics will always be scheduled on Thu morning (9-10am XYb lecture).
2. Prof Halim will try to make this course has difficulty rating in [4.0-4.1] range instead of 4.3, 4.3, 4.2, 4.2 in his last four iterations..., i.e., he is consciously making the course a bit easier, closer to IT5003 version.
3. Prof Halim had disappeared three times: on Week 04 (IOI 2024, Alexandria, Egypt), on Week 06 (ICPC World Finals 2024, Astana, Kazakhstan), and on Week 09 (ICPC Challenge Championship powered by Huawei). On all weeks, Prof Halim had been substituted by TAs.
4. Since our Thursday lecture slot is moved from 5-6pm (evening) to 9-10am (morning), Prof Halim decides to halve the duration (and thus the difficulty) of PE. The weightage of 15% PE is now reduced to 11% and the 4% is spread to midterm and the usually easier VisuAlgo Online Quizzes.

Note: This course registration section will not be prominent from Week 1 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.

News Show All

Lesson Plan Hide Past Show Past Hide Details Show Details