演算法

The study of algorithms is at the heart of computer science. This course focuses on fundamental results in this area, including the unifying principles and underlying concepts of algorithm design and analysis. We expect everyone to be comfortable reading, even writing, proofs. Several programming assignments will be given to embody the ideas. Moreover, we hope that everyone can learn general problem-solving techniques. Intended audience: 1. who are interested in computer science 2. who are computing something 3. who are learning problem-solving techniques

1. Data structures 2. Discrete mathematics 3. Computer programming in C 4. Computer programming in C++ *Two out of above four courses*

Lecture notes and related information will be released on the e3 course website.

1. Homework assignments 10% 2. Projects (two mini-projects: 20% + term project: 20%) 3. Two in-class tests (Midterm: 25% + Final: 25%)

• Basics of algorithm analysis
• Introduction
• Graphs
• Greedy algorithms
• Divide and conquer
• Dynamic programming
• Network flow
• NP and computational intractability
• Amortized analysis
• Linear Programming
• PSPACE
• Approximation algorithms
• Local search
• Randomized algorithms
• Algorithms that run forever

Required text: J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006. (J. Kleinberg, 20 Best Brains under 40, Discover Magazine, 2008) Reference books: S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill, 2007. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Third Edition, McGraw Hill/The MIT Press, 2009.

地點

ED540

時間

12:00--12:30, Mondays (made by appointment)

聯絡方式

huiru.jiang@gmail.com