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.
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:
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:
This is what you will learn this semester:
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.
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.
Date | News |
---|
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- 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 (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) (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) See VisuAlgo reductions page (the overview then 3-SAT ≤p IS) 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 - NP-complete See VisuAlgo reductions page (3-)CNF-SAT ≤p SUBSET-SUM (not ready) VC ≤p HS This question type may be the hardest Q in the Final |
Wed, 10 Apr 2024 is Hari Raya Puasa PH CS3230 is not affected 11. Order Statistics (design and analysis) Worst-case Linear Time Sort (not in VisuAlgo) See (unsorted) array page and try "Select", especially "Quickselect" 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 [optional sub lecture of cake-cutting problem] Interested students are invited to take Prof Warut Suksompong CS4261 - Algorithmic Mechanism Design] |
Written Assignment 3 continued |
13, 15-19 Apr |
Tut11 - Wrap Up Order Statistics 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: MPSH2-B 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). |