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/11: grade report available; please send inquiries, if any, to the instructor by 2PM 07/12.
• 06/18: slides from TA sessions: HW#1-2, HW#4, HW#6, HW#7, HW#8, HW#9.
• 06/06: notes/slides for NP-Completeness and an appendix available.
• 05/31: HW#10 (revised as discussed in class) due on 06/14.
• 05/31: notes/slides for Reduction available.
• 05/24: HW#9 due on 05/31.
• 05/24: notes/slides for Dynamic Programming available.
• 05/17: HW#8 due on 05/24.
• 05/17: notes/slides for Advanced Graph Algorithms available.
• 05/10: Suggested Solutions to Midterm Problems available.
• 05/03: notes/slides for Basic Graph Algorithms available.
• 04/27: change of schedule: TA session on 5/3 moved to 5/10.
• 04/26: HW#7 due on 05/10.
• 04/25: notes/slides for String Processing available.
• 04/11: HW#6 due on 04/26.
• 04/11: old exams.
• 04/05: HW#5 due on 04/14.
• 03/29: notes/slides for Searching and Sorting available.
• 03/23: the date of midterm reverted to follow the NTU schedule (which is 4/19).
• 03/23: notes/slides for A Supplement to Data Structures available.
• 03/15: HW#4 due on 03/29.
• 03/15: notes/slides for Design by Induction available.
• 03/08: HW#3 due on 03/22.
• 03/08: notes/slides for Analysis of Algorithms and an appendix on Solving a Recurrence Relation with Generating Functions available.
• 03/01: HW#2 due on 03/15.
• 03/01: notes on Proving a Loop Invariant available.
• 02/23: HW#1 due on 03/08.
• 02/23: notes/slides for Introduction and for Mathematical Induction available.
• 02/17: this website announced.

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

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

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

Willy Chang (張子建), 3366-1205, Xr03725007@ntu.edu.twX (between the enclosing pair of X's).
Po-Chuan Chien (簡伯銓), Xr04725015@ntu.edu.twX (between the enclosing pair of X's).

• [M] Introduction to Algorithms - A Creative Approach, U. Manber, Addison-Wesley, 1989. (Four copies of this book have been put on reserve at NTU Library in the B1-教師指定參考書區 under 演算法(BM-4). Additionally, eight copies are available for loan; please contact one of the TAs.)
• [C] Introduction to Algorithms, Third Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2009. (開發圖書代理; one copy of this book has been put on reserve at NTU Library in the B1-教師指定參考書區 under (FF-9).)

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/15, 3/29, 5/10, and 6/7.)

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/23a) [notes, slides]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/23b, 3/1) [notes, slides, Proving a Loop Invariant (the gcd example, the original example)]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/8) [notes, slides, Solving a Recurrence Relation with Generating Functions]
• Design by Induction [M: Ch. 5] (1.5 weeks: 3/15*, 3/22a) [notes, slides]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 3/22b) [notes, slides, Building an AVL Tree (Illustration)]
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (2 weeks: 3/29*, 4/12) [notes, slides, Heapsort (Illustration), Bottom-Up Heap Building (Illustration)]
• Midterm (2016/04/19)
• String Processing [M: Ch. 6; C: Ch. 32] (1 week: 4/26) [notes, slides, Construction of a Huffman Tree (Illustration)]
• Graph Algorithms: Basic [M: Ch. 7; C: Ch. 22,23,24,25,26] (2 weeks: 5/3, 5/10*) [notes, slides, Dijkstra's Algorithm (Illustration), Prim's Algorithm (Illustration)]
• Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 22,23,24,25,26] (1 week: 5/17) [notes, slides]
• Dynamic Programming [C: Ch.15] (1 week: 5/24) [notes, slides]
• Reduction [M: Ch. 10; C: Ch. 29] (1 week: 5/31) [notes, slides]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/7*, 6/14) [notes, slides, An NP-Completeness Proof]
• Final (2016/06/21)

• Mathematical Induction (a Wikipedia page)
• Structural 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
• The website of ACM-ICPC (International Collegiate Programming Contest)

Homework 20%, Participation 10%, Midterm 35%, Final 35%.