CS2040 - Data Structures and Algorithms (Java)

Introduction

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 rather successful and the second one was CS2040C in S2 also of this AY2017/18, which was also rather 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 20 June 2018, there are 55 students

  1. A few exchange students (let's say, 5 students?),
    As of 06 June 2018, only 1 exchange student
  2. A few incoming freshmen from AY2018/19 who have taken CS1010X under A/Prof Ben Leong this Jan-Jun 2018) 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 11 June 2018, there are 5 such students
  3. A few minor in computing students from other faculties (let's say, 10 students?),
    As of 20 June 2018, there are already 41 such students, far above my prediction :O... (20 SCI, 18 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 13 June 2018, there are only 8 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 rather 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.
    Rating
    (out of 5.0)
    (SoC avg ~4.1)
    Jun-Aug 18
    (n=??+/55)
    > 70%??
    Jan-May 18 (C)
    (n=145/173)
    84%
    Aug-Dec 17 (C)
    (n=28/37)
    76%
    Module feedback Target: 4.3+ (maintain) 4.3 (5x larger class) 4.4 (above avg :)
    Module difficulty Target: 4.0 (maintain) 4.0 (getting better) 4.1 (harder than avg)
    Steven's teaching Target: 4.5+ (maintain) 4.5 (5x larger class) 4.7 (Thanks God :)

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

    This setup is as of 20 Jun 2018, which can still change.

    Date, Time COM1 Room (#Stu/#Cap) No Tutor
    Tue+Thu, 14-15 0201-SR5 (17/18) 1 Ivan
    Tue+Thu, 15-16 One hour break - -
    Tue+Thu, 16-17 0201-SR5 (17/18) 2 Ivan
    Tue+Thu, 17-18 0201-SR5 (19/19) 3 Ivan
    1. Ivan Chew (3 groups, 2x Best Teaching Assistant Award winners); consultation hour: Wed, (?-?pm TBC) @ his office (AS6-04-27)

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

    This setup is as of 20 Jun 2018, which can still change.

    Date, Time COM1 Room (#Stu/#Cap) No Lab TA
    Tue+Thu, 14-16 B111-PL4 (17/18) 01 Steven
    Tue+Thu, 14-16 B108-PL3 (19/19) 02 Ranald
    Tue+Thu, 16-18 B108-PL3 (17/18) 03 Si Jie
    1. Dr Steven Halim (presentation only, your PSes will still be graded by Ranald and/or Si Jie, consultation hour: before his class)
    2. Ranald Lam Yun Shao (CS2040C tutorial TA in S1+S2; consultation hour: after his class)
    3. Lin Si Jie (consultation hour: before his class)
  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.

Syllabus

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 using 3 adjacent labs PL2-PL3-PL4. The date and time TBA.
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. However, since the module size for this special semester 4 is currently 54 and at most 60, a weaker form of Bell Curve system will be used instead...
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.
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 ~2850+ 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 to be rather 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 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 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 1 of S4 AY 2017/2018 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.

News

Date News

Lesson Plan

Week Lecture,
3h/session @ SR2
Tutorial,
1h/session
Lab,
2h/session
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
-02/-01,
Bef
Tue,
26 Jun
Not started, but please revise
your CS1010 (Steven assumes that all? of you
have taken 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
1a,
Tue,
26 Jun
01. Course Admin, 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),
zamka (review: function),
bookingaroom (NEW: Java class, Java Vector),
autori (NEW: Java StringTokenizer, String split)

Reminder: Read sorting e-Lecture slides before Lecture 1b
At least until slide 8-3, preferably more
Not Started Not Started PS0: A+B, not graded
Out: Mon, 25 Jun 18, 09.00am
(demo-ed during intro lecture)
1b,
Thu,
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)
NEW: HIDDEN, to be revealed on the spot
T01: Introduction,
Java OOP (basic),
Analysis,
Sorting (pt1)
tut01.pdf

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

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

04a. List ADT: LL, Stack ADT (until slide 4-7)
Focus on the harder content of SLL
Java LinkedList and Stack classes
SLLDemo.java
Intro to Stack ADT
Kattis problem discussed:
evenup (NEW: Java Stack and its usage)
T02: Sorting (pt2),
One Application,
ADT Introduction
List ADT (array/vector),
tut02.pdf
D01: Introduction,
Java Collections,
Java Vector,
Java String,
Review Java code
PS1 Preview
PS1, continued
2b
Thu,
05 Jul
04b. Queue ADT, DLL, Deque ADT (until end)
Focus on Queue, DLL, Deque
Plus a few other small LL technicalities
Java Queue and Deque interfaces
Linked List Online Quiz (medium)
Kattis problem discussed:
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
Kattis problem discussed:
numbertree (reversed Binary Heap indexing, NEW: << bit shift operator)
No tutorial,
Ivan is not available
D02: Java OOP
List ADT (vector),
Implement this,
A sorting challenge,
VA OQ demo (sorting),
PS2: Guessing Game
Out: Thu, 05 Jul 18, 11.15am

PS1
Due: Thu, 05 Jul 18, 01.59pm
(3%)
3a,
Tue,
10 Jul
05b. Priority Queue (PQ) ADT: Binary Heap (until end)
Java PriorityQueue class
BinaryHeapDemo.java
Binary Heap Online Quiz (medium)

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, will be changed):
greedilyincreasing (Java/growing list/vector),
synchronizinglists (sort/binary search/re-mapping),
server (FIFO/queue/or just on-the-fly computation)
T03: List ADT,
Linked List Review,
Stack/Queue ADT,
Deque ADT,
Applications
tut03.pdf

Midterm test is
up to end of T03
D03: PS1 Debrief,
Java LinkedList,
Java Stack class,
Java Queue interface,
PS2 Discussion,
Implementation Demo,
VA OQ demo (list)
Midterm preparation
PS2, continued
3b,
Thu,
12 Jul
Past Papers Discussion (first 1 hour):
CS2040C-2017-18-S1-midterm-medium.pdf (PS: 22 Sep 2017 was a Friday).
CS2040C-2017-18-S2-midterm-medium.pdf.

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...
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,
PQ ADT,
tut04.pdf

D04: Java PriorityQueue,
Max-Min conversion,
BinaryHeapDemo,
Solve UVa 01203,
PS3: Scheduling Deliveries
Out: Thu, 12 Jul 18, 11.15am

PS2
Due: Thu, 12 Jul 18, 01.59pm
(3%)
Virtual mid-point of the Special Semester (no Recess Week though :O)
4a,
Tue,
17 Jul
07. Table ADT part 1: Hash Table
Java HashSet/HashMap classes
HashTableDemo.java
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,
tut05.pdf
D05: PS2 Debrief (short),
PS3 Discussion,
VisuAlgo OQ demo (heap),
Java HashSet,
Java HashMap,
Mock PE 1:
TBA
PS3, continued
4b,
Thu,
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,
tut06.pdf
D06: Java TreeSet,
Java TreeMap,
Indexing demo,
VA OQ demo (hashtable),
Mock PE 2:
TBA
PS4: Baby Names
Out: Thu, 19 Jul 18, 11.15am

PS3
Due: Thu, 19 Jul 18, 01.59pm
(3%)
5a,
Tue,
24 Jul
09. Graph Data Structures + Simple Applications
CS1231 happens to be not a pre-req of CS2040/C
so I will play safe by reviewing a bit of CS1231 (graph topic) first
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
tut07.pdf
D07: PS3 Debrief,
PS4 Discussion,
Graph DS conversions,
VA OQ demo
(bst/avl, graphds),
Mock PE 3:
TBA
PS4, continued
5b,
Thu,
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:
reachableroads (DFS, count #CC),
runningmom (AL of strings; DFS; back edge detection)
T08: Some Graph Properties,
(CS1231 short review),
Conversion exercises,
Modeling exercise 1,
DFS/BFS Review
tut08.pdf
D08: PE (12%)
Date: This day
Timing: Lab timing
Venue: PL2-3-4 :O
Capacity: 80+ seats (PCs)
Other details TBA
PS5: The Onset of Labor
Out: Thu, 26 Jul 18, 11.15am

PS4
Due: Thu, 26 Jul 18, 01.59pm
(3%)
6a,
Tue,
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, Floodfill, Toposort++,
Modeling exercise 2,
tut09.pdf
D09: PS4 Debrief,
PS5 Discussion,
VA OQ demo run (all)
Mock Final Assessment:
TBA
PS5, continued
6b,
Thu,
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 (preview of log(a*b*c) to log(a)+log(b)+log(c) transformation)
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, will be changed):
conformity (< 3 pointer previously, map of set to int frequencies),

Final Assessment Consultations (per request)
Written Quiz 2 Past Papers (from other relevant modules,
notice that the syllabus have changed!):
CS2010-2011-12-S1-WQ2-medium.pdf,
CS2010-2012-13-S1-WQ2-medium.pdf,
CS2010-2013-14-S1-WQ2-medium.pdf,
CS2010-2014-15-S1-WQ2-medium.pdf,
CS2010-2015-16-S1-WQ2-medium.pdf.
Final Assessment Past Papers (from other relevant modules,
notice that the syllabus have changed!):
CS2010-2011-12-S1-final.pdf,
CS2010-2012-13-S1-final.pdf,
CS2010-2013-14-S1-final.pdf,
CS2010-2014-15-S1-final.pdf,
CS2010-2015-16-S1-final.pdf.
Final Assessment Past Papers:
CS2040C-2017-18-S1-final.pdf,
CS2040C-2017-18-S2-final.pdf.
T10: BFS, Bellman Ford's,
Dijkstra's Review,
Modeling exercises 3,
tut10.pdf
D10: VA OQ (12%)
(URL: this)
'CS2040/C Quiz'
All in CS2040/C
19+1 hard Qs,
Time: 30m,
Other details TBA
PS5
Due: Thu, 02 Aug 18, 01.59pm
(3%)
Final Assessment (40%)
Date and Time: Fri, 03 Aug 2018, (1-3) PM
Venue: TBA (likely 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 by 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 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 submission each
  6. Guessing Master (#): Given to the first 7 students who solve all subtasks of PS2
  7. PS2 Marksman (#): Given to the first 7 students who can solve all PS2 subtasks with just one submission 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 students who can solve all PS3 subtasks with just one submission each
  11. Naming Master (#): Given to the first 7 students who solve all subtasks of PS4
  12. PS4 Marksman (#): Given to the first 7 students who can solve all PS4 subtasks with just one submission each
  13. Taxi Driver (#): Given to the first 7 students who solve all subtasks of PS5
  14. Competitive Programmer to be (#): Given to the first 7 students who can solve all PE subtasks under that stressful environment.
  15. Chow-Yuan-Bin Award (#): Given to the top students from each lab group 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)
  16. PS5 Marksman (#): Given to the first 7 students who can solve all PS5 subtasks with just one submission each
  17. Nowhere to Hide (Reason): Given to students who already remembered by Steven; 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 (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 Student Name Achievements