World of Seven - CS3233 (original) (raw)
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
-06/-05/
-04/-03/
-02/-01
As many pages from CP4 Book 1+2; at least from preface up to the end of Chapter 4 (the entire Book 1 basically); Note: For the actual semester, you must have a(n electronic) copy of CP4 (both book 1+2) to go through this course successfully; if you don't already have both books, go to lulu.com to get a (legit) copy.
Lots of preparatory work especially for those who do not have competitive programming background yet
Optional Kattis set #00 starts on Monday, 06 Jan 2025, 21:00 SGT
No contest yet; But if you are not a multi-lingual programmer yet, pick up both C++17 (main), Python3 (secondary), and Java17 (tertiary) by yourself during holiday time
At home: Set up a (free) Codeforces account, then use Dec24+early Jan25 holiday (~3-4 weeks) to get ≥ 1299 rating in CodeForces and/or set up a (free) Kattis (open) account, then get ≥ 500.0 points (~250 AC of ~2 pointer problems, see first ~3+ pages sorted based on Kattis difficulty ratings :O), use Prof Halim's classification here) in Kattis by Tue, 31 Dec 24, 23:59 (or MUCH earlier) to ensure course acceptance, familiarize yourself with Ubuntu 22 LTS with GNOME desktop, or self-read the older teaching materials in this public website
01
13 Jan
Preface to Chapter 1 (all pages) plus simple Ad Hoc problems in Chapter 2+3+9
Optional Kattis set #00 due
The official Kattis set #01 starts
Mock
Ad Hoc
(after first lecture)
Let's Talk CP
Introduction; Brief Course Admins; Focus on delivering some "Wow Moments"; A Bit of C++17, Python3, Java17, Mock/Preview Contest (not graded, but has high standard)
02
20 Jan
Chapter 2; Focus on Section 2.2 and 2.4.3
Read the rest of Chapter 2 by yourself
Solve Mock 01 B/C
HW01 due
Kattis set #01 due
and Kattis set #02 starts (we repeat this pattern until Set #12)
Mini 01
O(n1.5) Algorithms
Money Contest
funded by
NUS ICPC endowment
Be A Librarian
Mastery of Libraries (C++ STL, Python Standard Library, & Java API); Focus on Bit Manipulation and Binary Indexed (Fenwick) vs Segment Tree
VisuAlgo: bitmask, ufds, fenwicktree (optional), and segmenttree
Decision to Drop CS3233/R without penalty by Fri, 24 Jan 25 (this time you can self-drop, but do inform Prof Halim first; hopefully we have 'no-one-drop-by-week-02' whenever possible)
03
27 Jan
Chapter 3, 4, 8, and 9;
Focus on Section 3.1-2, 4.2.3, 4.4.2-3, 8.1-8.2, 8.6 (some NP-hard/complete problems with complete search solution), 9.20, and 9.21;
Read Section 3.3 (DnC) too, especially about BSTA
Solve Mini 01 B/C
HW02 due
Kattis set #02 due
Mini 02
Libraries
Money Contest
funded by
NUS ICPC endowment
(Binary) Searching for Answers
Iterative Techniques (the fancier ones); Recursive Backtracking (bitmask-based, reverse thinking, data compression, etc); State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra's) with Meet in the Middle (Bidirectional Search); and finally, what if we can 'guess' the answer in Binary Search fashion?
This AY 2024/25, CNY does *not* affect CS3233
CNY Eve (Reunion Dinner): 28 Jan 2025 PM (Tue)
Day 1: 29 Jan 2025 (Wed)
Day 2: 30 Jan 2025 (Thu)
04
03 Feb
Chapter 3, 4, 5, 6, 8, and 9;
Focus on Section 3.5, 4.6.1, 5.4, 5.5, 5.8, 6.3, 8.3, 8.5, 8.6 (some NP-hard/complete problems with DP solution), 9.3, 9.7, and 9.29
Read Section 3.4 (Greedy) too
HW03 due
Solve Mini 02 B/C
Kattis set #03 due
Mini 03
Complete/Binary Search
Money Contest
donated by
HRT
The Art of Stenography (or Being Greedy)
Dynamic Programming; "Instant" review of CS3230/CS4234 DP Materials; Focus on relationship between DP and DAG; Discussion of a few non-classic DP examples; Formulating non trivial DP states + transitions; DP vs greedy algorithm comparisons on some problems
HRT class visit
Mon, 03 Feb 2025, dinner provided from 4.30-5.25pm
Assemble at COM1-Basement by 4.30pm (FCFS)
05
10 Feb
Chapter 8 and 9; Focus on Section 8.4, 9.24, and 9.25; Optional: Read the Max-Flow material of CS4234
*short* HW04 due
Solve Mini 03 B/C
Kattis set #04 due
Mini 04
DP or Greedy
Money Contest
Optiver
How to Prevent Flood?
Quick overview of Network Flow; Quick review of Ford-Fulkerson Max Flow algorithm variants: Edmonds-Karp and especially Dinic's (short comparison with Push-Relabel);
Focus on Flow Graph Modeling skill and applications
VisuAlgo: maxflow
Optiver class visit
Mon, 10 Feb 2025, dinner provided from 4.30-5.25pm
Assemble at COM1-Basement by 4.30pm (FCFS)
06
17 Feb
Chapter 4 and 8; Focus on Section 4.6 (Bipartite Graph) and 8.5;
Then read Section 9.26, 9.27, 9.28, 9.29;
We postpone Graph Matching in special cases of NP-hard problems (8.6) to Week 09
HW05 due
Solve Mini 04 B/C
Kattis set #05 due
Mini 05
Graph1: Network Flow
Money Contest
donated by
Jane Street
(PS: We do midterm team contest formation outside class time via class Discord after Mini 05 so that you can practice as a team over Wk6 and/or recess week)
Career Development Network, see Hall of Fame
Quick overview of Graph Matching; Unweighted MCBM; Greedy Bipartite Matching, Focus on (Bipartite) Graph Modeling skill and applications; Quick Discussion on Weighted MCBM (Kuhn-Munkres/Hungarian algorithm); Review of DP bitmask for Graph Matching (any variant, but on small graph) -- (Edmonds' Matching algorithm shelved)
VisuAlgo: maxflow, matching
Jane Street class visit
Mon, 17 Feb 2025, dinner provided from 4.30-5.25pm
Assemble at COM1-Basement by 4.30pm (FCFS)
Additionally, we will extend the class to 9.15pm tonight
Discover Citadel & Citadel Securities (Singapore)
Fri, 21 Feb 2025 (by invitation only)
NOI 2025 Competition is this Sat, 22 Feb 2025
(online qualification contest, onsite for potential EGOI25 participants)
Recess
24 Feb
No class
Kattis set #06,
continued
No class
Although we are not supposed to have any face to face activity this week, nobody prevents you to keep solving Kattis problems (KS06 or more) 'by yourself' (or as a team of three) :). Again, peruse Prof Halim's classification here, this time probably aiming for the 3-4+ pointer problems...
Prof Halim and his (international) organizing (host/judge/technical) team organized the second ICPC Asia Pacific Championship, 27 Feb-02 Mar 2025
It went well and NUS team Jägermeister clinched 2nd place (gold medal)
Decision to Drop CS3233/R with 'W' grade by Sun, 02 Mar 25
07
03 Mar
Re-read Week 01-06 reading materials and CS1020/2040/C/S stuffs;
Re-read "standard" CS2040/C/S graph topics by yourself (Section 4.1-4.6)
Week01-06 + CS2040/C/S
5.15-9.45pm (4.5h)
Money Contest
funded by
NUS ICPC endowment
No lecture, we do Midterm Team Contest
VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp
Midterm Team Contest (recent 3 AYs only):
Midterm Team Contest (28 Feb 22)
Midterm Team Contest (27 Feb 23)
Midterm Team Contest (04 Mar 24)
Our Midterm Team Contest (03 Mar 25) is on Kattis
Starts at 5.15pm SGT, ends at 9.45pm SGT (4.5 hours)
08
10 Mar
Chapter 8; Focus on the Section 8.6; Optional: Read the first 1/3 of CS4234 material
HW06 (special) due
HW07 due
Solve Mini 05 B/C
(upsolve some non AC Midterm Contest problems by yourself, optional)
Kattis set #07 due
Mini 06
Graph2: Matching
Money Contest
donated by
Citadel |
Citadel Securities
Coping with (NP-)hard Problems
Summary of 2/3 of CS4234 - Optimisation Algorithms (except local search) in CS3233 style.
VisuAlgo: mvc, steinertree, tsp
09
17 Mar
Chapter 5 and 9; Focus on Section 5.3-5.6 + 9.36;
Read the rest of Chapter 5 by yourself;
Plus Section 9.9, 9.11, 9.15, 9.16, and 9.30
HW08 due
Solve Mini 06 B/C
Kattis set #08 due
Mini 07
(NP-)hard Problems
Money Contest
donated by
NUS ICPC endowment
NUMB3RS
Mathematics overview with a movie; Focus on Python/Java Big Integer, Combinatorics, Number Theory (Extended Euclid, Modular Inverse, Fermat's little theorem, Chinese Remainder Theorem), and a bit of Probability
VisuAlgo: cyclefinding
NOI 2025 Competition is this Sat, 22 Mar 2025
(onsite final contest)
10
24 Mar
Chapter 6; Focus on Section 6.6 + 9.45;
Read the rest of Chapter 6 by yourself
HW09 due
Solve Mini 07 B/C
Kattis set #09 due
Mini 08
Mathematics
Money Contest
donated by
Jump Trading
(we will take a class photo #1)
A Glance at Bioinformatics
String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array; a bit of String Hashing
VisuAlgo: suffixtree, suffixarray
Jump Trading class visit
Mon, 24 Mar 2025
7.00-7.30pm + QnA during break time
Fri, 28 Mar 2025 is chosen as
NUS well-being day S2 AY 2024/25
This is to link with Hari Raya Puasa PH next Monday
Also, NUS Online Teaching Feedback opens this Fri
You can already start declaring your vote about this course
11
31 Mar
No class
Kattis set #10 due
(automatic)
No class
No class
Hari Raya Puasa Public Holiday
12
07 Apr
Chapter 7; Focus on Section 7.2, 7.3, 9.5;
Also Section 8.7 (problem decomposition)
Read the rest of Chapter 7 by yourself
HW10 due
Solve Mini 08 B/C
Kattis set #11 due
Mini 09
String
Money Contest
donated by
NUS ICPC endowment
(final team contest formation are finalised via class Discord discussion)
(we will then do a no-longer-optional CS3233 Final Online Quiz (7.20-7.30pm))
Inside Video Games
(Computational) Geometry; Focus on Algorithms on Points, Lines, a bit of 3D Geometry, and Polygon, Art Gallery Problem
VisuAlgo: polygon, convexhull
(we will run a short last lecture to close the course and may extend beyond 9pm)
The Last Lecture (8.50-9.15pm)
13
14 Apr
The entire CP4 book 1+2 and beyond
Do not forget to give your official
NUS Online Teaching Feedback
after final team contest is over
Solve Mini 09 B/C
Kattis set #12 due
Week01-12 stuffs
5.15-9.45pm (4.5h)
Money Contest
funded by
NUS ICPC endowment
Join NUS ICPC team selection
(~Late August 2025?)
No lecture, we do Final Team Contest
VisuAlgo (for self-review): maxflow, matching, mvc, steinertree, tsp, cyclefinding, suffixtree, suffixarray, polygon, convexhull
Final Team Contest (recent 3 AYs only):
Final Team Contest (11 Apr 22)
Final Team Contest (10 Apr 23)
Final Team Contest (15 Apr 24)
Our Final Team Contest (14 Apr 25) is on Kattis
Starts at 5.00pm SGT, ends at 10.00pm SGT (5 hours)
No final assessment, go and save your other courses after tonight
Good Friday and Easter Sunday this Week