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/04: grade report available (updated 07/09); please send inquiries, if any, to the instructor by 2PM July 07.
• 06/11: slides for Reduction and a note on NP-Completeness available.
• 06/11: slides from TA sessions: HW#6, HW#7, HW#8, HW#9.
• 06/04: slides for NP-Completeness available.
• 05/28: HW#10 due on June 11.
• 05/28: slides for Dynamic Programming available.
• 05/14: HW#9 due on May 28.
• 05/14: slides for Advanced Graph Algorithms available.
• 05/14: HW#8 due on May 21.
• 05/02: Suggested Solutions to Midterm Problems available (revised on 05/06).
• 04/30: HW#7 due on May 7.
• 04/23: slides for String Processing and Basic Graph Algorithms available.
• 04/13: old exams: 1996-2011.
• 04/13: slides from TA sessions: HW#1, HW#2, HW#3, HW#4.
• 03/26: reminder: TA session on Apr. 9, 1:20-2:10PM.
• 03/26: reminder: no class meeting on Apr. 2.
• 03/26: HW#6 due on Apr. 16.
• 03/25: slides for Searching and Sorting available.
• 03/19: HW#5 due on Apr. 9.
• 03/18: slides for Data Structures (A Supplement) available.
• 03/12: reminder: TA session on Mar. 19, 1:20-2:10PM.
• 03/12: HW#4 due on Mar. 26.
• 03/11: slides for Design by Induction available.
• 03/05: HW#3 due on Mar. 19.
• 03/03: HW#2 due on Mar. 12.
• 03/03: slides for Analysis of Algorithms and a note on Solving a Recurrence Relation with Generating Functions available.
• 02/20: HW#1 due on Mar. 5.
• 02/20: eight copies of [Manber 1989] available for loan; please contact TAs Lai or Chang.
• 02/19: slides for Introduction and Mathematical Induction and a note on Proving a Loop Invariant 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.

Monday 1:30~2:00PM, Thursday 1:30~2:00PM, or by appointment, Room 1108, Management II.

Jing-Jie Lin (林靖婕), 3366-1205, Xgrace6349@gmail.comX (between the enclosing pair of X's);
Jui-Shun Lai (賴瑞舜), 3366-1205, Xnarration.lai@gmail.comX (between the enclosing pair of X's).
Wei-Hsien Chang (張暐獻), 3366-1205, Xb96705043@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. (Five copies of this book have been put on reserve at NTU Library in the 教師指定參考書區 under the name “BM-4演算法”.)
  
• [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/19, 4/9, 5/21, and 6/4, making up the missed class meeting on 4/2.)

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/20a) [slides: print,display]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/20b, 3/3) [slides: print, display; notes: Proving a Loop Invariant]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/5) [slides: print, display; notes: Solving a Recurrence Relation with Generating Functions]
• Design by Induction [M: Ch. 5] (1 week: 3/12) [slides: print, display]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 3/19a*) [slides: print, display]
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (2.5 weeks: 3/19b, 3/26, 4/9*) [slides: print, display]
• Midterm (2012/04/16)
• String Processing [M: Ch. 6; C: Ch. 32] (1.5 weeks: 4/23, 4/30a) [slides: print, display]
• Graph Algorithms: Basic [M: Ch. 7; C: Ch. 22,23,24,25,26] (1.5 weeks: 4/30b, 5/7) [slides: print, display]
• Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 22,23,24,25,26] (1 week: 5/14) [slides: print, display]
• Dynamic Programming [C: Ch.15] (1 week: 5/21*) [slides: print, display]
• Reduction [M: Ch. 10; C: Ch. 29] (1 week: 5/28) [slides: print, display]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/4*, 6/11) [slides: print, display; notes: An NP-Completeness Proof]
• Final (2012/06/18)

• Mathematical Induction (a Wikipedia page)
• What is an Algorithm? (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
• MIT OpenCourseWare: Introduction to Algorithms
• Stanford Coursera: Design and Analysis of Algorithms
• Animated Sorting Algorithms
• Graph Animations with Combinatorica

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