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 fifth time Prof Steven Halim (co-)teaches CS3230. This time, he is with Prof Chang Yi-Jun and Prof Prashant Nalini Vasudevan. For S1 AY2025/26, we are expecting ~425 (so all can fit at LT11 and we can continue to just disband L2-E-Learn lecture group). Historically, it was 434 in S1 and 299 in S2 AY 2024/25.
As of Mon, 16 Jun 2025, we are expecting [400-450] students.
Important information:
| Rating (out of 5.0) |
Aug-Nov 25 (n=???/???) ??% |
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 avg lvl 3000 ~3.9) | [3.9..4.0] (tgt) | 3.9 (Joint-PB) ▲ | 3.8 ▼ | 3.9 ▲ | 3.8 |
| Course difficulty (SoC avg lvl 3000 ~3.9) | [4.3..4.4] (tgt) | 4.5 == | 4.5 ▲ | 4.4 ▲ | 4.0 |
| Prof Halim's teaching (SoC avg lvl 3000 ~4.2) | [4.3..4.4] (tgt) | 4.4 (PB) ▲ | 4.2 == | 4.2 ▲ | 4.0 |
Confirmed TAs (information on which tutorial group that these TAs are taking will be decided later):
Senior students who are interested to be TA (did (very) well in recent CS3230) should contact Prof Halim (PIC for tutorial) ASAP.
List of known applicants (we need around 10-11 more part-time TAs, TBC).
PS: This list is currently in FCFS mode, no ranking yet.
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 prashvas 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 2025/26 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
| Date | News |
|---|
The S1 AY 2025/26 timetable below is still tentative, especially those that are highlighted with pink color.
| Week | Lecture Tue 10am-12nn Venue: LT11 (≤450 pax) |
Tutorial Timings TBA Venues TBA |
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 Aug |
Has Not Started Just review CS2040S content |
Has Not Started Singapore National Day on Sat, 09 August 2025 |
Has Not Started |
|
01, 11-15 Aug |
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 demo: fibonacci-number (at LeetCode) Formal definitions of Big-O, Ω, Θ, o, ω with helper xlsx file to draw the charts References: Review Asymptotic_Analysis-Useful_Facts.pdf (to be added as appendix of lec01b) CLRS 4th ed Chapter 1-2-3 KT Chapter 2 CP4 Book 1 Chapter 1.3.3; Book 2 Chapter 5 (Fibonacci) Extra exercises: climbing-stairs, n-th-tribonacci-number, rijeci (these exercises will be quickly revisited in Week 06) |
Has Not Started | Has Not Started |
|
02, 18-22 Aug |
02. Recurrences and Master Theorem (analysis) Quick review of Merge Sort especially its analysis Review Merge Sort implementation at SortingDemo.cpp | py | java Solve this (optional) task that forces you to unbox Merge Sort: ultraquicksort 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) 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 (to offset Deepavali-NUS Well-Being Day in S1) onsite at our tutorial venue (to be booked one week in advance) Checking Definitions: O, Ω, Θ o, ω, Limits True/False tests Ranking functions |
Written Assignment 1 (22 Aug-05 Sep) Asymptotic Analysis, Recurrences/Master Theorem |
|
03, 25-29 Aug |
03a. Proof of Correctness (analysis) Review Iterative IFib from lec01b Review Iterative Selection Sort Review Iterative Dijkstra's algorithm Review Recursive Fib from lec01b Review Recursive Binary Search (also a D&C algorithm) Live demo: guess (at open.kattis) 03b. Divide and Conquer (D&C) Algorithm (d) - 1 Review Merge Sort (again) See modulo power/Mod Pow/modular exponentiation Even faster Fib computation using 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 |
Written Assignment 1 continued |
|
04, 01-05 Sep |
03b. Divide and Conquer (D&C) Algorithm (d) - 2 Complete the leftovers from Week 03 From Matrix Multiplication (Strassen's) - 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 Experiment to solve this (optional) task: pivot (QuickSort Partition review) 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) Extra exercise: find-peak-element. |
Written Assignment 1 due Fri, 05 Sep, 23:59 Programming Assignment 1 (05-19 Sep) D&C-related task, Randomized algorithm task Has online judge component (optional) Only the reflection component is graded |
|
05, 08-12 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) Summary: 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 |
Programming Assignment 1 continued |
|
06, 15-19 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 |
Programming Assignment 1 due Fri, 19 Sep, 23:59 Programming Assignment 2 (19 Sep-10 Oct) DP task Greedy task Has online judge component (optional) Only the reflection component is graded |
|
Recess Week, 20-28 Sep 2025 You can take a break this week :) |
|||
|
07, 29 Sep-04 Oct |
07. Greedy Algorithms (design) Coin Change (complete search, DP, vs greedy version) Fractional Knapsack (comparison with 0/1-Knapsack that needs DP) Huffman Coding Live demo: canvas (at open.kattis) References: CLRS 4th ed Chapter 15 KT Chapter 4 CP4 Book 1 Chapter 3.4 Midterm Test (30%) Details TBA But we are aiming either Sat, 05 Oct 25 (wk7) or 11 Oct 25 (wk8) Somewhere in MPSH 2.5 hours block booking (effective 2 hours midterm test) Midterm Test Past Papers (recent 3 AYs only): AY 2022/23: S1-N/A (not ours), S2-midterm.pdf, AY 2023/24: S1-N/A (not ours), S2-midterm.pdf, AY 2024/25: S1-midterm.pdf (ours), S2-N/A (not ours). |
tut06.pdf Dynamic Programming Convex Polygon Triangulation Extra exercise: minimum-score-triangulation-of-polygon (There will be at least one other) FAQ: DP question will be in Midterm |
Programming Assignment 2 Continued |
|
08, 06-10 Oct |
08. Amortized Analysis (analysis) Try the 'increment' operation at bitmask visualization Try the 'resize-able array doubling' operation at array visualization Try the 'multipush/pop' operation at Stack visualization Try the 'multienqueue/dequeue' operation at Queue visualization Live demo: To find a suitable example... 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 Extra exercise: boats-to-save-people Activity Selection Problem Extra exercise: non-overlapping-intervals |
Programming Assignment 2 due Fri, 10 Oct, 23:59 Written Assignment 2 (10-24 Oct) Amortized Analysis Problem Reduction |
|
09, 13-17 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 |
Written Assignment 2 Continued |
|
10, 20-24 Oct |
As Mon, 20 Oct 2025 is Deepavali PH and Tue, 21 Oct 2025 is NUS well-being day We do not have Tue, 21 oct 2025 lecture Makeup Midterm Test Time Window Only announced to affected student(s) NUS Online Teaching Feedback opens this Fri But this timing is too early for our course... You can wait until last lecture on Week 13 |
tut09.pdf Problem Reduction Use VisuAlgo reductions page for 2 out of 4 questions FAQ: Could be the hardest Q in the Final |
Written Assignment 2 due Fri, 24 Oct, 23:59 Written Assignment 3 (24 Oct-07 Nov) NP-complete proof, One other question |
|
11, 27-31 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: To find a suitable example... References: CLRS 4th ed Chapter 34.3-34.5 |
tut10.pdf NP-complete See VisuAlgo reductions page 3-SAT ≤p SUBSET-SUM ?? ≤p FIND-FAMILY This question type may be the hardest Q in the Final |
Written Assignment 3 Continued |
|
12, 03-07 Nov |
11. Linear-Time Sorting & Selection (d&a) (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 if we use Θ(b/r * (n+2^r)) Radix Sort Live demo: magicsequence (at open.kattis) Reduction to sorting problem... sort everything 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") 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) |
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) |
Written Assignment 3 due Fri, 07 Nov, 23:59 (Optional if your CA ≥ 40/40) |
|
13, 10-14 Nov |
13. 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: To find a suitable example... |
tut12.pdf Finale 1 DP — from Week 06, 1 Greedy — from Week 07, 1 Amortized — from Week 08 1 NP-complete — from Week 09+11 |
No more assignment :) |
|
Study Week, 15-21 Nov 2025 Final Assessment Discussions at Class Discord Final Assessment Past Papers (recent 3 AYs only): AY 2022/23: S1-N/A (not ours), S2-final.pdf, AY 2023/24: S1-N/A (not ours), S2-final.pdf, AY 2024/25: S1-final.pdf (ours), S2-N/A (not ours), NUS Online Teaching Feedback System closes on Friday of Study Week |
|||
|
Final Assessment (40%) Date and Time: Tue, 25 Nov 2025, 09.00-11.30am (we will use this 2.5h format) Venue: TBA Open book |
|||