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 second time Prof Steven Halim (co-)teaches CS3230 with Prof Diptarka Chakraborty. This time, we are joined by Prof Sanjay Jain. For S2 AY23/24, we are expecting another 400 over CS3230 students too (it was 405 pax in S2 AY22/23).

As of Tue, 05 Mar 2024, the class size is 362 (should not change anymore).

Important information:

  1. Lecturers:
    Diptarka CHAKRABORTY,
    Steven HALIM,
    Sanjay JAIN.

    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;
    so some small apparently wide variations of the same syllabus (between S1 vs S2 versions) is expected...
    CS3230 S2 AY23/24 will be closer to CS3230 S2 AY22/23 version.

  2. Teaching Assistants:
    There are 18 tutorial groups, all are 1-hour block (effective 45m), all are at COM4-SR33.
    9 sessions are on Mondays (9am until 6pm) and the other 9 sessions are on Tuesdays.
    Here are the session to TA mapping information so far.
    As of Thu, 25 Jan 2024, everyone has a tutorial group.
    We are good to go for tutorials on Wk3 onwards.

    Time (ID) Mon TA (size/capacity) (ID) Tue TA (size/capacity)
    09-10 (01) @asleep (20/21) (10) @devansh3788 (22/21)
    10-11 (02) @PeppaPig (21/21) (11) @yalechen (22/21)
    11-12 (03) @prof_halim (22/21) (12) @dblackhat (21/2)
    12-13 (04) @benson (19/21) (13) @huajun (22/21)
    13-14 (05) @hungkhoaitay (21/21) (14) @yalechen (21/21)
    14-15 (06) @aussinami (19/21) (15) @hightower2 (22/21)
    15-16 (07) @berted (22/21) (16) @9V1BD (21/21)
    16-17 (08) @lovemathboy (21/21) (17) @myangat (16/21)
    17-18 (09) @shacha (18/21) (18) @rama_pang (12/21)

    List of TAs:

    1. @prof_halim, A/P Steven Halim (taking 1 tutorial group)
    2. @asleep, Ling Yan Hao (GT)
    3. @aussinami, Alvin Yan Hong Yao (GT)
    4. @yalechen, Chen Yanyu (taking 2 tutorial groups)
    5. @shacha, Shashwat Chandra
    6. @berted, Edbert Geraldy Cangdinata
    7. @rama_pang, Rama Aryasuta Pangestu
    8. @lovemathboy, Huang Xing Chen
    9. @hightower2, Ryan Ong Zheng Xun
    10. @myangat, Yang Mingyang
    11. @benson, Yeung Man Tsung
    12. @hungkhoaitay, Nguyen Thuan Hung
    13. @dblackhat, Pratham Jain
    14. @huajun, Teow Hua Jun
    15. @devansh3788, Shah Devansh Apoorva
    16. @9V1BD, Ho Jie Feng
    17. @PeppaPig, Pontakorn Prasertsuk

  3. Consultation Hours:
    We employ Divide and Conquer (D&C) strategy in managing this large class.
    During these time slots (Thu/Fri nights, 9-11pm), there will be at least one TA who will man the Zoom session to answer CS3230-related questions.

    Thursday nights (9-11pm) recurring Zoom link
    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)
    • Order Statistics
    • Dynamic Programming (DP)
    • Greedy Algorithms
  • Analysis:
    • Asymptotic Analysis
    • Recurrences and Master Theorem
    • Proof of Correctness
    • 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), diptarka at comp, or sanjay at comp. Relevant answers will be posted here to reach wider audiences.

Q: Will CS3230 S2 AY 2023/24 has onsite components?
A: Yes. Almost all class activities are onsite. We will have two lecture groups each Thursday, 2-4pm (L1 at COM1-02-SR1, for up to 200 pax onsite and L2-hybrid online class). However, from last year's experience, anyone who prefers to study live (especially from the L2 group) shall just appear onsite at SR1. Lectures at SR1 will be recorded centrally by NUS CIT.
Q: I will be taking ATAP too, can you approve me taking CS3230 alongside doing ATAP?
A: Auto reply: Contact UG office, we will decline giving yes/no answer.
Q: I want to take CS3230 and another course that has (lecture) timetable clash with CS3230, i.e., overlap with Thu 2-4pm time window. Can you give me a timetable clash waiver?
A: Auto reply: 99% no. Contact UG office if you are sure your case is very 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); PS: the e-book version is sold with 25% discount under this agreeement
  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 Diptarka+Steven+Sanjay 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 the class.

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

News

Date News

Lesson Plan

The S2 AY 2023/24 timetable below is still tentative, especially those that are highlighted with pink color.

Week Tutorial
Mon or Tue
Lecture
Thu 2-4pm,
COM1-02-SR1+E-Learn
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,
15-19 Jan
Not Started 01. Course Admins
Asymptotic Analysis (analysis)
Model of Computation (Word-RAM)
Experiment with Fibonacci cpp|py|java code and its recursion tree vs DAG
Experiment to solve this (optional) simple Fibonacci task: rijeci
Formal definitions of Big-O, Ω, Θ o, ω
Plus a 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)
Optional Early CS3230 Topics
(11 Jan-08 Feb)
02,
22-26 Jan
Tut01 - Introduction + Asymptotic Analysis
started early
onsite at COM4-SR33 (our tutorial venue)
(already booked one week in advance)
02. Recurrences and Master Theorem (analysis)
Quick review of Merge Sort especially its analysis
Review Merge Sort implementation at SortingDemo.cpp | py | java
Experiment to solve this (optional) task that forces you to use Merge Sort: ultraquicksort
Use VisuAlgo recursion page to analyse some recursion trees
Telescoping, Recursion Tree, Master Theorem case 1|2|3, and Substitution Method
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
Optional Early CS3230 Topics
continued

