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 fourth time Prof Steven Halim (co-)teaches CS3230. This time, he is with Prof Chang Yi-Jun. For S1 AY24/25, we are expecting ~425 (so all can fit at LT11 and we can disband L2-E-Learn lecture group), but with an upperbound of max 540 CS3230 students (it was 405 pax in S2 AY22/23 and 362 pax in S2 AY23/24).

As of Thu, 25 Jul 2024, the class size is 392.

Important information:

  1. Lecturers:
    Chang Yi-Jun,
    Steven HALIM.

    CS3230 have been changing hands so frequently in recent AYs and the experience varies:
    S1 AY22/23: Arnab Bhattacharyya+Prashant Nalini Vasudevan → S2 AY22/23: Diptarka Chakraborty+Steven Halim →
    S1 AY23/24: Arnab Bhattacharyya+Rahul Jain → S2 AY23/24: Diptarka Charkraborty+Steven Halim+Sanjay Jain;
    S1 AY24/25: Chang Yi-Jun+Steven Halim; S2 AY24/25: Sanjay Jain+Warut Suksompong+Arnab Bhattacharyya;
    CS3230 in both S1+S2 of AY 24/25 should now be more similar than before as I (Prof Halim) transfer S2 knowledge to S1 version.

    Rating
    (out of 5.0)    		 Aug-Nov 24
    (n=1??/392?)
    ≥ 50%+?    		 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 (target) 3.8 ▼ 3.9 ▲ 3.8
    Course difficulty (SoC avg lvl 3000 ~3.8) ≤ [4.2..4.3] (let's reduce...) 4.5 ▲, too hard :(... 4.4 ▲ 4.0
    Steven's teaching (SoC avg lvl 3000 ~4.2) ≥ 4.3 (target) 4.2 == 4.2 ▲ 4.0
  2. Teaching Assistants:
    3. There are 17 tutorial groups, all are 1-hour block (effective 45m), all are at COM1-0209 (SR9) — except TG04 venue is at COM1-0210 (SR10).
    7 sessions are on Wednesdays, 4 are on Thursdays, and the other 6 on Fridays.
    PS: TG08-TG10 are removed because Wed 3-6pm are blocked for NUSOne project.
    Prof Halim has completed TA selection by 23 July 2024.
    Thanks for all who have applied.
    Below is the session to TA mapping information.

    Time (ID) Wed (size/cap) (ID) Thu (size/cap) (ID) Fri (size/cap)
    08-09 (01) @dominic (??/24)
    09-10 (02) @aprup (??/24)
    10-11 (03) @kurumi (??/24) (15) @sleeping (??/24)
    11-12 (04) @sevant (??/24) (16) @wongkj (??/24)
    12-13 (05) @bryanckh1 (??/24) (11) @huajun (??/24)
    13-14 (06) @x1213 (??/24) (12) @asleep (??/24)
    14-15 (07) @yalechen (??/24) (17) @flicker_v (??/24)
    15-16 NUSOne (18) @aussiroth (??/24)
    16-17 NUSOne (13) @lovemathb (??/24) (19) @hithisisjj (??/24)
    17-18 NUSOne (14) @chocolate (??/24) (20) @naman8667 (??/24)

    List of Wednesday TAs (ordered using Lab Group Number):

    1. @dominic, Dominic Berzin Chua Way Gin (has done IT5003 TA before)
    2. @aprup(.kale), Kale Aprup Vinay (has done CS2040S/CS2030S/CS1101S TA before, peak rating 4.6 at CS1231S+CS2040S, also CS2109S TA)
    3. @kurumi, Tan Wei Seng (has done CS3230 TA before with rating 4.4, peak rating 4.6 at CS3241, also CS3241 TA)
    4. @sevant, Stanve Avrilium Widjaja (new TA, but IMO G 2020)
    5. @bryanckh1, Bryan Chan Kah Hoe (also CS2040 TA)
    6. @x1213, Prof Chang Yi-Jun (taking 1 tutorial group)
    7. @yalechen, Chen Yanyu (has done CS3230 TA before)

    List of Thursday TAs (ordered using Lab Group Number):

    1. @huajun, Teow Hua Jun (has done CS3230 TA before)
    2. @asleep, Ling Yan Hao (GT, has done CS3230 TA before)
    3. @lovemathb(oy), Huang Xing Chen (has done CS3230 TA before)
    4. @chocolate, Nguyen Doan Phuong Anh (has done CS3230/CS1231S/CS2040S TA before, peak rating 4.6 at CS2040S, also CS1231S TA)

    List of Friday TAs (ordered using Lab Group Number):

    1. @sleeping(pants), Ramanathan Kumarappan (has done CS2109S TA before)
    2. @wongkj, Wong Kai Jie (has done CS1231S TA before)
    3. @flicker_v(ieri), Juan Carlo Vieri (new TA)
    4. @aussiroth, Alvin Yan Hong Yao (GT, has done CS3230 TA before)
    5. @hithisisjj, Teoh Jun Jie (has done CS4234 TA before with rating 4.6, peak rating 4.8 at CS2100+CS1231S, also CS3241 TA)
    6. @naman8667, Agrawal Naman (has TA-ed so many other courses before, peak rating 4.8 at IT1244, also IT1244 TA)

  3. Consultation Hours: TBA
  4. Have you passed (or exempted from) CS2040 (or its equivalents/variants)? You have to... This course assumes that you have passed the lower-level DSA course.
  5. Have you passed (or exempted from) MA1100/CS1231 (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 many times in this course)
    • Divide and Conquer (D&C)
    • Randomized Algorithms
    • Dynamic Programming (DP)
    • Greedy Algorithms
    • Order Statistics
  • Analysis:
    • Asymptotic Analysis
    • Recurrences and Master Theorem
    • Proof of Correctness of Iterative and Recursive Algorithms
    • Probabilistic Analysis of Randomized Algorithms
    • Amortized Analysis
    • NP-completeness

Course Registration Additional FAQ

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

Q: Will CS3230 S1 AY 2024/25 has onsite components?
A: Yes. Almost all class activities are onsite (will be 100% onsite if L2 is cancelled). We will have two lecture groups each Tuesday, 10am-12nn (L1 is onsite at the very big LT11 (first 450 pax) and L2 is online class — the rest up to student number 540 — but L2 will be cancelled if class size is ≤ 450). However, from past experience, anyone who prefers to study live (especially from the L2 group) shall just appear onsite. Lectures will be recorded centrally by NUS CIT.
Q: I will be taking ATAP too, can you approve me taking CS3230 alongside doing ATAP?
A: Latest official reply (23 July 2024): The default answer from Prof Halim and from UG/IR office is a "NO, Take CS3230 in S2 AY24/25 or latter semester instead". However, do appeal to Prof Halim if your case is very special, e.g., if this is your last available semester to take CS3230 (e.g., going for exchange next semester and wanting to take S1 advanced algorithm courses in S1 of your final year, e.g., my previous other CS4234 course).
Q: I want to take CS3230 and another course that has (lecture) timetable clash with CS3230, i.e., overlap with Tue 10am-12nn time window. Can you give me a timetable clash waiver?
A: Auto reply: 99% no. Contact UG office for appeal. Only contact Prof Halim if you are sure your case is special.
Q: Can I audit CS3230?
A: CS3230 is a core course and we generally do not accept students auditing CS3230. Email Prof Halim (dcssh) directly for case-by-case appeal. Students who are outbidded this semester are generally not allowed to audit CS3230 this semester, just read the course officially next sem/next year.
Q: Do I have to buy any textbook for this course?
A: Generally, we do not requite 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)
Q: Can I S/U this course?
A: No.
Q: Is CS3230 under Yi-Jun+Steven a flipped classroom course?
A: Not yet, Prof Halim still need to go through a few more iterations to improve the material before we can be confident enough to flip (some lectures of) the class.

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

