Algorithms, Spring 2010

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.