CS3230 - Design and Analysis of Algorithms

Introduction

First, let's abbreviate "Design and Analysis of Algorithms" as DAA to differentiate it with Steven'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 first time Steven (co-)teaches CS3230 with Dr Diptarka Chakraborty in S2 AY 2022/23 (Jan-Apr 2023).

As of Sun, 29 Jan 2023, the class size is 409.

Important information:

  1. Lecturers:
    Main Lecturer (except for the first lecture): Assistant Professor Diptarka Chakraborty,
    Co-Lecturer (assisting the main lecturer in the hybrid Zoom session and managing class Discord): Dr Steven Halim.

    CS3230 have been changing hands so frequently in recent AYs and the experience varies: S2 AY20/21: Diptarka Chakraborty → S1 AY21/22: Arnab Bhattacharyya → S2 AY21/22: Warut Suksompong → Last S1 AY22/23: Arnab Bhattacharyya+Prashant Nalini Vasudevan → This S2 AY22/23: Steven Halim+Diptarka Chakraborty; so some small variations of the same syllabus is expected...

    The main target for this semester is to have a good baseline of CS3230 in our first time co-teaching together.

    Rating
    (out of 5.0)    		 Jan-Apr 23
    (n=???/409)
    ≥ 50%
    Course feedback (SoC avg ~3.9) Target 3.9 (large class, try to at least match SoC avg)
    Course difficulty (SoC avg ~3.8) Target 4.1 (likely a bit higher than SoC avg; esp Steven is a 'competitive' type and Diptarka's 2021 edition was harder than this...)
    Steven's teaching (SoC avg ~4.2) Target 4.2 (large class, try to at least match SoC avg)
  2. Teaching Assistants:
    There are 18 tutorial groups, all are 1-hour block (effective 45m), all are at COM3-B1-10 (except T11+T12 at COM1-2-SR9).
    9 sessions are on Mondays (9am until 6pm) and the other 9 sessions are on Tuesdays.
    Here are the session to TA mapping information.

    As of Fri, 27 Jan 2023, everyone has a tutorial group. We are good to go for tutorials on Wk4 onwards.

    Time (ID) Mon TA (size/capacity) (ID) Tue TA (size/capacity)
    09-10 (01) @the lecturer (22/23) (10) @myangat (23/23)
    10-11 (02) @zwliew (22/23) (11) @cheeheng (21/23)
    11-12 (03) @athin (21/23) (12) @YaleChen (24/23)
    12-13 (04) @athin (23/23) (13) @Berted (22/23)
    13-14 (05) @AudreyFA (21/23) (14) @Homura (23/23)
    14-15 (06) @AudreyFA (24/23) (15) @Rezwan (24/23)
    15-16 (07) @shacha (23/23) (16) @cai (23/23)
    16-17 (08) @Arpan (23/23) (17) @kurumi (24/23)
    17-18 (09) @Arpan (22/23) (18) @T1duS (24/23)

    List of TAs:

    1. @the lecturer, Dr Steven Halim (taking 1 tutorial group)
    2. @athin, Ammar Fathin Sabili ("full-time" TA and PhD student, 2 groups)
    3. @Arpan, Arpan Losalka (PhD student, 2 groups)
    4. @AudreyFA, Audrey Felicio Anwar, 2 groups
    5. @T1duS, Udit Sanghi
    6. @Berted, Edbert Geraldy Cangdinata
    7. @Rezwan[Arefin01], Rezwan Arefin
    8. @shacha, Shashwat Chandra
    9. @myangat, Yang Mingyang
    10. @zwliew, Liew Zhao Wei
    11. @cheeheng, Tan Chee Heng
    12. @Homura[ Akemi], Sanchez Bryce Ainsley Ang
    13. @kurumi, Tan Wei Seng
    14. @YaleChen, Chen Yanyu
    15. @cai, Cai Kai'an

  3. Consultation Hours:
    We employ Divide and Conquer (D&C) strategy in managing this large (over 400 pax) class.
    During these time slots (note mostly evening/night and Sat morning timings), the assigned PIC will open a 1h (3 are 2h) block of Zoom (3 are F2F) session for anyone to ask CS3230 related questions.
    The PIC will also use that 1h time slot to clear (or delegate) as many pending questions in class Discord and/or to throw new questions there, or to use that time to grade your WA/PA submissions.
    As you can see, CS3230-related official help is always available every day throughout the semester except on Sabbaths (Sat evening - entire Sun).

    Day Time 1
    (PIC)    		 Time 2
    (PIC)    		 Time 3
    (PIC)    		 Time 4
    (PIC)
    Mon 20-21
    @myangat    		 21-23
    @Arpan
    Tue 19-20
    @Berted    		 20-21
    @T1duS    		 21-22
    @Homura
    Wed 12-13
    @the lecturer
    (COM2-03-37)    		 16-17
    @YaleChen    		 20-21
    @zwliew    		 21-22
    @kurumi
    Thu 20-21
    @shacha    		 21-22
    @cheeheng    		 22-23
    @Rezwan
    Fri 12-13
    @diptarka
    (COM3-02-55)    		 15-17
    @athin
    (AS6-04-a401F/a421F)    		 17-18
    @cai    		 22-midnight
    @AudreyFA

  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 if you take CS3230 taught by Diptarka+Steven (TBC):

  • Design:
    1. Complete Search/prune-and-search/branch-and-bound (no specific lecture, but Complete Search algorithms appear many times in this course)
    2. Divide and Conquer (D&C)
    3. Sorting in Linear Time
    4. Order Statistics
    5. Dynamic Programming (DP)
    6. Greedy Algorithms
  • Analysis:
    1. Asymptotic Analysis
    2. Recurrences and Master Theorem
    3. Proof of Correctness
    4. Probabilistic Analysis of Randomized Algorithms
    5. Amortized Analysis
    6. NP-completeness

Course Registration Additional FAQ

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

Q: Will CS3230 S2 AY 2022/23 has onsite components?
A: Yes. Almost all class activities are onsite. We only have one online component as iCube-Auditorium has a maximum capacity of 350 pax and the official class size is 409 pax (information as of 29 Jan 2023). Therefore each Thursday lectures will be in Hybrid mode with the main lecturer (Dr Diptarka) be the main lecturer onsite (except the first lecture) and Dr Steven taking care of the online interactions during live lectures.
Q: Will this course be graded using Bell curve?
A: CS3230 is a gigantic class (as of 29 Jan 2023, we are at 409 students). Bell curve system will obviously be used.
Q: I will be taking ATAP too, can you approve me taking CS3230 alongside doing ATAP?
A: It should be fine as long as you can regularly attend lectures and tutorials (and especially midterm test and final assessment). There are class participation marks both for lectures and tutorials that you will lose if you skip most (or all) of them. Please arrange your timetable properly with your company supervisor.
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: No. Note that this is different from ATAP with coordinated timetable rearrangement+CS3230 above.
Q: CS3230 vacancy (even for the newly opened E-Learning L2-group) is now no more (for Round 2 onwards)... Can I directly appeal to you to slot me in?
A: No. We are really planning to run at most with 450 students. Please take CS3230 next semester (S1 AY23/24) or next year (S2 AY23/24) instead.
Q: Can I audit CS3230 instead?
A: CS3230 is a core course and we generally do not accept students auditing CS3230. Email Steven (dcssh) directly for case-by-case appeal. Students who are outbidded this semester (see the previous question) 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, no. 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 can refer to:
  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 Diptarka+Steven a flipped classroom course?
A: Not yet, Steven will probably go through a few 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 2022/23 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 2022/23 timetable below is still tentative, especially those that are highlighted with pink color.

Week Tutorial
Mon or Tue		 Lecture
Thu 2-4pm,
iCube Auditorium+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,
09-13 Jan 		Not Started 01. Course Admins
Asymptotic Analysis (analysis)
Model of Computation (Word-RAM)
Experiment with the Fibonacci cpp|py|java code and its recursion tree
Experiment with the Prime Test cpp|py|java
Formal definitions of Big-O, Ω, Θ o, ω
Plus a helper xlsx file to draw the charts
References: CLRS 4th ed Chapter 1-2-3
KT Chapter 2
CP4 Book 2 Chapter 5 (Fibonacci, Prime Test)
 		Not Started
02,
16-20 Jan 		Tut01 - Asymptotic Analysis
started early (confirmed)
onsite at COM3-B1-10 (our tutorial venue)
Tut01 plan in Canvas Files by Fri 13 Jan PM
 02. Recurrences and Master Theorem (analysis)
Quick revision of Merge Sort especially its analysis
Use VisuAlgo recursion page to analyse some recursion trees
References: CLRS 4th ed Chapter 2.3 and 4.3-4.6
KT Chapter 5.1-5.2
Recurrence analysis is 'assumed' in CP4
 		Written Assignment 1
(20 Jan-03 Feb)
(Recurrences, Master Theorem,
Proof of Correctness)
03,
23-27 Jan 		CNY Reunion Dinner on Sat, 21 Jan
CNY Day 1 on Sun, 22 Jan
CNY Day 2 on Mon, 23 Jan
Tue, 24 Jan is also a PH
CS3230 Tutorial classes this week
are canceled
 		03. Proof of Correctness (analysis)
Divide and Conquer (D&C) Algorithm (design)
Use VisuAlgo sorting page to review insertion/selection/merge sort
Use VisuAlgo recursion page to see binary search/modulo power
References: CLRS 4th ed Chapter 2.1 and 4
KT Chapter 5
CP4 Book 2 Chapter 3.3 (Binary Search), 5 (Matrix/Modulo Power)
 		Written Assignment 1
continued
04,
30 Jan-03 Feb 		Tut02 - Recurrences, D&C
Proof of Correctness
Note: T11+T12 now at COM1-2-SR9 		04. D&C - continued (design)
Lower bound of comparison-based sorting (analysis)
Sorting in Linear Time 1 (design)
Read sorting e-Lecture slides (Slide 14 to 16-2)
(just use it as it is;
Counting/Radix sort e-Lecture slides
are edited a bit to match CS3230 presentation)
References: CLRS 4th ed Chapter 4.1-4.2 and Chapter 8.1-8.2
KT doesn't have a chapter on linear-time sort
CP4 Book 1 Chapter 2.2.2 (CS)
 		Written Assignment 1 due
(03 Feb, 23:59)
Programming Assignment 1
(03-17 Feb)
D&C and Linear Sorting
05,
06-10 Feb 		Tut03 - D&C and Sorting
Decision Trees
 05. Sorting in Linear Time 2 (design)
(Deterministic) Quicksort (analysis)
Read sorting e-Lecture slides (Slide 12 to 13-2)
Analysis of the average case of deterministic Quicksort
References: CLRS 4th ed Chapter 8.3 (RS) + 7 (QS)
KT Chapter 13 (some examples, e.g., 13.5 (QS))
CP4 Book 1 Chapter 2.2.2 (RS)
 		Programming Assignment 1
continued
06,
13-17 Feb 		Tut04 - Sorting
Probabilistic Analysis
Randomized Algorithms
 06. Randomized Quicksort (analysis)
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
 		Programming Assignment 1 due
(17 Feb, 23:59)
Programming Assignment 2
(17 Feb-03 Mar)
Randomized Algorithm
and Order Statistics
Recess Week, 18-26 Feb 2023
We can take a break this week :)
(or do Programming Assignment 2/prepare for Midterm Test)
07,
27 Feb-03 Mar
Plus 04 Mar
 Tut05 - Randomized Algorithms