News

Date News

Lesson Plan

The S1 AY 2024/25 timetable below is still tentative, especially those that are highlighted with pink color.

Week Lecture
Tue 10am-12nn
Venue: LT11 (450 pax)+E-Learn (the rest)		 Tutorial
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
01,
12-16 Aug 		01. Course Admins
Asymptotic Analysis (analysis)
Model of Computation (Word-RAM)
Experiment with Fibonacci cpp|py|java code and its recursion tree vs DAG
Solve this (optional) simple Fibonacci task: rijeci (at open.kattis; not tracked)
Formal definitions of Big-O, Ω, Θ o, ω with helper xlsx file to draw the charts

References:
Review Asymptotic_Analysis-Useful_Facts.pdf
CLRS 4th ed Chapter 1-2-3
KT Chapter 2
CP4 Book 1 Chapter 1.3.3; Book 2 Chapter 5 (Fibonacci)
 		Not Started Not Started
02,
19-23 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, Recursion Tree, Master Theorem case 1|2|3, and Substitution Method
Use this Master Theorem tool from Baylor University

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
(23 Aug-06 Sep)
Asymptotic Analysis,
Recurrences/Master Theorem
03,
26-30 Aug 		03. Proof of Correctness (analysis)
Use VisuAlgo SSSP page to review Dijkstra's algorithm
Divide and Conquer (D&C) Algorithm (design) part 1
Quick review of Merge Sort (again)
Use VisuAlgo sorted array page and try (binary) search (lowerbound/upperbound)
Use VisuAlgo recursion page to see binary search/modulo power
Solve these (optional) tasks: guess (interactive Binary Search),
checkingforcorrectness (Mod Pow), and porpoises (Harder Fibonacci; needs Mod Pow too)

