CS2040 - Data Structures and Algorithms (Java)

Prof Halim is no longer teaching CS2040.
He is teaching CS2040S in Sem 1 instead.
This page below is very outdated.


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 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.

Course Registration

This is the third time Steven runs CS2040/C (the first one was CS2040C in S1 of this AY2017/18, which was successful and the second one was CS2040C in S2 also of this AY2017/18, which was also successful). Steven is currently planning to use ~90% similar setup as with the S1+S2 version of CS2040C, with only one expected change: The switch of programming language from C++ in CS2040C to Java in CS2040.

The quota of this class for S4 AY2017/18 (Special Semester 2) is 60 students. This is far smaller than 173 that I worked with in S2 and bigger than 37 that I worked with in S1. The estimated student demographics (as per May 2018) are as follows (the updated numbers are refined nearing the start date and highlighted with red font):
As of 10 July 2018, the final number of students is 38 students (can no longer drop without penalty)

  1. A few exchange students (let's say, 5 students?),
    As of 10 July 2018, back to 0 exchange student
  2. A few incoming freshmen from AY2018/19 who have taken CS1010(X) or will be exempted from CS1010 (e.g. SGP NOI Gold/Silver medalists but not the IOI ones, or Polytechnic students, let's say, 5 students?),
    As of 10 July 2018, there are only 3 such students
  3. A few minor in computing students from other faculties (let's say, 10 students?),
    As of 10 July 2018, there are 29 such students, far above my prediction :O... (15 SCI, 11 ENG, and 3 ART students)... This group actually forms the majority of the class roster
  4. The rest will be mostly going-to-be-year-2 students (current freshmen from AY 2017/18) who want to catch up with their peers.
    As of 10 July 2018, there are only 6 such students, far lower than my prediction :O...

Some other facts:

  1. Steven has just taught the first two iterations of CS2040/C in S1 and S2 of this AY2017/18.
    Steven uses flipped classroom, machine-teach-(and-auto-test)-students, and in-class live discussion of (hard)er problems.
    Both iterations were successful.
  2. Steven has taught other similar modules: CS2020 once (2011), CS2010 six times (2011-2016), CS1020E once (2016), and the 99% clone CS2040C twice (2017-2018).
  3. Teaching staffs:
    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used very extensively in this module.
    (out of 5.0)
    (SoC avg ~4.1)
    Jun-Aug 18
    > 70%??
    Jan-May 18 (C)
    Aug-Dec 17 (C)
    Module feedback 4.4 (S1 level) 4.3 (5x larger) 4.4 (> avg :)
    Module difficulty 4.2 (Sp Sem) 4.0 (better) 4.1 (> avg :O)
    Steven's teaching 4.8 (Thx God :) 4.5 (5x larger) 4.7 (> avg :)

    Tutorial Teaching Assistants (3 tutorial sessions, sorted chronologically):

    Date, Time COM1 Room (#Stu/#Cap) No Tutor
    Tue+Thu, 14-15pm 0201-SR5 (10) 1 Ivan
    Tue+Thu, 15-16pm One hour break - -
    Tue+Thu, 16-17pm 0201-SR5 (16) 2 Ivan
    Tue+Thu, 17-18pm 0201-SR5 (12) 3 Ivan
    1. Ivan Chew (3 groups, 2x Best Teaching Assistant Award winners); consultation hour: Wed, 5.30-7.30pm @ COM1-0204 (SR2), mostly catered for anyone who needs urgent help before Thu 1.59pm PS deadlines, Ivan have been given liberty to pour (algorithmic) hints if needed

    Laboratory Teaching Assistants (3 laboratory sessions, sorted chronologically, note that Group 01+02 have parallel time slot):

    Date, Time COM1 Room (#Stu/#Cap) No Lab TA
    Tue+Thu, 14-16pm B111-PL4 (15) 01 Steven
    Tue+Thu, 14-16pm B108-PL3 (13) 02 Ranald
    Tue+Thu, 16-18pm B108-PL3 (10) 03 Si Jie
    1. Dr Steven Halim (presentation only, your PSes will still be graded by Ranald and/or Si Jie, consultation hour: 13-14pm (before his class) at COM1-Basement, for anyone (no Tutorial/Lab Demo at 1-2pm yet))
    2. Ranald Lam Yun Shao (CS2040C tutorial TA in S1+S2; consultation hour: 16-17pm (after his class) at COM1-Basement, mostly catered for people who will attend either Steven's or Ranald's Lab Group 01/02 at 14-16pm and will attend Tutorial Group 3 at 17-18pm (~12 students))
    3. Lin Si Jie (consultation hour: 15-16pm (before his class) at COM1-Basement, mostly catered for people who will attend Tutorial Group 1 at 14-15pm and will attend Si Jie's Lab Group 3 at 16-18pm (~10 students))
  4. Have you passed (or exempted from) CS1010 (or its variants)? You have to...
  5. Have you taken CS1020/CS1020E/CS2010/CS2020? You cannot take CS2040/C if you have taken similar/older module(s) that have huge degree of overlap with this new module.


This is what you will learn if you take CS2040/C taught by Steven:

Course Registration Additional FAQ

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.

Q: Will there be a practical exam/coding test for CS2040?
A: Yes, once only, at Week 05, nearing the end of the semester, after sufficient practices in Lab Demos and PSes. This time (Special Semester 4), we will use full controlled PE setup. PE will be conducted during Lab Session of Week 05b.
Q: Will this module be graded using Bell curve?
A: The magic number is 40. If there are more than 40 students for this special semester 4 class, yes. Otherwise, no. Since many (17 :O) students dropped this module after the 2 free viewing sessions, the module size for this special semester 4 is currently 38, so NO Bell Curve system will be used...
Q: I am from CS1101S (JavaScript)/CS1010S (Python)/other modules that do not use Java, should I pick up Java on my own during this mid May-mid June 2018?
A: Yes, that is a good idea. We will only review basic Java in the first week of this special semester module and then Steven will encourage you to self-learn Java along the way.
Q: What Integrated Development Environment (IDE) that we will use in CS2040/C?
A: The choice of IDE is entirely up to you. But note that we will have Practical Exam (PE), so try to be familiar with the Java programming tools what we have in our various PLs, e.g. IntelliJ, Eclipse, NetBeans, any text editor (e.g. Notepad++) with javac compiler, etc.
Q: Do I have to buy any textbook for this course?
A: Generally, no. But my Competitive Programming book, the 3.17b edition (actually for CS3233) 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 ~2900+ problems in that book (CP3.17b) and the next full edition (CP4) with more challenging problems is in the pipeline... :D.
Q: Can I S/U this module if I am a freshman when I take this module?
A: I don't think so, as this is a level-2 core module. CS2040/C has CS1010 as pre-requisite and according to Registrar's Office: "The S/U option will apply to all Level 1000 modules (with or without pre-requisites) and Level 2000 modules without other NUS modules as pre-requisites, unless otherwise stipulated by the Faculties/Departments". So factor this information when taking this module during your freshmen year.
Q: I heard from my friend/senior that this CS2040/C under Steven is a flipped classroom module?
A: You heard that correctly. Steven is working hard at the background to improve his 24/7 electronic clone, VisuAlgo, to be able to explain basic data structures and algorithms covered in CS2040/C as clear? (that's debate-able) as possible to first timer. This will free the precious 2x1.5h (effective 2x75m = 150m 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 Steven to scale himself (one person) to handle much larger algorithm class (CS2040/C are projected to grow bigger in future AYs when the CS1020+CS2010 route is fully closed). The first year of experiment was conducted with 37 students in S1 plus 173 students in S2. Both seem were successful.
Q: What are the potential changes that you will apply to CS2040 in S4 compared to CS2040C in S1+S2 version (that I heard from my friend/senior)?
A: These are the potential changes:
  1. The pace is 2+ times faster as we compress 13 teaching weeks (without recess and study week :O) into 6 in this special semester :O
  2. The programming language is changed from C++ to Java :O. Steven will likely keep his demo Kattis problems (mostly) the same, just that this time he will solve them in Java, live... Steven will include his C++ file too (for comparison purpose)
  3. PS deadline will be once every week :O (it is per two weeks in normal semester)
  4. Another round of enhancement to various VA e-Lecture slides so that Steven receives even less 'basic' question than the already low number in S1+S2, including adding a few more example code and self-check MCQs for earlier e-Lectures; Indonesian and Chinese translation for CS2040 topics will be made ready before the actual lecture; print-friendly format will be also made ready
  5. All others are planned to be kept roughly constant as in CS2040C of S2 version as Steven wants to have a flipped classroom module that has been proven to work in S1+S2 for CS2040C to be versatile enough to handle differences in two programming languages (C++ and Java)

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


Date News

Lesson Plan

Week Lecture,
3h/session @ SR2
Interesting Problem Set
Per One Week
@ Home
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
26 Jun
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 Java specific instructions @ Kattis,
and solve these optional OJ problems
by yourself (CS1010 level):
hello (revise Java simple O of I/O)
judgingmoose (revise simple I/O, simple if-else)
timeloop (revise simple I/O, simple for-loop)
mia (revise simple function, another if-else)
Not Started Not Started Not Started
26 Jun
01. Course Admin, (Re-)Introduction to Java
Setting the tone for a flipped classroom module
VisuAlgo + Mooshak + this Private IVLE + Kattis (NUS) + Kattis (open)
Basic Java review/new feature introduction
Kattis problems discussed:
statistics (revise I/O, control flow: repetition, selection),
treasurehunt (revise (2D character) array, (recursive) function),
autori (NEW: Java StringTokenizer, String split),
zamka (review: function),
bookingaroom (NEW: Java class (overkill actually), Java Vector),
raggedright (last minute addition for mini sprint coding challenge)

Reminder: Read old CS1020/E lecture note on algorithm analysis
and sorting e-Lecture slides (until slide 8-3 or more) before Lecture 1b
Not Started Not Started PS0: A+B, not graded
Out: Mon, 25 Jun 18, 09.00am
(demo-ed during intro lecture)
28 Jun
02. Analysis of Algorithms
(old CS1020/E lecture note on this topic will be digitised later)
Kattis problems discussed:
(several previous problems, with analysis)

03a. Sorting (until slide 8-3)
Java Collections.sort
Kattis problems discussed:
mjehuric (bubble sort simulation),
lineup (NEW: Java Collections.sort, Collections.reverse),
sortofsorting (NEW: custom comparator)
dyslectionary (sortofsorting+lineup+raggedright)
T01: Introduction,
Java OOP (basic),
Sorting (pt1)

Started early
Not Started PS1: Continuous Median
Out: Thu, 28 Jun 18, 11.15am
It is at Mooshak OJ system
Use SoC WebVPN
or force HTTPS at Mooshak's URL
if you are outside campus

"due": Thu, 28 Jun 18, 01.59pm
not graded
03 Jul
03b. Sorting (until end)
Focus on the harder content of sorting e-Lecture
Sorting Online Quiz (medium)

04a. List ADT: (Single) LL (until slide 3-22)
Introduction of List ADT and SLL operations
Java LinkedList class
T02: Sorting (pt2),
One Application,
ADT Introduction,
List ADT (array/vector),
PS1 Discussion
D01: Introduction,
Java Collections,
Java ArrayList (ignore Vector),
Java String,
Review Java code (so far)
PS1 Discussion
Hands-on 1: classy
(sortofsorting/dyslectionary, autori++,
somewhat reading comprehension)
PS1, continued
05 Jul
04b. Stack/Queue/Deque ADT (DLL) (until end)
Focus on Stack, Queue, DLL, Deque
Plus a few other small LL technicalities
Java Stack class and Java Queue and Deque interfaces
Linked List Online Quiz (medium)
Kattis problem discussed:
evenup (NEW: Java Stack and its usage)
integerlists (NEW: Java LinkedList, use both sides)

05a. Priority Queue (PQ) ADT: Binary Heap (until slide 6)
Review of basic ideas of PQ ADT and basic Binary Heap structure
No tutorial,
Ivan is not available
D02: Java OOP
List ADT (ArrayList),
Implement this,
A sorting challenge,
VA OQ demo (sorting),
Hands-on 2: throwns
(use Stack for its LIFO behavior)
PS2: Guessing Game
Out: Thu, 05 Jul 18, 11.15am

Due: Thu, 05 Jul 18, 01.59pm
10 Jul
05b. Priority Queue (PQ) ADT: Binary Heap (until end)
Java PriorityQueue class
Binary Heap Online Quiz (medium)
Kattis problem discussed:
numbertree (reversed Binary Heap indexing, NEW: << bit shift operator)

06. Application 1 - Java/Arrays/Vectors/Sorting/Lists/PQs
Mock Midterm Test :O, can be a major wake up call...,
This is a kind of CS2040/C review so far,
Kattis problems discussed (S2 version, for self exercise):
greedilyincreasing (Java/growing list/vector),
synchronizinglists (sort/binary search/re-mapping),
server (FIFO/queue/or just on-the-fly computation)
Kattis problems discussed (S4 version):
froshweek (something D&C)
pivot (n^2 TLE)
T03: List ADT,
Linked List Review,
Stack/Queue ADT,
Deque ADT,
PS2 Discussion

Midterm test is
up to end of T03
D03: PS1 Debrief,
Java LinkedList,
Java Stack,
Java Queue,
Java PriorityQueue,
PS2 Discussion,
Implementation Demo,
VA OQ demo (list)
Hands-on 3: rationalsequence2
('extension' of 'numbertree')

Midterm test is
up to end of D03
PS2, continued
12 Jul
Past Papers Discussion (first 1 hour):
CS2040C-2017-18-S1-midterm-medium.pdf (PS: 22 Sep 2017 was a Friday).

Midterm Test (15%)
During our lecture time, 10.00-11.40am (100m)
Material: Up to L05b (a bit of PQ), T03, and D03
Open book (no restriction), just no electronic devices (except standard calculator)
For the question paper and modal answer (see IVLE after test)
Venue: SR2, our lecture venue

NUS SoC Commencement on Fri 13 July 2018
T04: Midterm
Test Solutions (algorithm),

D04: Midterm
Test Solutions (code)
Max-Min conversion,
BinaryHeapDemo review,
VisuAlgo OQ demo (heap),
Hands-on 4: backspace
(easy problem to cheer you all up =)
PS3: Scheduling Deliveries
Out: Thu, 12 Jul 18, 11.45am
(after midterm test is over)

Due: Thu, 12 Jul 18, 01.59pm
Virtual mid-point of the Special Semester (no Recess Week though :O)
17 Jul
07. Table ADT part 1: Hash Table
Java HashSet/HashMap classes
Hash Table Online Quiz
Kattis problems discussed:
oddmanout (assume G = 100 000 codes; map code to f; find only code with f == 1),
whatdoesthefoxsay (assume there are 10 000 animals; string hashing)
T05: Midterm
Test Debrief,
More Binary Heap,
PS3 Discussion
D05: PS2 Debrief (short),
PS3 Discussion,
Java HashMap,
Java HashSet,
VisuAlgo OQ demo (hashtable),
Hands-on 5: cd
(showing > 1 ways to solve this classics)
PS3, continued
19 Jul
08. Table ADT part 2: Binary Search Tree, AVL Tree
Java TreeSet/TreeMap classes
BSTDemo.java and AVLDemo.java
BST Online Quiz (medium, including AVL)
Kattis problem discussed:
baconeggsandspam (assume n = 5 000 customers)
T06: Table ADT 1 - unordered,
Hashing concepts,
Hash Table issues,
D06: Java TreeMap,
Java TreeSet,
Indexing demo,
VA OQ demo (bst,avl),
Hands-on 6: PE S1-easier
(to iron out technical glitches)
PS4: Baby Names
Out: Thu, 19 Jul 18, 11.15am

Due: Thu, 19 Jul 18, 01.59pm
24 Jul
09. Graph DS + Simple Applications (slide 1 until end)
Graph DS Online Quiz (medium)
No built-in Java API
see ch2_07_graph_ds.java in ch2.zip of CPbook website
Kattis problem discussed:
flyingsafely (for a 30s jaw-dropping moment)

10a. Graph Traversal + Simple Applications (until slide 6-4)
DFS/BFS Online Quiz (easy)
No built-in Java API
see ch4_01_dfs/ch4_02_UVa00469/ch4_04_bfs.java in ch4.zip of CPbook website
T07: Table ADT 2 - ordered,
BST/AVL advanced stuffs,
PQ ADT alternative implementation,
Comparison with Table ADT 1,
unordered vs ordered,
PS4 Discussion
D07: PS3 Debrief,
PS4 Discussion,
Graph DS conversions,
Simple DFS/BFS demo,
VA OQ demo (graphds),
Hands-on 6 Debrief,
Hands-on 7: PE S2-harder
(to show the *real* PE level)
PS4, continued
26 Jul
10b. Graph Traversal continued (just slide 7)
(we skip slide 8-12, out of CS2040/C scope)
Graph DS + DFS/BFS Online Quiz (medium)
Kattis problems discussed:
countingstars (floodfill, DFS, count #CC),
reachableroads (DFS, count #CC; skipped),
runningmom (AL of strings; DFS; back edge detection)
faultyrobot (make up PE S2)
T08: Some Graph Properties,
(CS1231 short review),
Conversion exercises,
Modeling exercise 1,
DFS/BFS Review
D08: PE (12%)
Date: This day
Timing: Normal Lab Timing (2h)
Venue: PL3+4
PS5: The Onset of Labor
Out: Thu, 26 Jul 18, 06.15pm
(after PE)

Due: Thu, 26 Jul 18, 01.59pm
31 Jul
11a. Single-Source Shortest Paths (SSSP) Problem:
Bellman Ford's, BFS, Dijkstra's (original)
(until slide 7-5)
No built-in Java API,
see ch4_06_bellman_ford/ch4_05_dijkstra.java in ch4.zip of CPbook website
Kattis problem discussed:
hidingplaces (BFS demo; implicit graph demo)
shortestpath1 (that Dijkstra's implementation is easy)
T09: DFS/BFS advanced stuffs,
Cycle, Toposort++, Floodfill/CC,
Modeling exercise 2,
PS5 Discussion
D09: PS4 Debrief,
PE Debrief,
PS5 "full" Discussion,
VA OQ demo run (all),
Hands-on 8: wheresmyinternet
(easy DFS/BFS reachability test)
PS5, continued
02 Aug
11b. SSSP continued: Modified Dijkstra's (exposure only),
On Tree, On DAG
(until end),
SSSP Online Quiz (hard),
(last preparation for VisuAlgo Online Quiz),
Kattis problems discussed:
shortestpath1 (modified Dijkstra's implementation, exposure only),
getshorty (shelved in Sp Sem 4 to focus on other things)
Closed with a few minutes of semester summary (last lecture),
followed with review of what can be done better for future iterations...

12. Application 2 (Mock Final) - Tables/Trees (Heap/bBST)/Graphs
Last Mock Final Assessment :O:
Kattis problem discussed (S2 version, for self exercise):
conformity (< 3 pointer previously, map of set to int frequencies),
Kattis problems discussed (S4 version):
brexit (chain reaction)

Final Assessment Consultations (per request)
Written Quiz 2 Past Papers (from other relevant modules,
notice that the syllabus have changed!):
Final Assessment Past Papers (from other relevant modules,
notice that the syllabus have changed!):
Final Assessment Past Papers:
T10: BFS, Bellman Ford's,
Dijkstra's Review,
Modeling exercises 3,
Photo taking (Ivan's last),

(Participation Marks, 3%)
D10: First hour:
PS5 (Rough) Debrief,
Hands-on 9: crosscountry
(simple sssp)
Photo taking

VA OQ (12%)
(URL: this)
'CS2040/C Quiz'
All in CS2040/C
19+1 hard Qs,
Time: 30m,
Max 2 runs,
The last one count

(Participation Marks, 3%)
Due: Thu, 02 Aug 18, 01.59pm
Final Assessment (40%)
Date and Time: Fri, 03 Aug 2018, 2.30-4.30 PM
Venue: COM1-2-SR1 (near our own lecture room)

Class Roster

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).

  1. I Say Hi: Given to first 7 (actually 8) students who reply Steven's welcome email -- (sent on Thu, 07 Jun 2018); Any early feedback will help Steven in refining the preparation of the 'special' version of this module --- First 7+1 email/FB replies are received by 07 Jun 2018, 4.15pm; the rest can still continue replying to further improve my understanding of the class dynamics of this special semester class
  2. Ready to Start: Given to as many students who have completed THREE pre-first-class admin setup work (closed one day before the first class on Tue, 26 Jun 2018, 09.00am):
    1). (Create a legit or just-dummy free Facebook account and) Join CS2040C FB group,
    2). Register a free trackable VisuAlgo account, activate it, and open at least one VisuAlgo page, e.g. Sorting e-Lecture,
    3). Register a free trackable NUS-Kattis account and has AC-ed at least 1 of the 4 warm-up tasks.
  3. Kiasu (#): Given to the first 7 students who solve all subtasks of PS0, albeit that it is 'optional' and 'not graded'
  4. Balance Master (#): Given to the first 7 (down to 5) students who solve all subtasks of PS1, the first graded PS of CS2040/C
  5. PS1 Marksman (#): Given to the first 7 students who can solve all PS1 subtasks with just one or at most two submission(s) each
  6. Guessing Master (#): Given to the first 7 students who solve all subtasks of PS2
  7. PS2 Marksman (#): Given to the first 7 (only 6) students who can solve all PS2 subtasks with just one or at most two submission(s) each
  8. Potential TA: Given to top 7 highest scorers in the Midterm Test: You survived all those intellectual challenges...
  9. Scheduling Master (#): Given to the first 7 students who solve all subtasks of PS3
  10. PS3 Marksman (#): Given to the first 7 (only 1) student(s) who can solve all PS3 subtasks with just one or at most two submission(s) each
  11. Naming Master (#): Given to the first 7 students who solve all subtasks of PS4
  12. PS4 Marksman (#): Given to the first 7 (only 5) students who can solve all PS4 subtasks with just one or at most two submission(s) each
  13. Competitive Programmer to be (#): Given to the first 7 (only 6) students who can solve all PE subtasks under that stressful environment
  14. Taxi Driver (#): Given to the first 7 students who solve all subtasks of PS5
  15. PS5 Marksman (#): Given to the first 7 (only 2) students who can solve all PS5 subtasks with just one or at most two submission(s) each
  16. Chow-Yuan-Bin Award (#): Given to the top students from each lab group (only 3 scored 20/20) who scored the highest (and if ties, by fastest submission time as acknowledged by Lab TA) in CS2040/C final Online Quiz using machine: VisuAlgo (before the actual Final Assessment set by a human); Note: students who need second attempt will not get this achievement
  17. Nowhere to Hide (Reason): Given to students who already remembered by Steven (closed one day before final assessment); These students can choose to hide their matric cards during CS2040/C official assessments and Steven will allow them to do so
  18. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 200.0 Kattis points or higher at some point during the execution of CS2040/C in S4 AY 2017/18 (closed one day before final assessment) (submitting all my AC demo code will only give you about ~50.0 free Kattis points so you must have done a lot more extra homework than necessary; PS: This is my account)
N T L FAC Student Name Achievements