Order Statistics
Worst-case select (group of 3 analysis)
Expected linear-time select (analysis) 		07. Amortized Analysis (analysis)
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
 		Programming Assignment 2 due
(03 Mar, 23:59)
Written Assignment 2
(03-17 Mar)
Randomization
Amortized Analysis
08,
06-10 Mar 		Tut06 - Amortized Analysis 08. Dynamic Programming (design)
References: CLRS 4th ed Chapter 14
KT Chapter 6
CP4 Book 1 Chapter 3.5 + Book 2 Chapter 8.3

Midterm Test
Venue: MPSH 2A
Sat, 11 Mar 2023, 3.30-5 PM

Midterm Test Past Paper:
AY 2022/23: S1-N/A (not ours), S2-midterm.pdf (our paper),
 		Written Assignment 2
continued
09,
13-17 Mar 		Tut07 - Dynamic Programming 09. Greedy Algorithms (design)
References: CLRS 4th ed Chapter 15
KT Chapter 4
CP4 Book 1 Chapter 3.4
 		Written Assignment 2 due
(17 Mar, 23:59)
Programming Assignment 3
(17-31 Mar)
DP and Greedy
10,
20-24 Mar 		Tut08 - Greedy Algorithms 10. Complete Greedy Algorithms
Problem reductions
Complete Huffman Coding
The concept of reductions (in polynomial time)
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,
27-31 Mar 		Tut09 - NPC 1 11. Introduction to NP-completeness (analysis)
TBA
 		Programming Assignment 3 due
(31 Mar, 23:59)
Written Assignment 3
(31 Mar-14 Apr)
Problem reduction
and NP-completeness
12,
03-07 Apr 		Tut10 - NPC 2 Thu, 06 Apr 2023 is chosen as
NUS well being day S2 AY 2022/23
This is just before Fri, 07 Apr 2023 Good Friday PH
CS3230 Lecture on 'Approximation Algorithm'
is cancelled; thus interested students are encouraged
to take CS4234 (that covers this) instead
 		Written Assignment 3
continued
13,
10-14 Apr 		Tut11 - Wrap Up 12. Summary and Revision
(through the lens of Graph Algorithms)
TBA
 		Written Assignment 3 due
Study Week, 15-21 Apr 2023
NUS Online Teaching Feedback closes on Friday of Study Week
Hari Raya Puasa PH on Sat, 22 Apr 2023
CS3230 is not affected
Final Assessment (40%)
Date and Time: Thu, 27 Apr 2023, 1-3pm
Venue: TBC