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 NPcompleteness. 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 pruneandsearch, dynamic programming, branchandbound, graph traversal, and randomised approaches), amortized analysis, NPcompleteness, 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.
This is the first time Steven (co)teaches CS3230 with Dr Diptarka Chakraborty in S2 AY 2022/23 (JanApr 2023).
As of Sun, 29 Jan 2023, the class size is 409.
Important information:
Rating (out of 5.0) 
JanApr 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) 
Time  (ID) Mon TA (size/capacity)  (ID) Tue TA (size/capacity) 

0910  (01) @the lecturer (22/23)  (10) @myangat (23/23) 
1011  (02) @zwliew (22/23)  (11) @cheeheng (21/23) 
1112  (03) @athin (21/23)  (12) @YaleChen (24/23) 
1213  (04) @athin (23/23)  (13) @Berted (22/23) 
1314  (05) @AudreyFA (21/23)  (14) @Homura (23/23) 
1415  (06) @AudreyFA (24/23)  (15) @Rezwan (24/23) 
1516  (07) @shacha (23/23)  (16) @cai (23/23) 
1617  (08) @Arpan (23/23)  (17) @kurumi (24/23) 
1718  (09) @Arpan (22/23)  (18) @T1duS (24/23) 
List of TAs:
Day  Time 1 (PIC) 
Time 2 (PIC) 
Time 3 (PIC) 
Time 4 (PIC) 

Mon  2021 @myangat 
2123 @Arpan 

Tue  1920 @Berted 
2021 @T1duS 
2122 @Homura 

Wed  1213 @the lecturer (COM20337) 
1617 @YaleChen 
2021 @zwliew 
2122 @kurumi 
Thu  2021 @shacha 
2122 @cheeheng 
2223 @Rezwan 

Fri  1213 @diptarka (COM30255) 
1517 @athin (AS604a401F/a421F) 
1718 @cai 
22midnight @AudreyFA 
This is what you will learn if you take CS3230 taught by Diptarka+Steven (TBC):
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.
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.
Date  News 

Week  Tutorial Mon or Tue 
Lecture Thu 24pm, iCube Auditorium+ELearn 
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, 0913 Jan 
Not Started 
01. Course Admins Asymptotic Analysis (analysis) Model of Computation (WordRAM) Experiment with the Fibonacci cpppyjava code and its recursion tree Experiment with the Prime Test cpppyjava Formal definitions of BigO, Ω, Θ o, ω Plus a helper xlsx file to draw the charts References: CLRS 4th ed Chapter 123 KT Chapter 2 CP4 Book 2 Chapter 5 (Fibonacci, Prime Test) 
Not Started 
02, 1620 Jan 
Tut01  Asymptotic Analysis started early (confirmed) onsite at COM3B110 (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.34.6 KT Chapter 5.15.2 Recurrence analysis is 'assumed' in CP4 
Written Assignment 1 (20 Jan03 Feb) (Recurrences, Master Theorem, Proof of Correctness) 
03, 2327 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 Jan03 Feb 
Tut02  Recurrences, D&C Proof of Correctness Note: T11+T12 now at COM12SR9 
04. D&C  continued (design) Lower bound of comparisonbased sorting (analysis) Sorting in Linear Time 1 (design) Read sorting eLecture slides (Slide 14 to 162) (just use it as it is; Counting/Radix sort eLecture slides are edited a bit to match CS3230 presentation) References: CLRS 4th ed Chapter 4.14.2 and Chapter 8.18.2 KT doesn't have a chapter on lineartime sort CP4 Book 1 Chapter 2.2.2 (CS) 
Written Assignment 1 due (03 Feb, 23:59) Programming Assignment 1 (0317 Feb) D&C and Linear Sorting 
05, 0610 Feb 
Tut03  D&C and Sorting Decision Trees 
05. Sorting in Linear Time 2 (design) (Deterministic) Quicksort (analysis) Read sorting eLecture slides (Slide 12 to 132) 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, 1317 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 Feb03 Mar) Randomized Algorithm and Order Statistics 
Recess Week, 1826 Feb 2023 We can take a break this week :) (or do Programming Assignment 2/prepare for Midterm Test) 

07, 27 Feb03 Mar Plus 04 Mar 
Tut05  Randomized Algorithms Order Statistics Worstcase select (group of 3 analysis) Expected lineartime 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 (0317 Mar) Randomization Amortized Analysis 
08, 0610 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.305 PM Midterm Test Past Paper: AY 2022/23: S1N/A (not ours), S2midterm.pdf (our paper). 
Written Assignment 2 continued 
09, 1317 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 (1731 Mar) DP and Greedy 
10, 2024 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, 2731 Mar 
Tut09  
11. Introduction to NPcompleteness (analysis) References: CLRS 4th ed Chapter 34.334.5 
Programming Assignment 3 due (31 Mar, 23:59) Written Assignment 3 (31 Mar14 Apr) Problem reduction and NPcompleteness 
12, 0307 Apr 
Tut10  NPC 
Thu, 06 Apr 2023 is chosen as NUS wellbeing 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, 1014 Apr 
Tut11  Wrap Up 1 DP, 1 Greedy, 1 NPcomplete questions 
12. Summary and Revision (through the lens of Graph Algorithms) Mostly 2nd half stuffs: Use VisuAlgo mvc page for Independent Setrelated randomized algorithm review Amortized Analysis review [no VisuAlgo page yet] Use VisuAlgo sssp page for BellmanFord (DP) review Use VisuAlgo mst page for Prim's (Greedy) review Reduction and NPcompleteness review 
Written Assignment 3 due (14 Apr, 23:59) 
Study Week, 1521 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, 13pm Venue: MPSH5 Final Test Past Paper: AY 2022/23: S1N/A (not ours), S2final.pdf (our paper). 