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.9..4.0] (tgt) | [3.9..4.0] (tgt) | 3.9 (Joint-PB) ▲ | 3.8 ▼ | 3.9 ▲ | 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.4 ▲ | 4.0 |
| Prof Halim's teaching (SoC CS avg lvl 3000 ~4.2) | [4.3..4.4] (tgt) | [4.3..4.4] (tgt) | 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) | ||
| 15-16 | NUSOne | ||
| 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:
For other applicants, thanks for your applications; If you are still keen to do other TA job, do reapply to TA other courses in S1 AY 2025/26.
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 | Lecture Tue 10am-12nn Venue: LT11 (≤450 pax) |
Tutorial Timings: Wed, Thu, or Fri (1 hr/wk) Venue: COM1-0209 (SR9) |
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 Just self-review CS2040S content |
Has Not Started Essential LeetCode exercises (CS2040S Review): Mon: two-sum (the first problem in LeetCode, uses CS2040S techniques), Tue: Wed: Thu: Fri: Sat: |
Has Not Started |
|
01, 10-14 Aug |
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) 01b. Asymptotic Analysis (analysis) Introduction Model of Computation (Word-RAM) Experiment with Fibonacci cpp|py|java code and its recursion tree vs DAG Live Tue Lec demo: climbing-stairs (at LeetCode) 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 Essential LeetCode exercises involving asymptotics: Mon: Tue: climbing-stairs (modeling, Fibonacci-like), Wed: fibonacci-number (does an exponential algorithm still passes?), Thu: n-th-tribonacci-number (extension of the first lecture), Fri: k-radius-subarray-averages (design a little-o(n^2) solution; what does this mean?). Sat: |
Has Not Started |
|
02, 17-21 Aug |
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 Tue Lec 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 |
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: |
Written Assignment 1 (21 Aug-04 Sep) Asymptotic Analysis, Recurrences/Master Theorem Find WA1.pdf at Canvas - Assignments |
|
03, 24-28 Aug |
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 (at LeetCode) 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 |
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: Discussed in the third lecture, 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: successful-pairs-of-spells-and-potions (sort, so that we can do BSTAs). Sat: |
Written Assignment 1 continued |
|
04, 31 Aug-04 Sep |
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) |
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: |
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 |
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 (at LeetCode) 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 |
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: Discussed in the fifth lecture, Wed: peak-index-in-a-mountain-array (binary search variant), Thu: h-index (easier than in tut04), Fri: h-index-ii (tut04), Sat: convert-sorted-array-to-binary-search-tree (DnC BST construction). |
Programming Assignment 1 continued |
|
06, 14-18 Sep |
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 (at LeetCode) 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 |
tut05.pdf Randomized Algorithms Freivald's algorithm revisited Randomised communication protocol Random cut of a graph Essential LeetCode exercises involving Randomization: Mon: Tue: Discussed in the sixth lecture, Wed: linked-list-random-node (hint: this), Thu: shuffle-an-array (hint: this), Fri: generate-random-point-in-a-circle (hint: this). Sat: |
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 |
07. Greedy Algorithms (design) Fractional Knapsack (comparison with 0/1-Knapsack that needs DP) Huffman Coding Live demo: assign-cookies (at LeetCode; greedy bipartite matching) 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). |
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: Discussed in the seventh lecture, Wed: uncrossed-lines (easy if you understand Lec06), Thu: combination-sum-iv (easy if you understand Lec06), Fri: minimum-score-triangulation-of-polygon (tut06), Sat: |
Programming Assignment 2 Continued |
|
08, 05-09 Oct |
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 (at LeetCode) 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 |
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: Discussed in the eighth lecture, Wed: ipo (doable if you understand Lec07), Thu: non-overlapping-intervals (tut07), Fri: boats-to-save-people (tut07), Sat: 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) |
Programming Assignment 2 due Sat, 10 Oct, 23:59 (one day after Well-Being Day) Written Assignment 2 (08-23 Oct) (one day before Well-Being Day) Amortized Analysis Problem Reduction |
|
09, 12-16 Oct |
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 (at LeetCode) References: CLRS 4th ed Chapter 34 CP4 Book 2 Chapter 8.6 (NP-hard/complete Problems) |
tut08.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: Discussed in the ninth lecture, Wed: daily-temperatures (from back; monotonic stack; analyze with amortized analysis), Thu: next-greater-element-ii (monotonic stack; analyze with amortized analysis), Fri: implement-queue-using-stacks (final S2 AY22/23, B3), Sat: |
Written Assignment 2 Continued |
|
10, 19-23 Oct |
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 (at LeetCode) 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 |
tut09.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: Rest day (Deepavali PH), Tue: Rest day (NUS well-being day), Wed: house-robber-ii (extension of Lec09 demo), Thu: partition-equal-subset-sum (PARTITION, tut09), Fri: shortest-path-visiting-all-nodes (weighted HAM-PATH; need bitmask), Sat: |
Written Assignment 2 due Fri, 23 Oct, 23:59 Written Assignment 3 (23 Oct-06 Nov) NP-complete 1, NP-complete 2 |
|
11, 26-30 Oct |
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 (QuickSelect real implementation) 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) |
tut10.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 1: Mon: partition-to-k-equal-sum-subsets (PARTITION into k (not just 2) subsets?; need bitmask), Tue: Discussed in the tenth lecture, 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: coin-change-ii (COIN-CHANGE (end of Lec06) is kinda KNAPSACK too), Sat: |
Written Assignment 3 Continued |
|
12, 02-06 Nov |
12. Special lectures/Make-up midterm This semester, we have full 13 lecture slots Most other semesters, there are only 12 (clash with PH or NUS well-being day) Thus, we plan to run preview of our "more advanced algorithm courses" as per learning objective of CS3230 Prof Steven Halim's more advanced classes: 11a. Preview of CS3233 - Competitive Programming Want to know how to recognize and implement what we learn in CS3230: Complete Search; DnC; DP; Greedy; or Randomized algorithms quickly? PS: Improving this aspect may indirectly help you for CS3230 final 11b. Preview of CS4234 - Optimisation Algorithms In CS3230, we learn to "recognize NP-complete" problems, e.g., CLIQUE ≤p VC Many NPc-complete decision have NP-hard optimization, e.g., VC ≤p MVC (but MVC is not in NP) Assuming P≠NP, want to know 3C2 ways to deal with such problems? Prof Chang Yi-Jun's more advanced class: 11c. Preview of CS5330 - Randomized Algorithms Want to know more about randomized algorithms? Makeup Midterm Test Time Window Only announced to ?? student(s) with official leave During NUSOne timeslot on Wed, 28 Oct 2026, 3-5pm SGT (TBC) |
tut11.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: Discussed in the eleventh lecture, 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: |
Written Assignment 3 due Fri, 06 Nov, 23:59 (Optional if your CA ≥ 30/30) |
|
13, 09-13 Nov |
Singapore National Day on Sun, 09 Aug 26 The following Mon, 10 Aug 26 is a Public Holiday this class is not affected 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 |
tut12.pdf We will (try to live-)solve up to SIX LeetCode problems: The chosen tasks from last S1 AY25/26 are was: 1: heaters (D&C — from Week 03+04). 2: maximum-score-from-performing-multiplication-operations (DP — from Week 06), 3: most-profit-assigning-work (Greedy — from Week 07), 4: online-stock-span (Amortized — from Week 08), 5: target-sum (NP-complete — from Week 09+11), 6: |
No more assignment :) |
|
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: TBC Venue: TBC Open book, no electronic device (except one calculator) |
|||