World of Seven - 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:

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=280/405) 69%
Course feedback (SoC avg ~3.8)	3.9 (slightly above SoC avg)
Course difficulty (SoC avg ~3.8)	4.4 (far harder than SoC avg)
Steven's teaching (SoC avg ~4.1)	4.2 (slightly above SoC avg)

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:

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

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

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.
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:

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)
Additional reference: Algorithm Design by Kleinberg & Tardos (2006)
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

Warning! Lesson Plan details are hidden on small viewport. Please view this page on large screen ≥ 992 pixels to avoid missing important deadlines.

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) References: CLRS 4th ed Chapter 34 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~~Reduction	11. Introduction to NP-completeness (analysis) References: CLRS 4th ed Chapter 34.3-34.5	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 1 DP, 1 Greedy, 1 NP-complete questions	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 (14 Apr, 23:59)
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: MPSH5 Final Test Past Paper: AY 2022/23: S1-N/A (not ours), S2-final.pdf (our paper).

CS3230 - Design and Analysis of Algorithms