CS3230: ace the component, not just read the notes
Your complete guide to National University of Singapore's design and analysis of algorithms course. See where the marks are, work real practice questions, and study with an AI tutor that knows CS3230.
Sia generates CS3230 practice questions, walks through asymptotic analysis and recurrences step by step, and quizzes you on the material the component that weights most heavily.
Worked example
Solve the recurrence T(n) = 2T(n/2) + n log n using the Master Theorem, or explain why it does not apply directly.
Compute n^{log_b a} = n^{log_2 2} = n.
Case 3 of the basic theorem needs polynomial separation, so none of the three basic cases applies.
The extended (CLRS 4th edition) form handles f(n) = Θ(n^{log_b a} log^k n) with k = 1, giving T(n) = Θ(n log² n). A recursion tree confirms: log n levels each costing about n log n.
The trap: Picking Θ(n log n) because f(n) 'looks like' the answer, or applying case 3 without checking the polynomial-separation condition. The exam rewards stating why a case does not apply. classic slip!
One component decides 40% of your grade. No make-up session. This whole page is built around that.
Overview
What CS3230 is, and where it sits
CS3230 Design and Analysis of Algorithms is the core algorithms course of the NUS Computer Science curriculum, taught in Semester 1 AY2026/27 by Chang Yi-Jun, Steven Halim and Rahul Jain in three blocks of weeks. It assumes CS2040S and the discrete mathematics of CS1231S or MA1100, and cannot be taken on S/U.
The course splits into design and analysis. Design covers divide and conquer, randomised algorithms, dynamic programming, greedy algorithms, linear-time sorting and order statistics. Analysis covers asymptotic notation, recurrences and the Master Theorem, proofs of correctness, the comparison-sort lower bound, probabilistic analysis, amortised analysis and NP-completeness. Lectures run Friday 2-4pm with weekly VisuAlgo quizzes; 21 tutorial groups meet from Week 2.
Assessment is 30% continuous assessment (capped), a 30% midterm test on the Saturday of Week 7 and a 40% written final assessment. The continuous component is built from lecture quizzes, tutorial participation and the best four of five written assignments; the course page notes that most students score the full 30%, which makes the two tests the real grade discriminator.
Always treat your own course outline and the exam timetable as authoritative.
Difficulty & time commitment
Is CS3230 hard, and how much time does it take?
CS3230 is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the course.
Is this course for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You write proofs comfortably from CS1231S and enjoy arguing why an algorithm is correct, not just that it works.
- You attend or watch every lecture and do the VisuAlgo quiz — 2% is there for free.
- You attempt every tutorial question before class and volunteer to present; 3% and a lot of exam practice.
- You start each assignment early; five are set, the best four count, and there are no extensions.
You may struggle if
- You treat the assignments as coding tasks; the submissions are written proofs and analyses.
- You skip Week 1-2 asymptotics because they feel familiar; every later analysis question depends on them.
- You leave reductions and NP-completeness to the last fortnight; the course flags them as the hardest final questions.
- You rely on memorised recurrences instead of being able to solve a new one.
- Keep a running sheet of every recurrence pattern and the Master Theorem case it falls under.
- For every algorithm covered, write down the invariant or the inductive claim and practise stating it in one sentence.
- Work the published past midterm and final papers under time; the team publishes recent papers for its own runs.
- Practise reductions in both directions: say which problem is known hard and which you are showing hard, and check the direction every time.
Syllabus
The 12 topics, week by week
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
T1 · Asymptotic analysis
Week 1; CLRS ch. 1-3Word-RAM model; formal definitions of O, Ω, Θ, o and ω; ranking functions.
T2 · Recurrences and the Master Theorem
Week 2; CLRS ch. 4Telescoping, substitution, recursion trees and the three Master Theorem cases.
T3 · Proof of correctness
Week 3; tutorial 3Loop invariants for iterative algorithms and induction for recursive ones.
T4 · Divide and conquer
Weeks 3-4; CLRS ch. 2, 4Merge sort, binary search, fast exponentiation, peak finding, polynomial multiplication.
T5 · Sorting lower bound and Quicksort analysis
Week 4; CLRS ch. 7-8Decision trees and Ω(n log n); average case of deterministic Quicksort.
T6 · Randomised algorithms
Week 5; CLRS ch. 7Indicator random variables, linearity of expectation, union bound, randomised Quicksort, Freivalds' algorithm.
T7 · Dynamic programming
Week 6; CLRS ch. 14Fibonacci, LCS, knapsack, coin change, LIS, polygon triangulation; DP as DAG.
T8 · Greedy algorithms
Week 7; CLRS ch. 15Fractional knapsack, Huffman coding, activity selection and exchange arguments.
T9 · Amortised analysis
Week 9; CLRS ch. 16Aggregate, accounting and potential methods on counters, stacks and resizable arrays.
T10 · Problem reductions and intractability
Week 10; CLRS ch. 34Polynomial-time reductions; vertex cover, independent set and the idea of hardness.
T11 · NP-completeness
Week 11; CLRS ch. 34P, NP, NP-hard and NP-complete; SAT, 3-SAT, IS, VC, HS, SUBSET-SUM reductions.
T12 · Linear-time sorting and selection
Week 12; CLRS ch. 8-9Counting and radix sort; Quickselect and median-of-medians; order-statistics trees.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Continuous assessment (capped): VisuAlgo lecture quizzes, tutorial participation, best 4 of 5 written assignments | 30% | Twelve VisuAlgo lecture quizzes (up to 2%), tutorial participation (up to 3%) and five written assignments with the best four counted (about 7.5% each); the total exceeds 30% and is capped at 30%. Weeks 1-13. Capped at 30%; no assignment extensions or make-up. |
| Midterm test (120 minutes, pen and paper) | 30% | Written test of 120 minutes covering Weeks 1-7 (asymptotics to greedy). No electronics except one non-programmable calculator. Saturday of Week 7 (3 Oct 2026). One make-up session for medical or approved reasons only. |
| Final assessment (150 minutes, pen and paper) | 40% | Written assessment of 150 minutes on the whole course; open book, no electronic device except one calculator. Examination period (26 Nov 2026). No make-up session. |
- The three components sum to 100 and no separate hurdle is published. The continuous component is capped at 30% even though the pieces add to more. Missing the midterm without medical or approved grounds forfeits it; the single make-up test is described as generally harder. There is no make-up for the final.
- Midterm: 120 minutes, Weeks 1-7 material, with an easier dynamic-programming question flagged as likely. Final: 150 minutes across the whole course; the lesson plan flags greedy, amortised analysis and a reduction or NP-completeness question as expected, with the reduction usually the hardest. Recent past papers are published on the course site for the teaching team's own semesters.
This is a coursework course. Coursework carries 100% of the grade and the final assessment (150 minutes, pen and paper) is the single heaviest piece at 40%, so steady work across the semester decides your result more than any one sitting. No make-up session.
Final exam timing: During the examination period. Confirm the exact date and venue on your exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The course rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Prove a tight Θ bound for a function or rank a list of functions by growth.
- Solve a recurrence three ways and match it to a Master Theorem case.
- Write a loop-invariant proof for a short iterative algorithm.
- Compute an expected running time using indicator random variables.
Before the final heaviest topics
- Formulate a DP with a clear state, transition and base case, and give its complexity.
- Give an exchange argument for a greedy choice.
- Run an amortised analysis with the potential method.
- Write a polynomial-time reduction between two named NP-complete problems, in the correct direction.
The mistakes that cost marks
Reduction in the wrong direction. To show X is hard you reduce a known hard problem to X, not X to the hard problem. The course names this as the classic final-exam error.
Using the divergence-style shortcut. In analysis questions, showing an upper bound is not showing a tight bound; state both O and Ω when Θ is asked.
Missing the assignment window. There are no extensions; the best-four-of-five rule is the only buffer.
Teaching team
Who teaches CS3230
The bios below are factual. We do not rate lecturers; any star ratings are submitted by students who have taken CS3230.
Steven Halim
Rucha Ravi Kulkarni
Teaching team as listed in the course materials reviewed. AskSia does not rate lecturers; star ratings are submitted by students who have taken CS3230.
Formula & concept sheet
The vocabulary and formulas you must own
- Big-O, Ω, Θ
- Upper, lower and tight asymptotic bounds on a function's growth.
- Master Theorem
- A three-case rule for recurrences of the form T(n) = aT(n/b) + f(n).
- Loop invariant
- A property that holds before and after each iteration, used to prove correctness.
- Indicator random variable
- A 0-1 variable whose expectation equals a probability; the tool for expected-time analysis.
- Optimal substructure
- The property that an optimal solution contains optimal solutions to subproblems, required for DP.
- Exchange argument
- A proof that swapping an optimal choice for the greedy choice never hurts.
- Potential method
- Amortised analysis using a potential function that pre-pays for expensive operations.
- Polynomial-time reduction
- A transformation of instances of one problem into another that runs in polynomial time.
- NP-complete
- A problem in NP to which every NP problem reduces in polynomial time.
- Median of medians
- The deterministic worst-case linear-time selection algorithm.
Set texts
The prescribed reading
The syllabus references map straight onto these.
Introduction to Algorithms
.
Algorithm Design
.
Where it fits
Prerequisites, related courses & why it matters
Prerequisites: CS2040S (or equivalent) and CS1231S or MA1100. 4 units; not S/U-able; offered in Semester 1 and Semester 2, with the two semesters kept similar by the teaching team.
Your CS3230 study toolkit
Study the course with Sia, not just read about it
Each tool already knows CS3230: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
Is CS3230 hard?
Moderately hard on the six-factor rubric. The mathematics is the heaviest in the CS core and 70% sits in two written tests, but the continuous assessment is designed to be maxed out and the teaching team says failing is hard if you put in the effort.
What is the assessment breakdown?
Continuous assessment 30% (capped: lecture quizzes up to 2%, tutorial participation up to 3%, best four of five assignments at about 7.5% each), midterm test 30% and final assessment 40%, as published on the course website for S1 AY2026/27.
Who teaches it?
In S1 AY2026/27 the lecturers are Chang Yi-Jun (Weeks 1-5), Steven Halim (Weeks 6-8, course coordinator) and Rahul Jain (Weeks 9-13), with Rucha Ravi Kulkarni joining for tutorials and consultation from Week 4.
Can I S/U or audit CS3230?
No to both. It is a core course; students who miss out on a place are asked to take it in the following semester.
Do I need a textbook?
Not required. The main reference is Introduction to Algorithms (CLRS), 4th edition, with Kleinberg and Tardos and Competitive Programming 4 as secondary references.
What are the prerequisites?
CS2040S (or an equivalent data structures and algorithms course) and CS1231S or MA1100; the course page stresses that it is heavy on mathematics.
Study CS3230 with Sia
Work through asymptotic analysis, recurrences, proof of correctness and the rest of the course with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
