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.

• 7/09: grade report available; please send inquiries, if any, to the instructor by 12Noon July 10.
• 5/31: HW#10 due on June 11
• 5/31: slides for NP-Completeness and a note available
• 5/31: slides for Dynamic Programming available
• 5/17: HW#9 due on May 31
• 5/17: slides for Advanced Graph Algorithms available
• 5/13: HW#8 due on May 24
• 5/03: Solutions to Midterm Problems available
• 5/03: slides for Basic Graph Algorithms available
• 4/26: HW#5 and HW#7 due on May 10
• 4/24: slides for String Processing available
• 4/16: solutions to selected homework problems: HW#1, HW#2, HW#3, HW#4
• 4/13: HW#6 due on April 26; HW#5 (a programming exercise) to be given later
• 4/12: slides for Searching and Sorting available
• 3/29: HW#4 due on April 8 (at 9AM, for this assignment)
• 3/28: slides for Data Structures: A Supplement available
• 3/23: HW#3 due on March 29
• 3/21: slides for Design by Induction available
• 3/08: HW#2 due on March 15
• 3/08: slides for Analysis of Algorithms and notes on Loop Invariants and Generating Functions available
• 3/02: HW#1 due on March 8
• 2/22: PDF version of this page (as of 2010/02/22, without the announcements)
• 2/19: 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).

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

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

• [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.:

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/22a) [slides]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/22b, 3/1) [slides;note]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/8) [slides;note]
• Design by Induction [M: Ch. 5] (2 weeks: 3/15, 3/22) [slides]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (1 week: 3/29) [slides]
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (1.5 weeks: 4/12, 4/26a) [slides]
• String Processing [M: Ch. 6; C: Ch. 32] (1.5 weeks: 4/26b, 5/3) [slides]
• Graph Algorithms [M: Ch. 7; C: Ch. 22,23,24,25,26] (3 weeks: 5/10, 5/17, 5/24) [slides: Basic Graph Algorithms, Advanced Graph Algorithms]
• Selected Topics: Dynamic Programming and Mergeable Heaps [C: Ch.15,19] (1 week: 5/31) [Dynamic Programming]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/7, 6/14) [slides;note]

Homework 20%, Participation 10%, Midterm (4/19) 35%, Final (6/21) 35%.

Yi-Wen Chang (常怡文), 3366-1205, Xr97725004@ntu.edu.twX (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 (tentatively on 3/22, 4/12, 5/17, and 6/7), between 1:20 and 2:10PM.