CS3230 - Design and Analysis of Algorithms

Introduction

First, let's abbreviate "Design and Analysis of Algorithms" as DAA to differentiate it with Prof Steven Halim's other course "Data Structures and Algorithms" (DSA).

This (DAA) course introduces different techniques of designing and analysing algorithms. Students will learn about the framework for algorithm analysis, for example, lower bound arguments, average case analysis, and the theory of NP-completeness. In addition, students are exposed to various algorithm design paradigms. The course serves two purposes: to improve the students' ability to design algorithms in different areas, and to prepare students for the study of more advanced algorithms. The course covers lower and upper bounds, recurrences, basic algorithm paradigms (such as prune-and-search, dynamic programming, branch-and-bound, graph traversal, and randomised approaches), amortized analysis, NP-completeness, and some selected advanced topics.

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 sixth time Prof Steven Halim (co-)teaches CS3230. For S1 AY2026/27, we are expecting ~400. Historically, it was 382 in S1 and 351 in S2 AY 2025/26 (we are aware on why S1.size() + S2.size() < c * NUS-Computing-CS-cohort-size, where 0.0 ≤ c ≤ 1.0 — we estimate c ≈ 0.7).

As of Wed, 18 Nov 2026, the class size is 410 (1 more had dropped) -- and this is final assessment attendance list size.

