Algorithms, Fall 2019

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.

• 01/18: grade report available; please send inquiries, if any, to the instructor by 10AM 01/20.
• 12/31: slides from TA sessions: HW#6, HW#7, HW#8, HW#9.
• 12/19: HW#10 due on 12/31; ICPC 2019 World Finals Problem E and Problem H.
• 12/17: notes/slides for Reduction and for NP-Completeness available.
• 12/10: HW#9 due on 12/17.
• 12/10: notes/slides for Dynamic Programming available.
• 11/25: HW#8 due on 12/03.
• 11/25: notes/slides for Advanced Graph Algorithms available.
• 11/19: HW#7 due on 11/26.
• 11/12: Suggested Solutions to Midterm Problems available.
• 11/12: notes/slides for Basic Graph Algorithms available.
• 10/30: slides from TA sessions: HW#1, HW#2, HW#3, HW#4.
• 10/30: old exams.
• 10/29: HW#6 due on 11/12.
• 10/29: notes/slides for String Processing available.
• 10/15: notes/slides for Searching and Sorting available.
• 10/13: HW#5 due on 10/29; ACM ICPC 2019 World Finals Problem A.
• 10/08: HW#4 due on 10/15.
• 10/08: notes/slides for A Supplement to Data Structures available.
• 10/01: HW#3 due on 10/08.
• 10/01: notes/slides for Design by Induction available.
• 09/23: HW#2 due on 10/01.
• 09/23: notes/slides for Analysis of Algorithms available.
• 09/16: HW#1 due on 09/24.
• 09/10: notes/slides for Introduction and for Mathematical Induction available.
• 09/03: this website created on 08/31.

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 103, 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.

Hung-Yang Lin (林宏陽), Xr08725027@ntu.edu.twX (between the enclosing pair of X's).
Wayne Zeng (曾守瑜), Xr08725038@ntu.edu.twX (between the enclosing pair of X's).
Rose Chou (周若涓), Xr08725008@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, eleven 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 six TA sessions on 9/24, 10/8, 10/29, 11/19, 12/10, and 12/31.)

• Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 9/10a) [notes, slides]
• Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 9/10b, 9/17) [notes, slides]
• Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 9/24*) [notes, slides]
• Design by Induction [M: Ch. 5] (1.5 weeks: 10/1, 10/8a*) [notes, slides]
• Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (1 week: 10/8b, 10/15a) [notes, slides, Building an AVL Tree (Illustration)]
• Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (1.5 weeks: 10/15b, 10/22) [notes, slides, Heapsort (Illustration), Bottom-Up Heap Building (Illustration)]
• String Processing [M: Ch. 6; C: Ch. 32] (1 week: 10/29*) [notes, slides, Construction of a Huffman Tree (Illustration)]
• Midterm (2019/11/05)
• Graph Algorithms: Basic [M: Ch. 7; C: Ch. 22,23,24,25,26] (2 weeks: 11/12, 11/19*) [notes, slides, Dijkstra's Algorithm (Illustration), Prim's Algorithm (Illustration)]
• Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 22,23,24,25,26] (2 weeks: 11/26, 12/3) [notes, slides]
• Dynamic Programming [C: Ch.15] (1 week: 12/10*) [notes, slides]
• Reduction [M: Ch. 10; C: Ch. 29] (1 week: 12/17) [notes, slides]
• NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 12/24, 12/31*) [notes, slides]
• Final (2020/01/07)

• 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 ICPC (International Collegiate Programming Contest)

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