This course provides an introduction to the design and analysis of computer algorithms, with a particular emphasis on the use of principles of mathematical induction in designing algorithms. Its goal is to acquaint the students with basic computer algorithms and their design principles and to cultivate the students' ability in designing and analyzing algorithms independently.

• 2025/01/06: grade report revised.
• 12/29: grade report available; please send inquiries/requests, if any, to the instructor by 5PM 12/31 (Tue.).
• 12/10: slides from TA sessions: HW#8, HW#9 (revised 12/15).
• 12/03: notes/slides for NP-Completeness available.
• 12/03: notes/slides for Reduction available.
• 12/02: HW#10 due on 12/10 by 1:20PM (because of the TA session).
• 11/26: slides from TA sessions: HW#7.
• 11/26: HW#9 due on 12/03.
• 11/26: notes/slides for Dynamic Programming available.
• 11/18: HW#8 due on 11/26 by 1:20PM (because of the TA session).
• 11/12: slides from TA sessions: HW#6 (revised 11/20).
• 11/11: notes/slides for Advanced Graph Algorithms available.
• 11/05: HW#7 due on 11/19.
• 11/04: notes/slides for Basic Graph Algorithms available (revised 12/12).
• 11/04: Suggested Solutions to Midterm Problems available (revised 11/11).
• 10/22: slides from TA sessions: HW#3 (revised), HW#4.
• 10/15: HW#6 due on 11/05.
• 10/13: notes/slides for String Processing available.
• 10/08: slides from TA sessions: HW#2, HW#3 (removed).
• 10/06: HW#5 due on 10/15.
• 10/03: notes/slides for Searching and Sorting available (revised 10/25).
• 10/03: notes/slides for A Supplement to Data Structures available (revised 10/15).
• 10/01: HW#4 due on 10/08 by 1:20PM (because of the TA session).
• 09/30: notes/slides for Design by Induction available (revised 10/02).
• 09/24: slides from TA sessions: HW#1.
• 09/24: HW#3 due on 10/01.
• 09/22: old exams.
• 09/22: notes/slides for Analysis of Algorithms available (revised 10/15).
• 09/10: HW#2 due on 09/24 by 1:20PM (because of the TA session).
• 09/09: classroom changed to Room 305, Management Building 2 for the entire semester.
• 09/02: HW#1 due on 09/10.
• 09/02: notes/slides for Introduction and for Mathematical Induction available (revised 09/24).
• 08/26: this wiki site created to complement the NTU COOL site for this course.

Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@ntu.edu.twX (between the enclosing pair of X's).

Tuesday 2:20~5:20PM, Room 305, Management Building 2.
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM; see the course schedule below.

Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108, Management Building 2.

Yu Hsiao (蕭瑀), Xb08705059@ntu.edu.twX (between the enclosing pair of X's).
Yu-Hsuan Wu (吳宇璇), Xb09705045@ntu.edu.twX (between the enclosing pair of X's)

• [M] Introduction to Algorithms - A Creative Approach, U. Manber, Addison-Wesley, 1989. (Four copies of this book have been put on reserve at NTU Library in the 3F-Course Reserves area 教師指定參考書區 under 演算法(BM-4). Additionally, ten copies are available for loan; please contact one of the TAs.)
• [C] Introduction to Algorithms, Fourth Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2022. (開發圖書代理; one copy of this book has been put on reserve at NTU Library in the 3F-Course Reserves area 教師指定參考書區 under (FF-9).)

We will try to cover most of Manber's book plus supplementary material, including a few chapters of the book by Cormen et al. (Note: a TA session will precede a class meeting whose date is marked with an *. There are six TA sessions on 09/24, 10/08, 10/22, 11/12, 11/26, and 12/10.)

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 09/03a) [notes, slides]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 09/03b, 09/10) [notes, slides]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 09/24*) [notes, slides]
• Design by Induction [M: Ch. 5] (1 week: 10/01) [notes, slides]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,19] (.5 week: 10/08a*) [notes, slides, Building an AVL Tree (Illustration)]
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (1.5 weeks: 10/08b, 10/15) [notes, slides, Heapsort (Illustration), Bottom-Up Heap Building (Illustration)]
• String Processing [M: Ch. 6; C: Ch. 32] (1 week: 10/22*) [notes, slides, Construction of a Huffman Tree (Illustration)]
• Midterm (2024/10/29)
• Graph Algorithms: Basic [M: Ch. 7; C: Ch. 20,21,22,23] (1.5 weeks: 11/05, 11/12a*) [notes, slides, Dijkstra's Algorithm (Illustration), Prim's Algorithm (Illustration)]
• Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 20,24,25] (1.5 weeks: 11/12b, 11/19) [notes, slides, Computing SCCs (Illustration)]
• Dynamic Programming [C: Ch.14] (1 week: 11/26*) [notes, slides]
• Reduction [M: Ch. 10; C: Ch. 29] (.5 week: 12/03a) [notes, slides]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (1.5 weeks: 12/03b, 12/10*) [notes, slides]
• Final (2024/12/17)

Homework/Quizzes 20%, Participation 10%, Midterm 35%, Final 35%.

• Mathematical Induction (a Wikipedia page)
• Structural Induction (a Wikipedia page)
• MIT OpenCourseWare: Introduction to Algorithms
• Stanford Coursera: Algorithms
• What is an Algorithm? (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
• Sorting Algorithms Animations
• Graph Animations with Combinatorica
• The P versus NP Problem (Stephen Cook)
• The website of ICPC (International Collegiate Programming Contest)