演算法分析與設計

臺北科技大學 114-2 學期課程，課號 357199。

課程大綱

The course gives a broad introduction about the design and analysis of computer algorithms. General topics to be covered include: growth of functions, recurrences, sorting and order statistics, fundamental and advanced data structures, dynamic programming, greedy algorithms, graph algorithms, and NP-completeness.

課程進度

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)

評量方式

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

教材

【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】 使用外文原文書：是 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.