Written Assignment 1
(26 Jan-09 Feb)
Asymptotic Analysis,
Recurrences/Master Theorem
03,
29 Jan-02 Feb
Tut02 - Recurrences
Telescoping
Recursion Tree
Master Theorem
Substitution Method
03. Proof of Correctness (analysis)
Use VisuAlgo sorting page to review insertion/selection sort
Experiment to solve this (optional) task: height (basic Insertion Sort)

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
Experiment to 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)
Optional Early CS3230 Topics
continued

Written Assignment 1
continued
04,
05-09 Feb
Tut03 - Correctness + D&C
Proof of Correctness (Dijkstra's)
Review weighted SSSP
D&C: Finding any peak (2D)
03. D&C Algorithm (design) part 2
Complete the leftovers from Week 03
From Matrix Multiplication (Strassen's) - 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)

04c. Linear-Time Sorting [not examinable]
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)
Optional Early CS3230 Topics
closed 08 Feb, 23:59

Written Assignment 1
due 09 Feb, 23:59
Submit early if you
celebrate CNY reunion dinner

Hint for solving recurrences or
drawing recursion trees:
use VisuAlgo, esp for GCD algorithm

Programming Assignment 1
(09-23 Feb)
(D&C tasks)
05,
12-16 Feb
CNY Reunion Dinner on Fri, 09 Feb
CNY Day 1 on Sat, 10 Feb
CNY Day 2 on Sun, 11 Feb
Mon, 12 Feb is also a PH
Monday+Tuesday tutorial classes are cancelled
(we have started earlier from Week 02)
(we will spread the contents to Tut04-11)
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
Programming Assignment 1
continued

Hint for PA1-A
Review Master Thorem
Use this tool from Baylor University

Hint for PA1-B
Try Subtask 1 first
(the Great Seedling does not move)
assert(log2(10**9) <= 32) is true
06,
19-23 Feb
Tut04 - D&C:
Polynomial Mult
Decision Trees
Math: Probabilistic Analysis
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
Hint for PA1-B (the 16 steps)
Divide by 2 or 3 both not enough
Try dividing by 4
PS: where can the seedling be if it moves?

Programming Assignment 1
due 23 Feb, 23:59

Programming Assignment 2
(23 Feb-0810 Mar)
Randomized Algorithm,
(Simpler) DP
Recess Week, 24 Feb-03 Mar 2024
07,
04-08 Mar
Tut05 - Dynamic Programming
Convex Polygon Triangulation
FAQ: Included in Midterm
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: MPSH1A
Sat, 09 Mar 2024, 3.30-5.00pm
O(1) SEATING PLAN: sorted names -> [0..365]

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 (ours).
Programming Assignment 2
due 0810 Mar, 23:59
(after midterm; but remember that
DP question appears in midterm)

Written Assignment 2
(08-22 Mar)
DP
Randomized Algorithm
08,
11-15 Mar
Tut06 - Greedy Algorithms
Burning CDs
Activity selection problem
FAQ: Confirm included in Final
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
Written Assignment 2
continued
09,
18-22 Mar
Tut07 - Amortized Analysis
Aggregate method
Accounting method
Potential method
FAQ: Also confirm included in Final
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)

Makeup Midterm Test
(venue booking in progress)
Venue: SR@LT19 (to be booked)
Sat, 23 Mar 2024, 3.30-5.00pm
Written Assignment 2
due 22 Mar, 23:59

Programming Assignment 3
(22 Mar-05 Apr)
Greedy
DP (with pseudo-polynomial constraint)
10,
25-29 Mar
Tut08 - Reduction
Use VisuAlgo new reductions page
for 2 out of 4 questions
FAQ: Could be the hardest Q in the Final
Makeup Midterm Test
Only for 2 out of 362 pax at a special venue this week

Thu, 28 Mar 2024 is chosen as
NUS well-being day S2 AY 2023/24
This is just before Fri, 29 Mar 2024 Good Friday PH
Thus, there is no lecture this week

NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until you reading week
Programming Assignment 3
continued
11,
01-05 Apr
Tut09 - Review of topics so far
1 DP, 1 Greedy, 1 Amortized
10. Introduction to NP-completeness (analysis)
References: CLRS 4th ed Chapter 34.3-34.5
Programming Assignment 3
due 05 Apr, 23:59

Written Assignment 3
(05-19 Apr)
Amortized Analysis
Problem reduction
and NP-completeness
12,
08-12 Apr
Tut10 - NPC Wed, 10 Apr 2024 is Hari Raya Puasa PH
CS3230 is not affected

11. Order Statistics (design and analysis)
See RandQSort recursion tree (refresh a few times, it is random)
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
Written Assignment 3
continued
13,
15-19 Apr
Tut11 - Wrap Up
Order Statistics (TBC)
NP-complete question
12. Summary and Revision
(through the lens of Graph Algorithms)
Mostly 2nd half stuffs:
Use VisuAlgo mvc page for Independent Set-related randomized algorithm review
Amortized Analysis review [no VisuAlgo page yet]
Use VisuAlgo sssp page for Bellman-Ford (DP) review
Use VisuAlgo mst page for Prim's (Greedy) review
Reduction and NP-completeness review
Written Assignment 3
due 19 Apr, 23:59
Study Week, 20-26 Apr 2024
NUS Online Teaching Feedback closes on Friday of Study Week
Final Assessment (40%)
Date and Time: Tue, 30 Apr 2024, 1-3pm
Venue: TBA

Final Test Past Paper:
AY 2022/23: S1-N/A (not ours), S2-final.pdf,
AY 2023/24: S1-N/A (not ours), S2-final.pdf (will be ours).