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.
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)
Some other facts:
Rating (out of 5.0) (SoC avg ~4.1) |
Jun-Aug 18 (n=~27+/38) > 70%?? |
Jan-May 18 (C) (n=145/173) 84% |
Aug-Dec 17 (C) (n=28/37) 76% |
---|---|---|---|
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 |
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 |
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 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 |
---|
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 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 |
1a, Tue, 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) |
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) dyslectionary (sortofsorting+lineup+raggedright) |
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: (Single) LL (until slide 3-22) Introduction of List ADT and SLL operations Java LinkedList class SLLDemo.java |
T02: Sorting (pt2), One Application, ADT Introduction, List ADT (array/vector), PS1 Discussion tut02.pdf |
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 |
2b Thu, 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 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) 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, Applications, PS2 Discussion tut03.pdf 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 |
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 (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), PQ ADT tut04.pdf |
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) 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, PS3 Discussion tut05.pdf |
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 |
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 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 PS3 Due: Thu, 19 Jul 18, 01.59pm (3%) |
5a, Tue, 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 tut07.pdf |
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 |
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: 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 tut08.pdf |
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) 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, Toposort++, Floodfill/CC, Modeling exercise 2, PS5 Discussion tut09.pdf |
D09: PS4 Debrief, PE Debrief, PS5 "full" Discussion, VA OQ demo run (all), Hands-on 8: wheresmyinternet (easy DFS/BFS reachability test) |
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 (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!): 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, CS2010-2015-16-S4-midterm-hard.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. CS2010-2015-16-S4-final.pdf. CS1020E-2016-17-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, Photo taking (Ivan's last), tut10.pdf, (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%) |
PS5 Due: Thu, 02 Aug 18, 01.59pm (3%) |
Final Assessment (40%) Date and Time: Fri, 03 Aug 2018, 2.30-4.30 PM Venue: COM1-2-SR1 (near our own lecture room) |
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).
N | T | L | FAC | Student Name | Achievements |
---|