References:
CLRS 4th ed Chapter 2.1 and 4.1-4.2
KT Chapter 5
CP4 Book 2 Chapter 3.3 (Binary Search), 5 (Matrix/Modulo Power)
 		tut02.pdf
Recurrences
Telescoping
Master Theorem
Substitution Method
Recursion Tree
 		Written Assignment 1
continued
04,
02-06 Sep 		03. D&C Algorithm (design) part 2
Complete the leftovers from Week 03
From [???] - end
04a. Lower bound of comparison-based sorting (analysis)
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 specific section on lower bound of sorting
04b. (Deterministic) Quicksort (analysis)
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 - Correctness + D&C
Proof of Correctness (TBC)
D&C: Finding any peak (2D)
 		Written Assignment 1
due Fri, 06 Sep, 23:59

Programming Assignment 1
(06-20 Sep)
D&C task,
Randomized algorithm task

Not using nus.kattis
Only the reflection component is graded
(DnC time complexity analysis;
Randomized algorithm experiment results)
05,
09-13 Sep 		05. Randomized Algorithms (design)
Randomized Quicksort (analysis)
Read sorting e-Lecture slides (Slide 12 to 13-2)
Key point 1: Randomization can speed-up certain algorithms
Key point 2: Indicator random variable + Lineary of Expectation for analysis

References:
Review Probability-Revision.pdf
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 - D&C:
Polynomial Mult
Decision Trees
 		Programming Assignment 1
continued
06,
16-20 Sep 		06. Dynamic Programming (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.

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
 		Tut05 - Randomized Algorithms
Math: Probabilistic Analysis
 		Programming Assignment 1
due Fri, 20 Sep, 23:59

Programming Assignment 2
(20 Sep-11 Oct)
DP task,
Greedy task

Not using nus.kattis
Only the reflection component is graded
(DP opt struct+overlap+time complexity analysis;
Greedy opt struct+greedy choice proof)
Recess Week, 21-29 Sep 2024
You can take a break this week :)
07,
30 Sep-04 Oct 		07. Greedy Algorithms (design)
Fractional Knapsack
Huffman Coding

References:
CLRS 4th ed Chapter 15
KT Chapter 4
CP4 Book 1 Chapter 3.4
Midterm Test
Venue: TBA
Date and Time: TBA

Midterm Test Past Paper:
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).
 		Tut06 - Dynamic Programming
Convex Polygon Triangulation
FAQ: Included in Midterm
 		Programming Assignment 2
