Course Syllabus

Course Information：

Year-Semester Course Number Course Name Phase Credits Hours Required/Elective Instructor Class Student NO. Withdraw Note

Fall Semester
Year 2018 249104 Design and Analysis of Computer Algorithms 1 3.0 3 ★ CHUAN-MING LIU GCSIE 33 7 資工四與資工所合開

Year-Semester	Course Number	Course Name	Phase	Credits	Hours	Required/Elective	Instructor	Class	Student NO.	Withdraw	Note
Fall Semester Year 2018	249104	Design and Analysis of Computer Algorithms	1	3.0	3	★	CHUAN-MING LIU	GCSIE	33	7	資工四與資工所合開

Course Plan：

Instructor CHUAN-MING LIU

Email cmliu@ntut.edu.tw

Last Updated 2018-06-25 11:26:02

Course Objective 1. 數學基礎 1.1 函數成長率之漸近性質 1.2 遞迴關係之解 1.3 數學歸納法 2. 基本分析技巧 2.1 計算複雜度之上下限2.2 最差情況分析及平均情況分析 2.3 動態平均分析 3. 基本設計技巧 3.1 分擊法 3.2 貪婪法 3.3 動態規劃 3.4 隨機演算法 4. 計算複雜度 4.1 資訊理論證明法 4.2 對抗式證明法 4.3 問題之線性轉換 4.4 完全NP

Course Schedule 1. Introduction (0.5 week) 2. Asymptotic analysis (1.5 weeks) 3. Recurrence Relations (1 week) 4. Advanced Data Structures (2 weeks) 5. Average and worst analysis (1 weeks) 6. Lower Bounds (1 week) 7. Dynamic Programming (2 weeks) 8. Graph algorithms (1.5 weeks) 9. Search and Traversal Techniques (1.5 week) 10. NP-Completeness (2 weeks) 11. Approximation Algorithms (1 week) 12. New Trends in Algorithms (2 weeks) (* 1 week for exams, including midterm and final)

Evaluation and grading policy Assignments (40%): 7-9 homework sets. Midterm (25%) Final exam (35%)

Materials All right reserved. Do not reproduce without permission.

Foreign-language textbooks:Yes
Textbook: Introduction to Algorithms, 3nd edition. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. MIT Press Edition, 2009. References: 1. Computer Algorithms /C++, 2nd Edition. E. Horowitz, S. Sahni, and S. Rajasekaran, W.H. Freeman and Company, 1998. 2. Computer Algorithms, 3rd edition. S. Baase and A. V. Gelder. Addison-Wesley, 2000. 3. Algorithms in C++, 3rd. R. Sedgewick. Addison-Wesley, 1998. 4. Algorithms, R. Johnsonbaugh and M. Schaefer, Pearson Prentice Hall, 2004. 5. Algorithm Design, Jon Kleinberg and ?va Tardos, Pearson/Addison-Wesley, 2006. 6. Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2008. ISBN:978-007-125975-0.

The access to curricular consultation

Note
　

Instructor	CHUAN-MING LIU
Email	cmliu@ntut.edu.tw
Last Updated	2018-06-25 11:26:02
Course Objective	1. 數學基礎 1.1 函數成長率之漸近性質 1.2 遞迴關係之解 1.3 數學歸納法 2. 基本分析技巧 2.1 計算複雜度之上下限2.2 最差情況分析及平均情況分析 2.3 動態平均分析 3. 基本設計技巧 3.1 分擊法 3.2 貪婪法 3.3 動態規劃 3.4 隨機演算法 4. 計算複雜度 4.1 資訊理論證明法 4.2 對抗式證明法 4.3 問題之線性轉換 4.4 完全NP
Course Schedule	1. Introduction (0.5 week) 2. Asymptotic analysis (1.5 weeks) 3. Recurrence Relations (1 week) 4. Advanced Data Structures (2 weeks) 5. Average and worst analysis (1 weeks) 6. Lower Bounds (1 week) 7. Dynamic Programming (2 weeks) 8. Graph algorithms (1.5 weeks) 9. Search and Traversal Techniques (1.5 week) 10. NP-Completeness (2 weeks) 11. Approximation Algorithms (1 week) 12. New Trends in Algorithms (2 weeks) (* 1 week for exams, including midterm and final)
Evaluation and grading policy	Assignments (40%): 7-9 homework sets. Midterm (25%) Final exam (35%)
Materials	All right reserved. Do not reproduce without permission. Foreign-language textbooks:Yes Textbook: Introduction to Algorithms, 3nd edition. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. MIT Press Edition, 2009. References: 1. Computer Algorithms /C++, 2nd Edition. E. Horowitz, S. Sahni, and S. Rajasekaran, W.H. Freeman and Company, 1998. 2. Computer Algorithms, 3rd edition. S. Baase and A. V. Gelder. Addison-Wesley, 2000. 3. Algorithms in C++, 3rd. R. Sedgewick. Addison-Wesley, 1998. 4. Algorithms, R. Johnsonbaugh and M. Schaefer, Pearson Prentice Hall, 2004. 5. Algorithm Design, Jon Kleinberg and ?va Tardos, Pearson/Addison-Wesley, 2006. 6. Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2008. ISBN:978-007-125975-0.
The access to curricular consultation
Note