CS3230 - Design and Analysis of Algorithms

Introduction

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.

Course Registration

This is the fourth time Prof Steven Halim (co-)teaches CS3230. This time, he is with Prof Chang Yi-Jun.

As of Mon, 30 Sep 2024 (from now on, dropping this class is an automatic 'F' grade), the class size is 435.

Important information:

1. Lecturers:
   CHANG Yi-Jun,
   Steven HALIM.
   
   CS3230 have been changing hands so frequently in recent AYs and the experience varies:
   S1 AY22/23: Arnab Bhattacharyya+Prashant Nalini Vasudevan → S2 AY22/23: Diptarka Chakraborty+Steven Halim →
   S1 AY23/24: Arnab Bhattacharyya+Rahul Jain → S2 AY23/24: Diptarka Charkraborty+Steven Halim+Sanjay Jain;
   S1 AY24/25: Chang Yi-Jun+Steven Halim; S2 AY24/25: Sanjay Jain+Warut Suksompong+Eric Han Liang Wee;
   CS3230 in both S1+S2 of AY 24/25 should now be more similar than before as I (Prof Halim) transfer S2 AY 23/24 knowledge to S1 AY 24/25 version, and later to S2 AY2 24/25 colleagues.
   
   

   Rating (out of 5.0)	Aug-Nov 24 (n≥140/435) ≥32%	Jan-Apr 24 (n=222/362) 61% ▼	Jan-Apr 23 (n=280/405) 69% ▲	Jan-Apr 14 (n=46/87) 53%
   Course feedback (SoC avg lvl 3000 ~3.9)	≥ 3.9 (target)	3.8 ▼	3.9 ▲	3.8
   Course difficulty (SoC avg lvl 3000 ~3.8)	≤ [4.2..4.3] (let's reduce...)	4.5 ▲, too hard :(...	4.4 ▲	4.0
   Prof Halim's teaching (SoC avg lvl 3000 ~4.2)	≥ 4.3 (target)	4.2 ==	4.2 ▲	4.0

2. Teaching Assistants:
   
There are 17 tutorial groups, all are 1-hour block (effective 45m), all are at COM1-0209 (SR9) — except TG04 venue is at COM1-0210 (SR10).
7 sessions are on Wednesdays, 4 are on Thursdays, and the other 6 on Fridays.
PS: TG08-TG10 are removed because Wed 3-6pm are blocked for NUSOne project.



Time	(ID) Wed (size/cap)	(ID) Thu (size/cap)	(ID) Fri (size/cap)
08-09	(01) @dominic (17/27)
09-10	(02) @aprup (27/27)
10-11	(03) @kurumi (25/27)		(15) @sleeping (25/27)
11-12	(04) @sevant (27/27)		(16) @wongkj (26/27)
12-13	(05) @bryanckh1 (19/27)	(11) @huajun (28/28)
13-14	(06) @x1213 (27/27)	(12) @asleep (28/28)
14-15	(07) @yalechen (27/27)		(17) @flicker_v (26/27)
15-16	NUSOne		(18) @aussiroth (28/28)
16-17	NUSOne	(13) @lovemathb (26/27)	(19) @hithisisjj (27/27)
17-18	NUSOne	(14) @chocolate (28/28)	(20) @naman8667 (24/27)

List of Wednesday TAs (ordered using Lab Group Number):

1. @dominic, Dominic Berzin Chua Way Gin(has done IT5003 TA before)
2. @aprup(.kale), Kale Aprup Vinay (has done CS2040S/CS2030S/CS1101S TA before)
3. @kurumi, Tan Wei Seng (has done CS3230 TA before)
4. @sevant, Stanve Avrilium Widjaja (new TA, but IMO G 2020)
5. @bryanckh1, Bryan Chan Kah Hoe (new TA)
6. @x1213, Prof Chang Yi-Jun (taking 1 tutorial group)
7. @yalechen, Chen Yanyu (has done CS3230 TA before)



List of Thursday TAs (ordered using Lab Group Number):

11. @huajun, Teow Hua Jun (has done CS3230 TA before)
12. @asleep, Ling Yan Hao (GT, has done CS3230 TA before)
13. @lovemathb(oy), Huang Xing Chen (has done CS3230 TA before)
14. @chocolate, Nguyen Doan Phuong Anh (has done CS3230/CS1231S/CS2040S TA before)



List of Friday TAs (ordered using Lab Group Number):

15. @sleeping(pants), Ramanathan Kumarappan (has done CS2109S TA before)
16. @wongkj, Wong Kai Jie (has done CS1231S TA before)
17. @flicker_v(ieri), Juan Carlo Vieri (new TA)
18. @aussiroth, Alvin Yan Hong Yao (GT, has done CS3230 TA before)
19. @hithisisjj, Teoh Jun Jie (has done CS4234 TA before)
20. @naman8667, Agrawal Naman (has done many other courses TA before)


3. Consultation Hours:
   We employ Divide and Conquer (D&C) strategy in managing this large class.
   During these time slots, you can find staff to answer CS3230-related questions.
   
   
   1. Steven HALIM (dcssh@nus.edu.sg)
      Consultation hour: Monday (12:00-13:00) @ COM2-03-37 (just appear, open door policy)
      (except on Week 04, 05, 06, and 09; overseas for various programming competitions)
   2. CHANG Yi-Jun (cyijun@nus.edu.sg)
      Consultation hour: Thursday (11:00-12:00) @ COM3-02-24 (just appear, open door policy)
   3. Friday nights (9-11pm) recurring Zoom link
      
   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 this semester:
   

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

   Course Registration Additional FAQ

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

   Q: Will CS3230 S1 AY 2024/25 has onsite components?

   A: Yes. All class activities are onsite. We only have one lecture group, L1: each Tuesday, 10am-12nn, at LT11 (big enough for 450 pax). Lectures will be recorded centrally by NUS CIT.

   Q: I will be taking ATAP too, can you approve me taking CS3230 alongside doing ATAP?

   A: Latest official reply (23 July 2024): The default answer from Prof Halim and from UG/IR office is a "NO, Take CS3230 in S2 AY24/25 or latter semester instead". However, do appeal to Prof Halim if your case is very special, e.g., if this is your last available semester to take CS3230 (e.g., going for exchange next semester and wanting to take S1 advanced algorithm courses in S1 of your final year, e.g., my previous other CS4234 course).

   Q: I want to take CS3230 and another course that has (lecture) timetable clash with CS3230, i.e., overlap with Tue 10am-12nn time window. Can you give me a timetable clash waiver?

   A: Auto reply: 99% no. Contact UG office for appeal. Only contact Prof Halim if you are sure your case is special.

   Q: Can I audit CS3230?

   A: CS3230 is a core course and we generally do not accept students auditing CS3230. Email Prof Halim (dcssh) directly for case-by-case appeal. Students who are outbidded this semester 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, we do not requite students to buy any textbook. 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 are encouraged to get a (legal) copy of some (or all) of these:

   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)
   4. NP-complete compendium: Computers and Intractability by Garey and Johnson (1979)

   Q: Can I S/U this course?

   A: No.

   Q: Is CS3230 under Yi-Jun+Steven a flipped classroom course?

   A: Not yet, Prof Halim still need to go through a few more iterations to improve the material before we can be confident enough to flip (some lectures of) the class.

   Note: This course registration section will not be prominent from Week 1 of S1 AY 2024/25 onwards. This behavior is normal. You can view it again by scrolling to the top of this page.
   

News Show All

Lesson Plan Hide Past Show Past Hide Details Show Details