Continued
08,
07-11 Oct 		08. Amortized Analysis (analysis)
Try the 'increment' operation at bitmask visualization
Try the 'multipush/pop' operation at Stack visualization
Try the 'multienqueue/dequeue' operation at Queue visualization
Try the 'resize-able array doubling' operation at array 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
 		Programming Assignment 2
due Fri, 11 Oct, 23:59

Written Assignment 2
(11-25 Oct)
Amortized Analysis,
Problem Reduction
09,
14-18 Oct 		09. Problem Reductions and Intractability
The concept of reductions (in polynomial time)
See the preview of VisuAlgo new reductions page (just starting)
Use VisuAlgo mvc page for two NP-complete problems VC and IS

References:
CLRS 4th ed Chapter 34
CP4 Book 2 Chapter 8.6 (NP-hard/complete Problems)
 		tut08.pdf
Amortized Analysis
Aggregate method (not recommended)
Accounting method
Potential method
 		Written Assignment 2
Continued
10,
21-25 Oct 		10. Introduction to NP-completeness (analysis)
See VisuAlgo reductions page (the overview then 3-SAT ≤p IS)

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 last lecture on Week 13
 		Tut09 - Reduction
Use VisuAlgo new reductions page
for 2 out of 4 questions
FAQ: Could be the hardest Q in the Final
 Written Assignment 2
due Fri, 25 Oct, 23:59

Written Assignment 3
(25 Oct-08 Nov)
NP-complete Proof,
One past final assessment question
11,
28 Oct-01 Nov 		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:
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
Want to know how to deal with NP-hard optimisation problems?
PS: We only learn how to "recognize NP-hard" problems in CS3230
PS: This is not examinable
Prof Chang Yi-Jun:
11c. Preview of CS5330 - Randomized Algorithms
Want to know more about randomized algorithms?
Sharing about algorithm theory research
PS: This is not examinable
Makeup Midterm Test Time Window
Only announced to affected students
 		Thu, 31 Oct 2024 is Deepavali PH

Additionally, Fri, 01 Nov 2024 is chosen as
NUS well-being day S1 AY 2024/25

CS3230 Tutorials this Wed/Thu/Fri are all cancelled
Enjoy our short break here
 		Written Assignment 3
Continued
12,
04-08 Nov 		12a. Linear-Time Sorting (design and analysis)
(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

References:
CLRS 4th ed Chapter 8.2-8.3
CP4 Book 1 Chapter 2.2.2 (Counting and Radix Sort)
12b. Linear-Time Selection (design and analysis)
Expected Linear-Time Selection, see (unsorted) array page; try "Select" → "Quickselect"
Worst-case Linear-Time Selection (not in VisuAlgo)
Dynamic Order Statistics (with data structure)

References:
CLRS 4th ed Chapter 7 (QS) + 9 (OS)
KT Chapter 13 (some examples, e.g., 13.5 (QS))
CP4 Book 1 Chapter 2.3.4 (OST)
Search for keyword 'Randomized Algorithm' in CP4 Book 1+2, index section
 		Tut10 - NP-complete
See VisuAlgo reductions page
(3-)CNF-SAT ≤p SUBSET-SUM (not ready)
VC ≤p HS
This question type may be the hardest Q in the Final
 Written Assignment 3
due Fri, 08 Nov, 23:59
13,
11-15 Nov 		13. Summary and Revision
(through the lens of (mostly) Graph Algorithms)
Mostly 2nd half stuffs:
Use VisuAlgo mvc page for Independent Set-related randomized algorithm review
Visit various VisuAlgo pages on Amortized Analysis review
Use VisuAlgo sssp page for Bellman-Ford (DP) review
Use VisuAlgo mst page for Prim's (Greedy) review
Reduction and NP-completeness review
 		Tut11 - Wrap Up
1 DP — from Week 06,
1 Greedy — from Week 07,
1 Amortized — from Week 08,
1 NP-complete — from Week 09-10
1 Linear-Time stuff — from Week 12
 		No more assignment :)
Study Week, 16-22 Nov 2024
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 (will be ours).
NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Fri, 29 Nov 2024, 2.30-5.00pm (we will use this 2.5h format)
Venue: TBA
Open book
Other details TBA