This is an old revision of the document!
Table of Contents
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.
Announcements
- 11/02:
- Slides from TA sessions: HW#5
- (String Processing) Fix a bug in slide #18, fix a typo in slide #24, and add more description to slide #26
- 10/29: HW#6 due on 11/19.
- 10/25: (Searching and Sorting) Fix a typo in slide #38, update slide #50, and add one more slide after slide #51
- 10/22:
- HW#5 due on 10/29.
- A TA session is scheduled on 10/29 (between 1:20PM-2:10PM)
- 10/16:
- Slides from TA sessions: HW#2
- Fix errors in HW#4.
- 10/15: HW#4 due on 10/22.
- 10/08:
- HW#3 due on 10/15.
- A TA session is scheduled on 10/15 (between 1:20PM-2:10PM)
- 10/04: Fixed some typos in the slides for Analysis of Algorithms
- 10/02: Slides from TA sessions: HW#1
- 10/01: HW#2 due on 10/8.
- 09/19: A TA session is scheduled on 10/01 (between 1:20PM-2:10PM)
- 09/17: HW#1 due on 09/25.
Instructors
Yu-Fang Chen (陳郁方)
Institute of Information Science, Academia Sinica
02-27883799 ext 1514
Xyfc@iis.sinica.edu.twX (between the enclosing pair of X's)
Ming-Hsien Tsai (蔡明憲)
Institute of Information Science, Academia Sinica
02-27883799 ext 2411
Xmhtsai208@gmail.comX (between the enclosing pair of X's)
Lectures
Monday 2:20-5:20PM, Room 103, Building I, College of Management
Office Hours
By appointment
TAs
陳昀靖, Xr06725004@ntu.edu.twX (between the enclosing pair of X's)
賴冠廷, Xr06725007@ntu.edu.twX (between the enclosing pair of X's)
Textbooks
- [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
Syllabus/Schedule
- Introduction [M: Ch. 1; C: Ch. 1,2] (09/10) [slides]
- Mathematical Induction [M: Ch. 2; C: Ch. 4] (09/10,09/17) [slides]
- Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (10/01) [slides]
- Design by Induction [M: Ch. 5] (10/08) [slides]
- Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (10/15) [slides]
- Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (10/15,10/22) [slides]
- String Processing [M: Ch. 6; C: Ch. 32] [slides] (10/29)
- Midterm (11/05)
- Graph Algorithms: Basic [M: Ch. 7; C: Ch. 22,23,24,25,26] (11/12, 11/19) [slides]
- Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 22,23,24,25,26](11/26, 12/3)
- Dynamic Programming [C: Ch.15] (12/10)
- Reduction [M: Ch. 10; C: Ch. 29] (12/17)
- NP-Completeness [M: Ch. 11; C: Ch. 34] (12/24)
- Final (1/7)
Grading
Homework 20%, Participation 10%, Midterm 35%, Final 35%