This course is an introduction to the design and analysis of computer 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. A particular emphasis will be given to principles of mathematical induction and their use in designing algorithms.

• 7/2: grade report available
• 6/4: slides for NP-Completeness available; Note on Chapter 11 of [Manber] available
• 6/4: slides for Dynamic Programming available
• 5/17: Suggested Solutions to Midterm Problems available
• 5/7: Homework Assignment #6 due on May 27 (Wednesday)
• 5/7: Homework Assignment #5 (Programming Exercise #2) due on June 4
• 5/7: slides for Graph Algorithms available
• 4/24: Homework Assignment #4 due on May 7
• 4/24: Homework Assignment #3 (Programming Exercise #1) due on May 14
• 4/14: partial solutions to HW#1 and HW#2 available
• 4/9: slides for Data Structures and for Sorting, Searching, and String Processing available
• 3/12: Homework Assignment #2 due on April 1; slides for Design by Induction available
• 3/9: slides for Analysis of Algorithms available; Note on Chapter 3 of [Manber] available
• 2/26: Homework Assignment #1 due on March 5; Note on Chapter 2 of [Manber] available
• 2/23: slides for Introduction and Mathematical Induction available

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

Thursday 2:20~5:20PM, Room 201, Management II.

Wednesday 1:30~2:30PM or by appointment, Room 1108, Management II.

Introduction to Algorithms - A Creative Approach, U. Manber, Addison-Wesley, 1989.
Introduction to Algorithms, Second Edition, T.H. Cormen, C.E. Leiserson, and R.L. Rivest, MIT Press, 2001.

The course will cover most of Manber's book plus supplementary mate- rial, including a few chapters of the book by Cormen et al.:

• Introduction - Chapter 1 (.5 week: 2/19a) [slides]
• Mathematical Induction - Chapter 2 (1.5 weeks: 2/19b, 2/26) [slides;note]
• Analysis of Algorithms - Chapter 3 (1 week: 3/5) [slides;note]
• Design by Induction - Chapter 5 (2 weeks: 3/12, 3/19) [slides]
• Data Structures: A Supplement - Sections 4.3.2,4.3.4,4.4,4.5 (1 week: 3/26) [slides]
• Sorting, Searching, and String Processing - Chapter 6 (2 weeks: 4/9, 4/23) [slides]
• Graph Algorithms - Chapter 7 (2 weeks: 4/30, 5/7) [slides]
• Selected Topics: Dynamic Programming, Mergeable Heaps, and Linear Programming - Chapters 15, 19, 20, and 29 of Cormen et al. (2 weeks: 5/14, 5/21) [Dynamic Programming]
• NP-Completeness - Chapter 11 (2 weeks: 6/4, 6/11) [slides;note]

Homework 20%, Participation 10%, Midterm (4/16) 35%, Final (6/18) 35%.

Yi-Wen Chang (常怡文), 3366-1205, Xr97725004@ntu.edu.twX (between the enclosing pair of X's);
Chih-Pin Tai (戴智斌), 3366-1205, Xsteve750312@gmail.comX (between the enclosing pair of X's).
TA sessions will be scheduled prior to some of the class meetings (tentatively on 3/19, 4/9, 5/14, and 6/4), between 1:20 and 2:10PM.