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.
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).
Important information:
| Rating (out of 5.0) |
Aug-Nov 26 (n=???/3??) ??% |
Aug-Nov 25 (n=252/382) 66% ▼ |
Aug-Nov 24 (n=306/434) 71% ▲ |
Jan-Apr 24 (n=222/362) 61% ▼ |
Jan-Apr 23 (n=280/405) 69% ▲ |
Jan-Apr 14 (n=46/87) 53% |
|---|---|---|---|---|---|---|
| Course feedback (SoC CS avg lvl 3000 ~3.9) | [3.8..4.0] (tgt) | 3.8 ▼ | 3.9 (Joint-PB) ▲ | 3.8 ▼ | 3.9 ▲ | 3.8 |
| Course difficulty (SoC CS avg lvl 3000 ~4.0) | [4.3..4.5] (tgt) | 4.5 == | 4.5 == | 4.5 ▲ | 4.4 ▲ | 4.0 |
| Prof Halim's teaching (SoC CS avg lvl 3000 ~4.2) | [4.2..4.4] (tgt) | 4.3 ▼ | 4.4 (PB) ▲ | 4.2 == | 4.2 ▲ | 4.0 |
| Time | (ID) Wed (size/cap) | (ID) Thu (size/cap) | (ID) Fri (size/cap) |
|---|---|---|---|
| 08-09 | (01) TBC (??/20) | ||
| 09-10 | (02) TBC (??/20) | (08) TBC (??/20) | |
| 10-11 | (03) TBC (??/20) | (09) TBC (??/20) | (15) TBC (??/20) |
| 11-12 | (04) TBC (??/20) | (10) TBC (??/20) | (16) TBC (??/20) |
| 12-13 | (05) TBC (??/20) | (11) TBC (??/20) | (17) TBC (??/20) |
| 13-14 | (06) TBC (??/20) | (12) TBC (??/20) | (18) TBC (??/20) |
| 14-15 | (07) @halim (??/20) | [Our lecture slot at LT11] | |
| 15-16 | NUSOne | [Our lecture slot at LT11] | |
| 16-17 | NUSOne | (13) TBC (??/20) | (19) TBC (??/20) |
| 17-18 | NUSOne | (14) TBC (??/20) | (20) TBC (??/20) |
List of TAs (Wednesdays):
List of TAs (Thursdays):
List of TAs (Fridays):
Part-time TAs applications:
This is what you will learn this semester:
If you have any important questions regarding this course, email dcssh at nus (course coordinator), cyijun at nus, or dcsrahul at nus. Relevant answers will be posted here to reach wider audiences.
Note: This course registration section will not be prominent from Week 1 of S1 AY 2026/27 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
| Date | News |
|---|
| 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 (CS2040S Review): Mon: two-sum (the first problem in LeetCode, uses CS2040S techniques), Tue: [TBC] Wed: [TBC] Thu: [TBC] Fri: [TBC] Sat: [TBC] |
Has Not Started Just self-review CS2040S content |
Has Not Started |
|
01, 10-14 Aug |
Has Not Started Essential LeetCode exercises involving asymptotics: Mon: [TBC], Tue: [TBC], Wed: fibonacci-number (does an exponential algorithm still passes?), Thu: n-th-tribonacci-number (extension of the first lecture), Fri: climbing-stairs (modeling, Fibonacci-like), Sat: k-radius-subarray-averages (design a little-o(n^2) solution; what does this mean?). |
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 AY25/26 edition — will be refreshed) 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 (Merge of Merge Sort (lec02); in array format), Tue: merge-two-sorted-lists (Merge of Merge Sort again; but in SLL format), Wed: merge-k-sorted-lists (extension of merge on k sorted lists, also see tut02 later), Thu: sort-colors (design Θ(n) solution with O(1) extra space), Fri: remove-duplicates-from-sorted-array-ii (design Θ(n) solution with O(1) extra space), Sat: [TBC]. |
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 (at nus.kattis; not public; a few subtasks 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 |
Written Assignment 1 (21 Aug-04 Sep) Asymptotic Analysis, Recurrences/Master Theorem Find WA1.pdf at 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 (not just the standard binary search), Tue: [DnC, TBC], Wed: powx-n (code out that D&C exponentiation; handle negative n), Thu: valid-perfect-square (avoid sqrt, but you can use mult, 'that' idea), Fri: guess-number-higher-or-lower (interactive binary search), Sat: successful-pairs-of-spells-and-potions (sort, so that we can do BSTAs). |
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) Live demo: guess-number-higher-or-lower 03b. Divide and Conquer (D&C) Algorithm (d) - 1 Review Merge Sort (again) See modulo power/Mod Pow/modular exponentiation 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 |
Written 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: search-a-2d-matrix (design a little-o(m*n) solution; ignore I/O cost), Wed: find-the-peaks (simple complete search), Thu: find-peak-element (DnC, 1D; ignore I/O cost), Fri: find-a-peak-element-ii (DnC, 2D, tut03; ignore I/O cost). Sat: [DnC, TBC]. |
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 References: CLRS 4th ed Chapter 7.1-7.2 CP4 Book 1 Chapter 2.2 (1D array processing) |
Written Assignment 1 due Fri, 04 Sep, 23:59 Programming Assignment 1 (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: sqrtx (similar to valid-perfect-square), Tue: peak-index-in-a-mountain-array (binary search variant), 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 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 |
Programming Assignment 1 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: [Randomized, TBC], Tue: [Randomized, TBC], 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), 0/1-Knapsack, and Coin Change. Experiment with more test cases beyond the static official lecture notes examples. Live demo: longest-common-subsequence 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 |
Programming Assignment 1 due Fri, 18 Sep, 23:59 Programming Assignment 2 (18 Sep-10 Oct) DP task Greedy task 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 FAQ: (Easier) DP question will be in Midterm Essential LeetCode exercises involving DP: Mon: perfect-squares (simple DP with only 1 parameter), Tue: [simple DP, TBC], 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 References: CLRS 4th ed Chapter 15 KT Chapter 4 CP4 Book 1 Chapter 3.4 Midterm Test (30%) Venue: Likely MPSH again, TBC Date and Time: Sat, 03 Oct 26 (wk7) TBC - this is our preferred date, Hall entry and exit time: TBC Mode of assessment: Hardcopy (Pen and Paper) No electronic device except one non-programmable calculator Midterm Test Past Papers (recent 3 AYs only): AY 2023/24: S1-N/A (not ours), S2-midterm.pdf, AY 2024/25: S1-midterm.pdf, S2-N/A (not ours), AY 2025/26: S1-midterm.pdf (ours), S2-N/A (not ours). |
Programming Assignment 2 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: jump-game-ii (greedy solution is much faster than systematic search), Tue: [simple greedy, TBC], Wed: ipo (doable if you understand Lec07), Thu: non-overlapping-intervals (tut07), Fri: boats-to-save-people (tut07), Sat: [medium greedy, TBC]. 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 |
Programming Assignment 2 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 cancelled, We will use this buffer slot to (try to live-)solve as many LeetCode problems involving techniques that we have learned so far: Mon: heaters (D&C — from Week 03+04), Tue: [randomized algorithm, TBC], Wed: maximum-score-from-performing-multiplication-operations (DP — from Week 06), Thu: most-profit-assigning-work (Greedy — from Week 07), Fri: counting-bits (using Lec08 explanation), Sat: [TBC]. |
08. Amortized Analysis (analysis) Try the 'increment' operation at bitmask visualization Try the 'resize-able array doubling' operation at array visualization Live demo: 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 |
Written Assignment 2 (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: partition-labels (there is a simple enough greedy strategy), Tue: implement-queue-using-stacks (final S2 AY22/23, B3), Wed: daily-temperatures (from back; monotonic stack; analyze with amortized analysis), Thu: next-greater-element-ii (monotonic stack; analyze with amortized analysis), Fri: house-robber (MWIS on line graph; DP), Sat: [NP-C, TBC]. |
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 Live demo: house-robber References: CLRS 4th ed Chapter 34 CP4 Book 2 Chapter 8.6 (NP-hard/complete Problems) |
Written Assignment 2 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: [NP-C, TBC], Tue: [NP-C, TBC], Wed: house-robber-ii (extension of Lec09 demo), Thu: partition-equal-subset-sum (PARTITION, tut09), Fri: house-robber-iii (MWIS on Tree; DP again), Sat: shortest-path-visiting-all-nodes (weighted HAM-PATH; need bitmask). |
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 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 |
Written Assignment 2 due Fri, 30 Oct, 23:59 Written Assignment 3 (30 Oct-13 Nov) NP-complete 1, NP-complete 2 |
|
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: partition-to-k-equal-sum-subsets (PARTITION into k (not just 2) subsets?; need bitmask), Tue: coin-change-ii (COIN-CHANGE (end of Lec06) is kinda KNAPSACK too), Wed: combination-sum-ii (find all unique SUBSET-SUM combinations; isn't this np-complete?, tut10), Thu: ones-and-zeroes (is this KNAPSACK variant? but two knapsacks?), Fri: kth-largest-element-in-an-array (implement QuickSelect), Sat: [harder order statistics, TBC]. |
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) |
Written Assignment 3 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) Essential LeetCode exercises involving Linear-time Sorting/Selection: Mon: find-the-kth-largest-integer-in-the-array (nums given upfront; static; same as Tue version), Tue: , Wed: query-kth-smallest-trimmed-number (selection problem), Thu: kth-smallest-element-in-a-bst (also see the follow-up), Fri: kth-largest-element-in-a-stream (k is constant, but data come as a stream), Sat: . |
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: N/A for the finale, see last tutorial 12 |
Written Assignment 3 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 later). 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: TBC Open book, no electronic device (except one calculator) |
|||