The goal of this course 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.

• 07/10: grade report available; please send inquiries, if any, to the instructor by 2PM July 11.
• 06/17: suggested solutions to HW#7 (Problem 4) revised.
• 06/13: suggested solutions to HW#8 and HW#9 available.
• 06/01: HW#10 due on 06/13.
• 05/30: Collection of algorithm animations implemented by Ming-Hsien.
• 05/29: slides for Dynamic Programming and for NP-Completeness plus a note available.
• 05/29: HW#9 due on 06/07.
• 05/23: HW#8 due on 05/30.
• 05/23: reminder: there is a TA session today!
• 05/23: suggested solutions to HW#6 and HW#7 available.
• 05/23: slides for Advanced Graph Algorithms available.
• 05/16: Grade Report of the Midterm available (one error corrected on 05/17); email inquiries, if any, to the instructor.
• 05/16: Suggested Solutions to Midterm Problems available.
• 05/09: HW#7 due on 05/16.
• 05/09: HW#5 due on 05/23.
• 05/02: HW#6 due on 05/09.
• 05/02: slides for Basic Graph Algorithms available.
• 04/25: slides for Searching and Sorting and for String Processing available.
• 04/17: suggested solutions to HW#3 and HW#4 available.
• 04/11: slides for Data Structures (A Supplement) available.
• 03/25: reminder: no class meeting on 3/28.
• 03/21: suggested solutions to HW#1 improved.
• 03/21: HW#4 due on 04/07.
• 03/20: suggested solutions to HW#1 and HW#2 available.
• 03/19: slides for Design by Induciton available.
• 03/14: Slide 23 for Analysis of Algorithms enhanced.
• 03/14: HW#3 due on 03/21.
• 03/13: slides for Analysis of Algorithms and a note on Solving a Recurrence Relation with Generating Functions available.
• 03/07: HW#2 due on 03/14.
• 02/21: Problem 3 (2.19) replaced by Problem 3 (2.14) in HW#1.
• 02/21: HW#1 due on 03/07.
• 02/18: slides for Introduction and Mathematical Induction and a note on Proving a Loop Invariant available.

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

Monday 2:20~5:20PM, Room 102, Management II.

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

Ming-Hsien Tsai (蔡明憲), 3366-1205, Xmhtsai208@gmail.comX (between the enclosing pair of X's);
Jing-Jie Lin (林靖婕), 3366-1205, Xgrace6349@gmail.comX (between the enclosing pair of X's);
Jen-Feng Shih (施任峰), 3366-1205, Xr98725050@ntu.edu.twX (between the enclosing pair of X's).
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM.

• [M] Introduction to Algorithms - A Creative Approach, U. Manber, Addison-Wesley, 1989.
  
• [C] Introduction to Algorithms, Third Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2009.

This course provides an introduction to the design and analysis of computer algorithms. A particular emphasis is given to principles of mathematical induction and their use in designing algorithms. The course will 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 four TA sessions on 3/21, 4/11, 5/16, and 5/30, making up the missed class meeting on 3/28.)

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/21a) [slides]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/21b, 3/7) [slides;note]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/14) [slides;note]
• Design by Induction [M: Ch. 5] (1.5 weeks: 3/21*, 4/11a*) [slides]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 4/11b) [slides]
• Midterm (2011/04/18)
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (1.5 weeks: 4/25, 5/2a) [slides]
• String Processing [M: Ch. 6; C: Ch. 32] (1.5 weeks: 5/2b, 5/9) [slides]
• Graph Algorithms [M: Ch. 7; C: Ch. 22,23,24,25,26] (2 weeks: 5/16*, 5/23) [slides: Basic Graph Algorithms, Advanced Graph Algorithms]
• Dynamic Programming [C: Ch.15] (1 week: 5/30*) [slides]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (1 week: 6/13) [slides;note]
• Final (2011/06/20)

Homework 20%, Participation 10%, Midterm 30%, Final 40%.