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.

As of Mon, 18 Nov 2024, the class size as per examination list is 434.

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+Eric Han Liang Wee;
    CS3230 in both S1+S2 of AY 24/25 should now be more similar than before as I (Prof Halim) transfer S2 AY 23/24 knowledge to S1 AY 24/25 version, and later to S2 AY2 24/25 colleagues.

    Rating
    (out of 5.0)    		 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 (PB) ▲ (hasn't break ≥ 4.0 barrier, but OK) 3.8 ▼ 3.9 ▲ 3.8
    Course difficulty (SoC avg lvl 3000 ~3.8) 4.5 == (fail to to bring this down :O) 4.5 ▲ 4.4 ▲ 4.0
    Prof Halim's teaching (SoC avg lvl 3000 ~4.2) 4.4 (PB) ▲ (finally > 4.2) 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.

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

    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)
    3. @kurumi, Tan Wei Seng (has done CS3230 TA before)
    4. @sevant, Stanve Avrilium Widjaja (new TA, but IMO G 2020)
    5. @bryanckh1, Bryan Chan Kah Hoe (new 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)

    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)
    6. @naman8667, Agrawal Naman (has done many other courses TA before)

  3. Consultation Hours:
    We employ Divide and Conquer (D&C) strategy in managing this large class.
    During these time slots, you can find staff to answer CS3230-related questions.

    1. Steven HALIM (dcssh@nus.edu.sg)
      Consultation hour: Monday (12:00-13:00) @ COM2-03-37 (just appear, open door policy)
      (except on Week 04, 05, 06, and 09; overseas for various programming competitions)
    2. CHANG Yi-Jun (cyijun@nus.edu.sg)
      Consultation hour: Thursday (11:00-12:00) @ COM3-02-24 (just appear, open door policy)
    3. Friday nights (9-11pm) recurring Zoom link
    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
      • Sorting in Linear-Time
      • 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. All class activities are onsite. We only have one lecture group, L1: each Tuesday, 10am-12nn, at LT11 (big enough for 450 pax). 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)
    4. NP-complete compendium: Computers and Intractability by Garey and Johnson (1979)
    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

Week Lecture
Tue 10am-12nn
Venue: LT11 (≤450 pax)		 Tutorial
Wed, Thu, or Fri (1 hr/wk)
Venue: COM1-0209 (SR9); one group at SR10		 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 		01a. Course Admin (S1 AY24/25 edition)
01b. Asymptotic Analysis (analysis)
Introduction
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 (will be appendix of future lec01b)
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, Substitution Method, Recursion Tree,
and Master Theorem case 1|2|3
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
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 		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)
Solve this (optional) task about D&C: guess (interactive Binary Search)
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
Solve these (optional) tasks: 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 		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)
 		Written Assignment 1
due Fri, 06 Sep, 23:59

Programming Assignment 1
(06-20 Sep)
Master Theorem,
D&C-related task

Not using nus.kattis
Only the reflection component is graded
05,
09-13 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

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,
16-20 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.

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.pdf
Randomized Algorithms
Freivald's algorithm revisited
Randomised communication protocol
Random cut of a graph
 		Programming Assignment 1
due Fri, 20 Sep, 23:59

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

Not using nus.kattis
Only the reflection component is graded
Recess Week, 21-29 Sep 2024
You can take a break this week :)
07,
30 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

References:
CLRS 4th ed Chapter 15
KT Chapter 4
CP4 Book 1 Chapter 3.4
Midterm Test (20%)
Venue: MPSH 1A & 1B
Date and Time: Sat, 05 Oct 2024, 14:00-15:40
Hall entry and exit time: 13:30 and 15:50
Mode of assessment: Hardcopy (Pen and Paper)
A few special needs students do the test at COM1-0210 (SR10)
O(1) SEATING PLAN: sorted names -> [1..435]

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), S2-N/A (not ours).
 		tut06.pdf
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 'resize-able array doubling' operation at array visualization
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
 		Programming Assignment 2
due Fri, 11 Oct, 23:59

Written Assignment 2
(11-25 Oct)
Greedy Algorithm,
Amortized Analysis
09,
14-18 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

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,
21-25 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

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.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, 25 Oct, 23:59

Written Assignment 3
(25 Oct-08 Nov)
NP-complete proof,
One (almost chosen as) final question
11,
28 Oct-01 Nov 		11. 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 six 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 week are cancelled
Enjoy our short break here
 		Written Assignment 3
Continued
12,
04-08 Nov 		12. 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
Try breaking the lower bound by solving this task: magicsequence

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)
 		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
due Fri, 08 Nov, 23:59
(Optional if your CA ≥ 40/40)
13,
11-15 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
 		tut11.pdf
Finale
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)
1 Amortized question from past paper (Week 08 review)
 		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 (ours), S2-N/A (not 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: MPSH5 (myself, Yi-Jun, 5 TAs) + UTown SR7+SR9 (special needs)
Open book
20x2 = 40% MCQs (extremely tricky again; each lecture 01-13 has at least 1 MCQ)
(the MCQs are there to speed up grading as Prof Halim has two other final assessments
on 13 Nov (33 pax) and 27 Nov (161 pax))
There will be 4 graders, thus 4 essays (approx 15% each)
Covering mostly the second half of CS3230 (NP-c; greedy; amortized; linear-time stuffs)
but without neglecting the first half of CS3230 (asymptotics; recurrences; proof of correctness; DnC; randomised; DP)