Algorithms, Spring 2013

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/03: grade report available; please send inquiries, if any, to the instructor by 2PM July 05.
• 06/14: slides from TA sessions: HW#6, HW#7, HW#8, HW#9.
• 06/03: notes/slides for NP-Completeness available.
• 05/29: reminder: there will be a TA session on 06/04.
• 05/28: HW#10 due on 06/11.
• 05/27: notes/slides for Dynamic Programming and for Reduction available.
• 05/21: HW#9 due on 05/28.
• 05/14: reminder: there will be a TA session on 05/21.
• 05/07: Suggested Solutions to Midterm Problems available.
• 05/06: HW#8 due on 05/14.
• 05/05: notes/slides for Advanced Graph Algorithms available.
• 04/29: notes/slides for Basic Graph Algorithms available.
• 04/22: HW#7 due on 04/30.
• 04/22: notes/slides for String Processing available.
• 04/09: slides from TA sessions: HW#1, HW#2, HW#3, HW#4.
• 04/09: old exams.
• 04/01: problem statement of 5.8 in HW#4 corrected.
• 03/27: reminder: there will be a TA session on 04/09.
• 03/26: HW#6 due on 04/16.
• 03/26: HW#5 due on 04/09.
• 03/25: notes/slides for Searching and Sorting available.
• 03/19: HW#4 due on 04/02.
• 03/19: notes/slides for Data Structures (A Supplement) available.
• 03/12: HW#3 due on 03/19.
• 03/11: notes/slides for Design by Induction available.
• 03/11: an appendix on Solving a Recurrence Relation with Generating Functions available.
• 03/04: notes/slides for Analysis of Algorithms available.
• 02/26: HW#2 due on 03/12.
• 02/19: HW#1 due on 03/05.
• 02/19: eight copies of [Manber 1989] available for loan; please contact TA Lai or Chang.
• 02/18: notes/slides for Introduction and Mathematical Induction and an appendix 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).

Tuesday 2:20~5:20PM, Room 205, Management II.
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM.

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

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).

• [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 skipped class meeting on 4/2.)

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

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

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