Course Overview: This is a graduate course on the design and analysis of algorithms, covering several advanced topics not studied in typical introductory courses on algorithms. This course will consist of a number of major sections. The first will be a short review of some preliminary material, including asymptotics, recurrences, and analysis and design techniques. These have been covered in earlier courses, and so we will breeze through them pretty quickly. We will then discuss approaches to designing optimization algorithms, including greedy algorithms, dynamic programming, linear programming, and NP-complete problems. The next major focus will be on graph algorithms. This will include a review of elementary graph algorithms. Next we will discuss minimum spanning trees and shortest paths. Finally, we will briefly introduce some important distributed algorithms arising from networked environments. After mid-term, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. The goal is for the class to be broad rather than deep. Our plan is to touch upon the machine learning areas. We will select material adaptively based on the background, interests, and rate of progress of the students.
I. Foundations 1. Introduction 2. Analyzing and designing algorithms 3. Mathematical foundations: Growth of functions and recurrences 4. Data structures: Trees 5. Probability and average complexity II. Graph Algorithms 6. Elementary graph algorithms 7. Minimum spanning trees 8. Shortest paths 9. Maximum flow 10. Overview of distributed graph algorithms III. Optimization Algorithms 11. Greedy algorithms 12. Dynamic programming 13. Linear programming 14. NP-complete problems 15. Mid-term Exam IV. Research Topics of Term Project 16. Approximation algorithms 17. Machine learning algorithms 18. Data mining algorithms
Grading: 30% Assignments 30% Mid-term Exam 40% Term Project Presentation
Reference books: There is no textbook required for the course. Lecture notes will be made available from the course web page (北科i學園). Please visit the course webpage frequently for extra reading material. Reference books for each topic are listed below. 1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, The MIT Press, 2001. (開發) 2. S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill, 2008. (開發) 3. K. A. Berman and J. L. Paul, Algorithms: Sequential, Parallel, and Distributed, Thompson Publishing, 2005. 4. N. Santoro, Design and Analysis of Distributed Algorithms, John Wiley & Sons, 2007. 5. P. Domingos, The Master Algorithm, Basic Books, 2015. 6. E. Alpaydn, Introduction to Machine Learning, 2nd Ed., The MIT Press, 2010. 7. Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014.