Important information:

  1. Lecturers (S1 AY26/27): CHANG Yi-Jun (Wk01-05), Steven HALIM (Wk06-08), and RAHUL Jain (Wk09-13).
    Lecturers (S2 AY26/27): Steven HALIM (Wk01-04), RUCHA Ravi Kulkarni (Wk05-09), and CHEN Yu (Wk10-13).

    CS3230 has been changing hands so frequently in recent AYs and the experience varies, but now "converging":
    S1 AY24/25: Chang Yi-Jun+Steven Halim → S2 AY24/25: Eric Han Liang Wee+Sanjay Jain+Warut Suksompong →
    S1 AY25/26: Chang Yi-Jun+Steven Halim+Prashant Nalini Vasudevan → S2 AY25/26: Sanjay Jain+Warut Suksompong+Chen Yu →
    S1 AY26/27: Chang Yi-Jun+Steven Halim+Rahul Jain+Rucha Ravi Kulkarni → S2 AY26/27: Steven Halim+Rucha Ravi Kulkarni+Chen Yu
    CS3230 in both S1+S2 of recent AYs should be more similar than before as we (CS3230 teaching colleagues) regularly do post-semester synchronization meetings.

    Rating
    (out of 5.0)
    Jan-Apr 27
    (n≥???/4??)
    ≥67?%
    Aug-Nov 26
    (n≥219+/410)
    ≥53%+
    Aug-Nov 25
    (n=252/382)
    66% ▼
    Aug-Nov 24
    (n=306/434)
    71% ▲
    Jan-Apr 24
    (n=222/362)
    61%
    Course feedback (SoC CS avg lvl 3000 ~3.9) [3.9..4.0] (tgt) [3.9..4.0] (tgt) 3.8 ▼ 3.9 (Joint-PB) ▲ 3.8
    Course difficulty (SoC CS avg lvl 3000 ~4.0) [4.3..4.4] (tgt) [4.3..4.4] (tgt) 4.5 == 4.5 == 4.5
    Prof Halim's teaching (SoC CS avg lvl 3000 ~4.2) [4.2..4.4] (tgt) [4.2..4.4] (tgt) 4.3 ▼ 4.4 (PB) ▲ 4.2
  2. Teaching Assistants:
    There are 20+1 = 21 tutorial groups, all are 1-hour block (effective 45m), all are at COM1-0209 (SR9).

    Time (ID) Wed (size/cap) (ID) Thu (size/cap) (ID) Fri (size/cap)
    08-09 (01) @yql (15/21)
    09-10 (02) @jose (20/21) (08) @kelven11 (20/21) (21) @rucha_76260 (16/21)
    10-11 (03) @maahir (20/21) (09) @stot (19/21) (15) @spadez (19/21)
    11-12 (04) @x1213 (20/21) (10) @ycteo_ (21/21) (16) @party (20/21)
    12-13 (05) @lwk19 (20/21) (11) @pacman (21/21) (17) @ryan (21/21)
    13-14 (06) @yosie (18/21) (12) @javalim (21/21) (18) @metal (22/22)
    14-15 (07) @halim (20/21) CS3230 lecture@LT11
    15-16 NUSOne CS3230 lecture@LT11
    16-17 NUSOne (13) @spynx6 (21/21) (19) @party (20/21)
    17-18 NUSOne (14) @bionicrjk (19/21) (20) @oolimry (20/21)

    List of TAs (Wednesdays):

    1. @yql, MICHAEL Yang Qianlong, ex CS3230 (A) (peak rating: 4.5/CS2040S and CS3230 S2 AY25/26) (also TA-ing CS2040S)
    2. @jose(_kjh), Kim Jaeho (JOSE) (peak rating: 4.7/CS1101S S1 AY24/25)
    3. @maahir(_garg), Garg MAAHIR Rajesh (peak rating: 4.8/CS3230 S1 AY25/26) (also TA-ing CS3263)
    4. @x1213, Prof CHANG Yi-Jun
    5. @lwk19, Lee WAI KIN (peak rating: 5.0/CS1101S S1 AY24/25)
    6. @yosie(667_12720), Song YUEXI (peak rating: 4.6/CS2040S S2 AY24/25)
    7. @(prof_)halim, Prof Steven HALIM (head TA for this sem, taking slot #7, right before NUSOne)

    List of TAs (Thursdays):

    1. @kelven11, KELVEN Nathanael, ex CS3230 S2 AY25/26 (A+, rank 1) and CS3233 (A)
    2. @(press_)stot, STUART Lim Yi Xiong, ex CS3233 (A) (new TA)
    3. @ycteo_, Teo YOCK CHENG (peak rating: 4.8/CS1101S S2 AY24/25) (also TA-ing CS2040S)
    4. @(.happy)pacman, ALBERT Ariel Putra, ex CS3230 (A) and CS3233 (A-) (peak rating: 4.4/IT5003 S2 AY25/26)
    5. @javalim, JAVIER Lim (peak rating: 4.4/CS2040S S2 AY25/26)
    6. @spynx6, Wong YEE HERN (peak rating: 4.8/CS1101S S1 AY25/26)
    7. @bionicrjk, KERK Tai Heng, ex CS3233 (A) (peak rating: 4.9/CS2040S S2 AY24/25) (also TA-ing CS2040S)

    List of TAs (Fridays):

    1. @rucha_76260, Dr RUCHA Ravi Kulkarni (new slot #21) - the first 2 tutorials had been covered by @lwk19
    1. @(the_kingof)spadez, Ratnavibusena Don SHAHAIN Manujith (peak rating: 4.9/CS3230 S2 AY24/25)
    2. @party(whenparty), RAJARSHI Basu (FTTA, full load, first group)
    3. @ryan(.low), Low Khing Wei, RYAN (peak rating: 4.6/CS3230 S1 AY25/26)
    4. @metal(_power), MATTHEW Allan (peak rating: 4.3/CS3230 S1+S2 AY25/26)
    5. @partywhenparty, RAJARSHI Basu (FTTA, full load, second group)
    6. @oolimry, Lim RUI YUAN, ex CS3230 S1 AY 25/26 (A+, rank 1) and CS3233 (A+) (new TA)

  3. Teaching Assistants (Preparation for S2 AY 26/27):
    There are 2x10 = 20 tutorial groups, all are 1-hour block (effective 45m), all are at COM1-0208 (SR8).

    Time (ID) Mon (size/cap) (ID) Tue (size/cap)
    09-10 (01) TBC (??/20) (10) TBC (??/20)
    10-11 (02) TBC (??/20) (11) TBC (??/20)
    11-12 (03) @halim (??/20) (12) @rucha_76260 (??/20)
    12-13 (04) TBC (??/20) (13) TBC (??/20)
    13-14 (05) TBC (??/20) (14) TBC (??/20)
    14-15 (06) TBC (??/20) (15) TBC (??/20)
    15-16 (07) TBC (??/20) (16) TBC (??/20)
    16-17 (08) TBC (??/20) (17) Chen Yu (??/20)
    17-18 (09) TBC (??/20) (18) TBC (??/20)
    18-19 (if needed) (19) TBC (??/20) (20) TBC (??/20)

    As Prof Halim+Dr Rucha will co-teach CS3230 in S2 AY26/27 too (with Dr Chen Yu), we are now opening part-time TAs applications too (for 2x10 slots: Mondays/Tuesdays 9.00am-6.00pm):
    Dr Rucha will be the final decision maker for S2 TA recruitment (please email Dr Rucha and cc me (Prof Halim) for tracking):

    • Category 0: Confirmed re-taken:
      1. @rucha_76260, Dr RUCHA Ravi Kulkarni (head TA for S2 AY26/27; she is in charge of other part-time TA selection below)
      2. @(prof_)halim, Prof Steven HALIM
      3. @???, Dr CHEN Yu
      4. @partywhenparty, RAJARSHI Basu (FTTA, full load, first group)
      5. @partywhenparty, RAJARSHI Basu (FTTA, full load, second group)
      6. [one more FTTA, half load, TBC]
    • Category 1: Prof Halim returning part-time TAs (sorted by non-increasing peak-performance - of most relevant course(s): CS3230/CS2040/S/IT5003/CS3233/others):
      1. @lwk19, Lee WAI KIN (peak rating: 5.0/CS1101S S1 AY24/25)
      2. @spynx6, Wong YEE HERN (peak rating: 4.8/CS1101S S1 AY25/26)
      3. @maahir(_garg), Garg MAAHIR Rajesh (peak rating: 4.8/CS3230 S1 AY25/26)
      4. @ycteo_, Teo YOCK CHENG (peak rating: 4.8/CS1101S S2 AY24/25) (also TA-ing CS2040S)
      5. @wilkinsang, Ang WEI JIAN, ex CS2040S S1 AY24/25 (A+), (peak rating: 4.6/CS2040S S1 AY25/26)
      6. @yosie(667_12720), Song YUEXI (peak rating: 4.6/CS2040S S2 AY24/25)
      7. @oolimry, Lim RUI YUAN, ex CS3230 S1 AY 25/26 (A+, rank 1) and CS3233 (A+) (new TA; will be 2nd time by S2 AY26/27; assuming rating ≥ 4.1)
      8. Nguyen Hoang TIEN (peak rating: 4.6/CS3233 S2 AY25/26)
    • Category 2: Has other NUS teaching experience(s), chance correlates with teaching feedback of those past experiences (sorted by non-increasing peak-performance) and perceived 'spare mental capacities left to do far-higher-than-average TA job again':
      1. @???, Chin KUAN JAK, (peak rating: 4.2/CS1231S S1 AY24/25)
      2. Ng Mun Hin: took CS3230 in AY25/26 Sem 1 and achieved a grade of A+. Taught CS2030S Labs (4.2 rating) and CS2100 Tutorials (4.6 rating)
      3. @???, RAFAEL Kristoforus Yanto, (peak rating: 3.9/CS2106 S2 AY25/26)
      4. Tang HAOYUN (past CS3230 TA? TBC)
    • Category 3: New with NUS teaching, chance correlates with Prof Halim's 'spider sense' about the candidates potential teaching capabilities and perceived 'spare mental capacities left to do first time TA job' (for future TA army replenishment) - discuss with Prof Halim directly to adjust your ranking below:
      1. Ng Hong Ming: A- in 1231S, A- in 2040S, Linear algebra math course MA1522 A+. Prospective A in 3230 with 47/60 in midterm. No past teaching experience at NUS.
      2. Orestis: PhD student with Prof Frank Stephan.
      3. We will not know this until TMTF is opened to us or until you email Dr Rucha (cc me).

    List of TAs (Mondays):

    1. @(prof_)halim, Prof Steven HALIM

    List of TAs (Tuesdays):

    1. @rucha_76260, Dr RUCHA Ravi Kulkarni (head TA for S2 AY26/27)
    2. @???, Dr CHEN Yu

  4. Consultation Hours (S1 AY26/27):
    Since the number of consultation requests from Week 01-05 so far is... zero (very likely due to GenAI), we change our consultation hours policy to:
    Whoever needs to talk to real human lecturer (most likely course admin related), just drop us an email.
    We are no longer guaranteed to be in our office in our previously stated office hours.
    1. CHANG Yi-Jun (cyijun@nus.edu.sg)
    2. Steven HALIM (dcssh@nus.edu.sg)
    3. RAHUL Jain (dcsrahul@nus.edu.sg)
    4. RUCHA Ravi Kulkarni (rucha@nus.edu.sg)
  5. Consultation Hours (Preparation for S2 AY 26/27):
    Whoever needs to talk to real human lecturer (most likely course admin related), just drop us an email.

    1. CHANG Yi-Jun (cyijun@nus.edu.sg)
    2. RUCHA Ravi Kulkarni (rucha@nus.edu.sg)
    3. CHEN Yu (yu.chen@nus.edu.sg)

  6. Have you passed (or exempted from) CS2040S (or its equivalents/variants)? You have to... This course assumes that you have passed the lower-level DSA course.
  7. Have you passed (or exempted from) MA1100/CS1231S (or its equivalents)? You have to... This course is heavy on mathematics

Syllabus

This is what you will learn this semester:

  • Design:
    • Complete Search/prune-and-search/branch-and-bound (no specific lecture, but Complete Search algorithms appear several times in this course)
    • Divide and Conquer (D&C)
    • Randomized Algorithms
    • Dynamic Programming (DP)
    • Greedy Algorithms
    • Sorting in Linear-Time
    • Order Statistics
  • Analysis:
    • Asymptotic Analysis
    • Recurrences and Master Theorem
    • Proof of Correctness of Iterative and Recursive Algorithms
    • Lower bound of comparison-based sorting
    • Probabilistic Analysis of Randomized Algorithms
    • Amortized Analysis
    • NP-completeness

Course Registration (already edited to S2 AY 2026/27 version) Additional FAQ

If you have any important questions regarding this course, email dcssh at nus (course coordinator), rucha at nus, or yu.chen at nus. Relevant answers will be posted here to reach wider audiences.

Q: Will CS3230 S2 AY 2026/27 be fully onsite?
A: Yes. All class activities are onsite. We plan for only one lecture group, L1: each Wednesday, 10am-12nn, at LT11 (big enough for 450 pax). Lectures will be recorded centrally by NUS CTLT (after each lecture, the lecture recording is released as early as CTLT is able to post-process the recording).
Q: I will be taking ATAP too, can you approve me taking CS3230 alongside doing ATAP?
A: There may be a change for S2 AY26/27 (TBC). Stay tuned.
Q: I want to take CS3230 and another course that has lecture timetable clash with CS3230 (Wed, 10am-12nn). Can you give me a timetable clash waiver?
A: Auto reply: NO.
Q: Can I audit CS3230?
A: CS3230 is a core course and we generally do not accept students auditing CS3230. Students who are outbidded this S2 AY 2026/27 (in case the number of bidder > 450... unlikely though based on historical data) are not allowed to audit CS3230 this semester, just read the course officially next S1 AY 2027/28 or latter semester instead. However, email Prof Halim (dcssh) directly for case-by-case appeal.
Q: Do I have to buy any textbook for this course?
A: Generally, we do not require students to buy any textbook. We will try to make the lecture notes, tutorial, and assignment files self-sufficient. However, students who aspire to self-study much more of DAA content are encouraged to get a (legal) copy of some (or all) of these:
  1. Main: Introduction to Algorithms by Cormen Leiserson, Rivest, Stein, 4th edition (2022), but the 3rd edition (2009) is still sufficient (no need to buy again if you already have the 3rd edition, but if you want to get this book for the first time, obviously get the latest 4th edition)
  2. Additional reference: Algorithm Design by Kleinberg & Tardos (2006)
  3. Programming assignment reference: Competitive Programming book: CP4, Book 1+2 (get a copy legally from lulu.com: eBook 1 and eBook 2)
  4. NP-complete compendium: Computers and Intractability by Garey and Johnson (1979)
Q: Can I S/U this course?
A: No.
Q: Is CS3230 a flipped classroom course?
A: Still a no...
Q: What are the potential changes that you will apply to CS3230 in S1 AY 2026/27 compared to your earlier runs of this course (e.g., S1 AY 2025/26)?
A: We only plan to change these variables this time (all others are planned to be kept roughly constant):
  1. If CS3230 is changed into blended-learning type, there will be a lots of changes... But if not, it will look somewhat similar to last year's S1 AY2025/26 edition (TBC) (this is a NO)
  2. Given the high importance of individual midterm test (30%) and final assessment (40%) for this course, do take a look at Prof Halim's recent Gen-AI style exam paper for CS2040C/IT5003 last S2 AY25/26. Whether the format is sustained or not depends on discussion with the other two three co-lecturers. Update after midterm: Only Prof Halim use this format for midterm (and likely he is the only one doing this for final).
  3. The main interaction between CS3230 students with teaching staffs usually happen during tutorial sessions. We will again have 12 (TWELVE) tutorial slots, starting from Week 02, ending on Week 13, without public holiday interrupting our Wed/Thu/Fri tutorial slots (except Fri of Wk08/NUS well-being day). NEW: There will be a mix of attendance (out of those 12) tutorial slots on top of tutorial participation points. Update: We stick with last year's format.
  4. LeetCode discussion will be increased. Most discussion will happen online at Class Discord, but on most Fri lecture (Update: This only happened on Wk2-7), Prof Halim will spend the last 5+ minutes discussing the LeetCode solution for that day and your Wed/Thu/Fri tutorial TA may discuss solution for Wed/Thu/Sat LeetCode task for that day.
Q: What are the potential changes that you will apply to CS3230 in S2 AY 2026/27 compared to your earlier runs of this course (e.g., S1 AY 2026/27)?
A: I will only update this answer by late Dec 2026/early Jan 2027 after I see the official teaching feedback data.

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

News

Date News

Lesson Plan

Week Tutorial
Timings: Wed, Thu, or Fri (1 hr/wk)
Venue: COM1-0209 (SR9)
Lecture
Fri 2-4pm
Venue: LT11 (≤450 pax)
Assignment
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
00,
03-07 Aug
Has Not Started

Essential LeetCode exercises involving asymptotics:
Mon: two-sum (first LeetCode problem; can you design o(n log n) solution?),
Tue: two-sum-ii-input-array-is-sorted (sorted; can you design θ(n) solution?),
Wed: two-sum-iv-input-is-a-bst (BST variant; can you design θ(n) solution?),
Thu: 3sum (uses two-sum solution; can you design θ(n^2) solution?),
Fri: 3sum-closest (another 3sum variant; can you design θ(n^2) solution?),
Sat: 4sum (can you design o(n^4) solution?).
Has Not Started

Just self-review CS2040S content
Has Not Started
01,
10-14 Aug
Has Not Started

Essential LeetCode exercises involving asymptotics:
Mon: equal-row-and-column-pairs (design any Ω(n^2) and O(n^3) solution),
Tue: longest-fibonacci-subarray (can you design a Θ(n) solution?),
Wed: fibonacci-number (does an exponential algorithm still passes?),
Thu: n-th-tribonacci-number (Fibonacci variant; do we need a faster algorithm?),
Fri: climbing-stairs (reduce this into a Fibonacci-like problem),
Sat: climbing-stairs-ii (extension of the three earlier problems).
Singapore National Day on Sun, 09 Aug 26
The following Mon, 10 Aug 26 is a Public Holiday
this class is not affected

01a. Course Admin (S1 AY26/27 edition — please read)
01b. Asymptotic Analysis (analysis)
Introduction
Model of Computation (Word-RAM)
Experiment with Fibonacci cpp|py|java code and its recursion tree vs DAG
Formal definitions of Big-O, Ω, Θ, o, ω with helper xlsx file to draw the charts

References:
CLRS 4th ed Chapter 1-2-3
KT Chapter 2
CP4 Book 1 Chapter 1.3.3; Book 2 Chapter 5 (Fibonacci)
Has Not Started
02,
17-21 Aug
tut01.pdf
Introduction + Asymptotic Analysis
started early (because we want to)
onsite at our tutorial venue
(already booked one week in advance)
Checking Definitions: O, Ω, Θ o, ω, Limits
True/False tests
Ranking functions

Essential LeetCode exercises:
Mon: merge-sorted-array (Θ(n+m) time; Θ(1) auxiliary space),
Tue: merge-two-sorted-lists (in SLL format; same target as above),
Wed: k-radius-subarray-averages (can you design an o(nk) solution?),
Thu: intersection-of-two-arrays-ii (can you design an O(n log n) solution?),
Fri: remove-duplicates-from-sorted-array-ii (Θ(n) time; Θ(1) auxiliary space),
Sat: longest-subarray-of-1s-after-deleting-one-element (use two pointers).
02. Recurrences and Master Theorem (analysis)
Quick review of Merge Sort especially its analysis
Review Merge Sort implementation at SortingDemo.cpp | py | java
Play with Tower of Hanoi puzzle.
Use VisuAlgo recursion page to analyse some recursion trees
Telescoping, Substitution Method, Recursion Tree,
and Master Theorem case 1|2|3
Use this Master Theorem tool from Baylor University
Live demo: mastertheorem (demo of case 1 only)

References:
CLRS 4th ed Chapter 2.3 and 4.3-4.6
KT Chapter 5.1-5.2
CP4 Book 1 Chapter 2.2.2
Assignment 1
(21 Aug-04 Sep)
Asymptotic Analysis,
Recurrences/Master Theorem
Check Canvas - Assignments
03,
24-28 Aug
tut02.pdf
Recurrences
Telescoping
Master Theorem
Substitution Method
Recursion Tree

Essential LeetCode exercises involving D&C:
Mon: search-in-rotated-sorted-array (on rotated array),
Tue: peak-index-in-a-mountain-array (on mountain array),
Wed: search-a-2d-matrix (on special 2D matrix; design an o(mn) solution; ignore I/O cost),
Thu: guess-number-higher-or-lower (interactive binary search),
Fri: powx-n (implement D&C exponentiation shown in class; handle negative n),
Sat: merge-k-sorted-lists (classic k-way merge, tut02).
03a. Proof of Correctness (analysis)
Review Iterative IFib from lec01b
Review Iterative Dijkstra's algorithm
Review Recursive Fib from lec01b
Review Recursive Binary Search (also a D&C algorithm)

03b. Divide and Conquer (D&C) Algorithm (d) - 1
Review Merge Sort (again)
See modulo power/Mod Pow/modular exponentiation
Live demo: powx-n

References:
CLRS 4th ed Chapter 2.1 and 4.1-4.2
KT Chapter 5
CP4 Book 2 Chapter 3.3 (Binary Search), 4.4 (Dijkstra's), 5 (Matrix Power)
Extra exercises: the entire binary-search study plan
Assignment 1
continued
04,
31 Aug-04 Sep
tut03.pdf
Correctness + D&C (1)
Proof of Correctness
Use VisuAlgo sorting page to review Insertion Sort
Prove an Interesting' Recursive Sorting Algorithm
D&C: Finding any peak (2D)

Essential LeetCode exercises involving D&C:
Mon: snapshot-array (snapshots are in increasing order; binary searchable),
Tue: successful-pairs-of-spells-and-potions (sort, so that we can do BSTAs),
Wed: find-the-peaks (simple θ(n) complete search),
Thu: find-peak-element (O(log n) DnC, 1D; ignore I/O cost),
Fri: kth-smallest-number-in-multiplication-table (O(m log ans) DnC; BSTA; a bit of math),
Sat: find-a-peak-element-ii (DnC, 2D, tut03; ignore I/O cost).
03b. Divide and Conquer (D&C) Algorithm (d) - 2
Complete the leftovers from Week 03
From computing n-th Fibonacci in O(log n) - end

04a. Lower bound of comparison-based sorting (a)
Read sorting e-Lecture slides (Slide 14 to 16-2)
Key point: Ω(n log n) to sort n-elements using comparison-based algorithm

References:
CLRS 4th ed Chapter 8.1
KT and CP4 don't have a section on lower bound of comparison-based sorting

04b. (Deterministic) Quicksort (analysis)
Read sorting e-Lecture slides (Slide 12 to 12-13)
Analysis of the average case of deterministic Quicksort
Key point: for non-randomized Quicksort algorithm, it is:
O(n^2) to sort n-elements in the worst-case but
O(n log n) to sort n-elements on average

Live demo: kth-smallest-number-in-multiplication-table

References:
CLRS 4th ed Chapter 7.1-7.2
CP4 Book 1 Chapter 2.2 (1D array processing)
Assignment 1
due Fri, 04 Sep, 23:59

Assignment 2
(04-18 Sep)
D&C-related task,
Randomized algorithm task

Has online judge component (optional)
Only the reflection component is graded
05,
07-11 Sep
tut04.pdf
D&C (2) + Decision Tree
Polynomial Multiplication
Binary Search
Decision Tree

Essential LeetCode exercises involving Binary Search:
Mon: valid-perfect-square (avoid sqrt; but you can use mult and BSTA),
Tue: sqrtx (similar to valid-perfect-square),
Wed: h-index (easier than in tut04),
Thu: h-index-ii (tut04),
Fri: majority-element (randomized algorithm demo),
Sat: convert-sorted-array-to-binary-search-tree (DnC balanced BST construction).
05. Randomized Algorithms (design)
Randomized Quicksort (analysis)

Probability techniques: union bound, expected value, Markov inequality,
Indicator random variable and linearity of expectation for analysis
Probability problems: balls into bins, coupon collector's.
Try Hash Table Separate Chaining (generate random N keys/balls to M cells/bins).
Read sorting e-Lecture slides (Slide 13 to 13-2)
Key point: Randomization can speed-up and/or simplify certain algorithms
Live demo: majority-element

References:
Review Probability (via those Wikipedia pages)
CLRS 4th ed Chapter 7.3-7.4
KT Chapter 13 (some examples, e.g., 13.5 (QS))
CP4 doesn't have a specific chapter on randomized algorithms — yet
Assignment 2
continued
06,
14-18 Sep
tut05.pdf
Randomized Algorithms
Freivald's algorithm revisited
Randomised communication protocol
Random cut of a graph

Essential LeetCode exercises involving Randomization:
Mon: majority-element-ii (extension of Week05 lecture demo),
Tue: random-pick-with-weight (random exercise),
Wed: linked-list-random-node (hint: this),
Thu: shuffle-an-array (hint: this),
Fri: longest-common-subsequence (classic DP),
Sat: generate-random-point-in-a-circle (hint: this).
06. Dynamic Programming (DP) (design)
Read VisuAlgo notes about Fibonacci
Longest Common Subsequence (LCS)
Live demo: longest-common-subsequence
0/1-Knapsack
Coin Change and
Longest Increasing Subsequence (LIS)
Experiment with more test cases beyond the static official lecture notes examples.

References:
CLRS 4th ed Chapter 14
KT Chapter 6
CP4 Book 1 Chapter 3.5 + Book 2 Chapter 5.4, 5.8, 6.4 and 8.3
Extra exercises: the entire dynamic-programming study plan
Assignment 2
due Fri, 18 Sep, 23:59

Assignment 3
(18 Sep-11 Oct)
DP task(s)
Greedy task(s)

Has online judge component (optional)
Only the reflection component is graded
Recess Week, 19-27 Sep 2026
You can take a break this week :)
07,
28 Sep-02 Oct
tut06.pdf
Dynamic Programming
Convex Polygon Triangulation
One or two DP tasks from LeetCode
FAQ: (Easier) DP question will be in Midterm

Essential LeetCode exercises involving DP:
Mon: perfect-squares (simple DP with only 1 parameter),
Tue: longest-increasing-subsequence (classic LIS; solve it in O(n^2) or better),
Wed: minimum-score-triangulation-of-polygon (tut06),
Thu: combination-sum-iv (easy if you understand Lec06),
Fri: assign-cookies (greedy bipartite matching),
Sat: uncrossed-lines (easy if you understand Lec06).
07. Greedy Algorithms (design)
Fractional Knapsack (comparison with 0/1-Knapsack that needs DP)
Huffman Coding
Live demo: assign-cookies (Greedy Bipartite Matching)
LIS revisited (patience sorting)

References:
CLRS 4th ed Chapter 15
KT Chapter 4
CP4 Book 1 Chapter 3.4

Midterm Test (30%)
Venue: MPSH 5
Date and Time: Sat, 03 Oct 26 (wk7), 02:00-04:00pm (120 mins)
Hall entry and exit time: 1:45pm and 4:15pm
Mode of assessment: Hardcopy (Pen and Paper)
Invigilators: Prof Halim, Prof Chang, Prof Rahul,
@lwk19, @maahir, @jose, @yosie, @spynx6, @oolimry (special cases)
No electronic device except one calculator
A few special needs students do the test at our tutorial room: SR9
O(1) SEATING PLAN: sorted names -> [1..423]

Midterm Test Past Papers (recent 3 AYs only):
AY 2024/25: S1-midterm.pdf, S2-N/A (not ours),
AY 2025/26: S1-midterm.pdf, S2-N/A (not ours),
AY 2026/27: S1-midterm.pdf (ours); S2-midterm.pdf (for next sem).
Assignment 3
Continued
08,
05-09 Oct
tut07.pdf
Greedy Algorithms
Burning CDs Problem
Activity Selection Problem
Greedy Algorithms Q will appear in the Final

Essential LeetCode exercises involving Greedy Algorithms:
Mon: two-furthest-houses-with-different-colors (there is a simple greedy strategy),
Tue: jump-game-ii (greedy solution is much faster than systematic search),
Wed: ipo (doable if you understand Lec07),
Thu: non-overlapping-intervals (tut07),
Fri: partition-labels (there is a simple enough greedy strategy),
Sat: boats-to-save-people (tut07).

Fri, 09 Oct 2026 is NUS Well-Being Day
Only Fri tutorial group is affected
(if possible, attend *any* Wed/Thu session)
(or just review the recording of Prof Halim's Wed session)
Fri, 09 Oct 2026 is NUS Well-Being Day
This Fri lecture slot is cancelled
Assignment 3
due Sun, 11 Oct, 23:59
(two days after Well-Being Day)
Then a few days break

09,
12-16 Oct
tut08.pdf
As last Fri lecture slot was canceled,
We will use this buffer slot to (try to live-)solve as many LeetCode problems
involving techniques that we have learned so far (Week 01-08):
Mon: minimum-positive-sum-subarray (O(n^3) solution — Week 01+02),
Tue: heaters (D&C — Week 03+04),
Wed: random-point-in-non-overlapping-rectangles (randomized — Week 05),
Thu: maximum-score-from-performing-multiplication-operations (DP — Week 06),
Fri: counting-bits (using Lec08 explanation),
Sat: most-profit-assigning-work (Greedy — Week 07).
Makeup Midterm Test Time Window
Only announced to 10 student(s) with official leave
During NUSOne timeslot on Wed, 14 Oct 2026, 3.30-5.30pm SGT, SR9

08. Amortized Analysis (analysis)
Try the 'increment' operation at bitmask visualization
Try the 'resize-able array doubling' operation at array visualization
Integrated in Prof Rahul's lecture: counting-bits

Extras:
Try the 'multipush/pop' operation at Stack visualization
Try the 'multienqueue/dequeue' operation at Queue visualization

References:
CLRS 4th ed Chapter 16
No specific chapter on amortized analysis in KT
Search for keyword 'Amortized Analysis' in CP4 Book 1+2, index section
Assignment 4
(16-30 Oct)
Amortized Analysis
Problem Reduction
10,
19-23 Oct
tut09.pdf
Amortized Analysis
Aggregate method (limited applicability)
Accounting method
Potential method
Amortized Analysis Q will appear in the Final

Essential LeetCode exercises involving Amortized Analysis:
Mon: implement-queue-using-stacks (CS3230 final S2 AY22/23, B.3),
Tue: largest-rectangle-in-histogram (monotonic stack; amortized analysis),
Wed: daily-temperatures (from back; monotonic stack; amortized analysis),
Thu: next-greater-element-ii (monotonic stack; amortized analysis),
Fri: house-robber (MWIS on line graph; DP),
Sat: online-stock-span (monotonic stack; amortized analysis).
09. Problem Reductions and Intractability
The concept of reductions (in polynomial time)
See the preview of VisuAlgo reductions page
Use VisuAlgo mvc page for two NP-complete problems VC and IS
Time permitting, live demo: house-robber

References:
CLRS 4th ed Chapter 34
CP4 Book 2 Chapter 8.6 (NP-hard/complete Problems)
Assignment 4
Continued
11,
26-30 Oct
tut10.pdf
Problem Reduction
Use VisuAlgo reductions page
for 2 out of 4 questions
This could be the hardest Q in the Final

Essential LeetCode exercises involving NP-complete/hard 1:
Mon: house-robber-ii (extension of Lec09 demo),
Tue: house-robber-v (another variant of Lec09 demo)
Wed: partition-array-into-two-equal-product-subsets (PARTITION, tut10),
Thu: partition-equal-subset-sum (PARTITION ≤p SUBSET-SUM, tut10),
Fri: house-robber-iii (MWIS on Tree; DP again),
Sat: partition-to-k-equal-sum-subsets (PARTITION into k subsets).
10. Introduction to NP-completeness (analysis)
See VisuAlgo reductions page again:
start from the beginning (C-SAT, CNF-SAT, 3-SAT);
then 3-SAT ≤p IS ≤p VC ≤p HS
also: IS ≤p CLIQUE
Time permitting, live demo: house-robber-iii

References:
CLRS 4th ed Chapter 34.3-34.5

NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until the last lecture on Week 13
Assignment 4
due Fri, 30 Oct, 23:59

(Optional) Assignment 5
(30 Oct-13 Nov)
NP-complete,
Order Statistics
12,
02-06 Nov
tut11.pdf
NP-complete
See VisuAlgo reductions page
3-SAT ≤p SUBSET-SUM
?? ≤p FIND-FAMILY
This could be the hardest Q in the Final

Essential LeetCode exercises involving NP-complete/hard 2:
Mon: maximum-profit-in-job-scheduling (CS3230 final S1 AY25/26, B.1),
Tue: coin-change (COIN-CHANGE general case),
Wed: combination-sum-ii (find all unique SUBSET-SUM combinations; tut11),
Thu: ones-and-zeroes (is this KNAPSACK variant? but two knapsacks?),
Fri: kth-largest-element-in-an-array (implement QuickSelect),
Sat: shortest-path-visiting-all-nodes (weighted HAM-PATH; need bitmask).
11. Linear-Time Sorting & Selection (d&a)
Linear-Time Sorting: (Re-)Introducing Counting Sort and Radix Sort
Key point: We can break the Ω(n log n) lower bound if we use
Θ(n+k) Counting Sort or Θ(b/r * (n+2^r)) Radix Sort

Linear-Time Selection: Reduction to sorting problem: sort array and report index k
see sorted array page; try "Select" k → "Go"
Expected Linear-Time Selection
see (unsorted) array page; try "Select" k → "Quickselect"
Worst-case Linear-Time Selection (a.k.a., median of medians)
(not in VisuAlgo; probably not worth it to animate this...)
Dynamic Order Statistics (with bBST, e.g., AVL Tree
augmented with size-of-subtree (a.k.a. Order Statistics Tree); try "Select")

Live demo 1: magicsequence (at open.kattis)
Live demo 2: kth-largest-element-in-an-array

References:
CLRS 4th ed Chapter 8.2-8.3, 9 (OS)
KT Chapter 13 (some examples, e.g., 13.5 (QS))
CP4 Book 1 Chapter 2.2.2 (Counting and Radix Sort), 2.3.4 (OST)
Assignment 5
Continued
13,
09-13 Nov
Deepavali PH on Sun, 08 Nov 2026
The following Mon, 09 Nov 2026 is PH in lieu
This class is not affected

tut12.pdf
Applications of linear-time selection
Quickselect expected linear-time analysis
(also double as Week 12/linear-time selection,
Week 05/randomized, and
Week 02/analyze recurrence review)
Pre-Final MCQs

Essential LeetCode exercises involving Linear-time Sorting/Selection:
Mon: find-the-kth-largest-integer-in-the-array (nums are given upfront; static),
Tue: the-kth-factor-of-n (solve this in O(n0.5)),
Wed: query-kth-smallest-trimmed-number (radix sort and selection problem),
Thu: kth-smallest-element-in-a-bst (also see the follow-up),
Fri: find-minimum-time-to-reach-last-room-ii (an SSSP task),
Sat: kth-largest-element-in-a-stream (k is constant, but data come as a stream).
12. Summary and Revision (d&a)
(through the lens of (mostly) Graph Algorithms)
Review of the entire semester:
Use VisuAlgo sssp page for Dijkstra's (Greedy) vs Bellman-Ford (DP) review
Use VisuAlgo mst page for Prim's (Greedy) review
Use VisuAlgo reductions page for NP-completeness review
Live demo: TBA
Assignment 5
due Fri, 13 Nov, 23:59
(Optional if your CA ≥ 30/30)
Study Week, 14-20 Nov 2026

Final Assessment Discussions at Class Discord

Final Assessment Past Papers (recent 3 AYs only):
AY 2023/24: S1-N/A (not ours), S2-final.pdf ,
AY 2024/25: S1-final.pdf , S2-N/A (not ours),
AY 2025/26: S1-final.pdf , S2-N/A (not ours),
AY 2026/27: S1-final.pdf (will be ours), S2-final.pdf (for next semester).

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Thu, 26 Nov 2026, 09:00-11:30am (2.5h format)
Venue: MPSH2-A (invigilators: 4 lecturers: Yi-Jun (CI), Rahul (DCI), Halim, Rucha, 2 TAs: Rajarshi Basu, Rajdeep Singh Hundal) + UTSR7 (a few special needs)
Open book, no electronic device (except one calculator)
There are 20 MCQs; down from 26 MCQs last year (each lecture 01-12 topic has about 2-3 MCQs each), worth 2 marks each, so up to 20x2 = 40 marks will be machine graded (please shade the circles properly with 2B pencil)
(do record your 20 character answers on the question paper (that you can take home) for instant self-grading as the 20 characters answer key will be released by 1pm that day - after a few special needs students complete their extra time)
There will be 4 essays; up from 3 essays last year (4x10 = 40 other marks) with sub-tasks, covering mostly the second half of CS3230 (greedy; amortized; NP-c; linear-time stuffs, without forgetting the finale lecture that reviews lec01-06 topics too)
As with midterm, we introduced the FOURTH grading category: [0/INCORRECT, 0.5/BLANK, HALF-MARKS-OF-THE-BOX, FULL-MARKS-OF-THE-BOX] to balance grading speed versus grading fairness (incorrect but has substantive progress that is too harsh to be rounded to 0, may get this partial)

Lesson Plan (S2 AY26/27)

Week Tutorial
Timings: Mon or Tue (1 hr/wk)
Venue: COM1-0208 (SR8)
Lecture
Wed 10am-12nn
Venue: LT11 (≤450 pax)
Assignment
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
00,
04-08 Jan
Has Not Started

Essential LeetCode exercises involving asymptotics:
Mon: two-sum (first LeetCode problem; can you design o(n log n) solution?),
Tue: two-sum-ii-input-array-is-sorted (sorted; can you design θ(n) solution?),
Wed: two-sum-iv-input-is-a-bst (BST variant; can you design θ(n) solution?),
Thu: 3sum (uses two-sum solution; can you design θ(n^2) solution?),
Fri: 3sum-closest (another 3sum variant; can you design θ(n^2) solution?),
Sat: 4sum (can you design o(n^4) solution?).
Has Not Started

Just self-review CS2040S content
Has Not Started
01,
11-15 Jan
Has Not Started

Essential LeetCode exercises involving asymptotics:
Mon: equal-row-and-column-pairs (design any Ω(n^2) and O(n^3) solution),
Tue: longest-fibonacci-subarray (can you design a Θ(n) solution?),
Wed: fibonacci-number (does an exponential algorithm still passes?),
Thu: n-th-tribonacci-number (Fibonacci variant; do we need a faster algorithm?),
Fri: climbing-stairs (reduce this into a Fibonacci-like problem),
Sat: climbing-stairs-ii (extension of the three earlier problems).
01a. Course Admin (S2 AY26/27 edition — not ready)
01b. Asymptotic Analysis (analysis)
Introduction
Model of Computation (Word-RAM)
Experiment with Fibonacci cpp|py|java code and its recursion tree vs DAG
Formal definitions of Big-O, Ω, Θ, o, ω with helper xlsx file to draw the charts

References:
CLRS 4th ed Chapter 1-2-3
KT Chapter 2
CP4 Book 1 Chapter 1.3.3; Book 2 Chapter 5 (Fibonacci)
Has Not Started
02,
18-22 Jan
tut01.pdf
Introduction + Asymptotic Analysis
started early (because we want to)
onsite at our tutorial venue
(already booked one week in advance)
Checking Definitions: O, Ω, Θ o, ω, Limits
True/False tests
Ranking functions

Essential LeetCode exercises:
Mon: merge-sorted-array (Θ(n+m) time; Θ(1) auxiliary space),
Tue: merge-two-sorted-lists (in SLL format; same target as above),
Wed: k-radius-subarray-averages (can you design an o(nk) solution?),
Thu: intersection-of-two-arrays-ii (can you design an O(n log n) solution?),
Fri: remove-duplicates-from-sorted-array-ii (Θ(n) time; Θ(1) auxiliary space),
Sat: longest-subarray-of-1s-after-deleting-one-element (use two pointers).
02. Recurrences and Master Theorem (analysis)
Quick review of Merge Sort especially its analysis
Review Merge Sort implementation at SortingDemo.cpp | py | java
Play with Tower of Hanoi puzzle.
Use VisuAlgo recursion page to analyse some recursion trees
Telescoping, Substitution Method, Recursion Tree,
and Master Theorem case 1|2|3
Use this Master Theorem tool from Baylor University
Live demo: mastertheorem (demo of case 1 only)

References:
CLRS 4th ed Chapter 2.3 and 4.3-4.6
KT Chapter 5.1-5.2
CP4 Book 1 Chapter 2.2.2
Assignment 1
(20 Jan-03 Feb)
Asymptotic Analysis,
Recurrences/Master Theorem
Check Canvas - Assignments
03,
25-29 Jan
tut02.pdf
Recurrences
Telescoping
Master Theorem
Substitution Method
Recursion Tree

Essential LeetCode exercises involving D&C:
Mon: search-in-rotated-sorted-array (on rotated array),
Tue: peak-index-in-a-mountain-array (on mountain array),
Wed: search-a-2d-matrix (on special 2D matrix; design an o(mn) solution; ignore I/O cost),
Thu: guess-number-higher-or-lower (interactive binary search),
Fri: powx-n (implement D&C exponentiation shown in class; handle negative n),
Sat: merge-k-sorted-lists (classic k-way merge, tut02).
03a. Proof of Correctness (analysis)
Review Iterative IFib from lec01b
Review Iterative Dijkstra's algorithm
Review Recursive Fib from lec01b
Review Recursive Binary Search (also a D&C algorithm)

03b. Divide and Conquer (D&C) Algorithm (d) - 1
Review Merge Sort (again)
See modulo power/Mod Pow/modular exponentiation
Live demo: powx-n

References:
CLRS 4th ed Chapter 2.1 and 4.1-4.2
KT Chapter 5
CP4 Book 2 Chapter 3.3 (Binary Search), 4.4 (Dijkstra's), 5 (Matrix Power)
Extra exercises: the entire binary-search study plan
Assignment 1
continued
04,
01-05 Feb
tut03.pdf
Correctness + D&C (1)
Proof of Correctness
Use VisuAlgo sorting page to review Insertion Sort
Prove an Interesting' Recursive Sorting Algorithm
D&C: Finding any peak (2D)

Essential LeetCode exercises involving D&C:
Mon: snapshot-array (snapshots are in increasing order; binary searchable),
Tue: successful-pairs-of-spells-and-potions (sort, so that we can do BSTAs),
Wed: find-the-peaks (simple θ(n) complete search),
Thu: find-peak-element (O(log n) DnC, 1D; ignore I/O cost),
Fri: kth-smallest-number-in-multiplication-table (O(m log ans) DnC; BSTA; a bit of math),
Sat: find-a-peak-element-ii (DnC, 2D, tut03; ignore I/O cost).

Chinese New Year Public Holidays:
CNY Eve on Fri, 05 Feb 2027 PM
CNY Day 1 on Sat, 06 Feb 2027
CNY Day 2 on Sun, 07 Feb 2027
CNY PH in-lieu on Mon, 08 Feb 2027 (affecting tut04)
03b. Divide and Conquer (D&C) Algorithm (d) - 2
Complete the leftovers from Week 03
From computing n-th Fibonacci in O(log n) - end

04a. Lower bound of comparison-based sorting (a)
Read sorting e-Lecture slides (Slide 14 to 16-2)
Key point: Ω(n log n) to sort n-elements using comparison-based algorithm

References:
CLRS 4th ed Chapter 8.1
KT and CP4 don't have a section on lower bound of comparison-based sorting

04b. (Deterministic) Quicksort (analysis)
Read sorting e-Lecture slides (Slide 12 to 12-13)
Analysis of the average case of deterministic Quicksort
Key point: for non-randomized Quicksort algorithm, it is:
O(n^2) to sort n-elements in the worst-case but
O(n log n) to sort n-elements on average

Live demo: kth-smallest-number-in-multiplication-table

References:
CLRS 4th ed Chapter 7.1-7.2
CP4 Book 1 Chapter 2.2 (1D array processing)
Assignment 1
due Wed, 03 Feb, 23:59

Assignment 2
(03-17 Feb)
D&C-related task,
Randomized algorithm task

Has online judge component
Only the reflection component is graded
Public holidays around this period:
01. Sat, 06 Feb 2027 (end of Wk4), Sun, 07 Feb 2027, and Mon, 08 Feb 2027 (start of Wk5) - this affect CS3230 tutorial 04 (content to be adjusted)
02. Wed, 10 Mar 2027 (Wk8) will clash with our lecture time, hence Dr Rucha will do her last lecture on Week 09 instead
03. Thu, 11 Mar 2027 (Wk8) NUS Well-Being Day - this does not affect CS3230

Dr Rucha will take over from Week 05 (Randomized Algorithm), 06 (Dynamic Programming), Recess Week, 07 (Greedy Algorithm), 08 (PH), and 09 (Amortized Analysis)
Public holiday around this period:
01. Fri, 26 Mar 2027 (end of Wk10) - this does not affect CS3230

Dr Chen Yu will take over from Week 10 (Problem Reduction), 11 (NP-complete), 12 (Order Statistics), and 13 (Summary and Revision)