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