教学目的、要求
计算机及相关学科硕士研究生的学科基础课。使学生掌握计算机算法的设计方法，学会分析算法的空间和时间复杂性。具体包括： 1） 抽象能力：能够认识实际问题的数学本质，从实际问题中抽象成数学（算法）问题； 2） 算法设计：分析问题的难度，并基于对算法问题的观察设计求解算法； 3） 算法分析：分析算法的空间和时间复杂性；
预修课程
离散数学、数据结构、一门编程语言。我们希望修课学生具有如下能力： 1） 掌握基本数据结构，比如lists, trees, heaps, sorting and searching； 2） 基本的数学能力，比如数学归纳法； 3） 了解可计算性，以及具有一定的编程经验；
教材
 T.H. Cormen, C.E. Leiserson, R. Rivest, and C. Stein, Algorithms (2nd ed.), MIT Press, 2001. Widely available.  J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.  R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge U. Press, 1995 Christos H. Papadimitriou, Kenneth Steiglitz, Kenneth Steiglitz. Combinatorial 　　Optimization: Algorithms And Complexity. Courier Dover Publications, 1998
主要内容
如果时间允许，本课程将涉及如下内容： 1) 问题难度：NP-完全性； 2) 基本算法设计技术：包括greedy, iteration, divide-and-conquer, dynamic programming, network flow, linear programming； 3) 对难问题的算法设计技术，包括approximation algorithms, local search, primal-dual algorithms, linear programming； 4) 随机算法：包括basic techniques from discrete probability, and applications to optimization. 5) 算法分析技术：包括worst-case and average-case, amortized, randomization, and competitive； 具体内容见下：  Week 1: Introduction to algorithm  Lecture 1: Introduction to algorithm: some representative problems; Lec1.pdf ; Lec1-regular-expression-problem ; Lec1 demo of GS algo (by K. Wayne)  Lecture 2: Basic algorithm analysis techniques, worst-case, average-case, and amortized analysis; Lec2.pdf ; Lec2 TableInsert (by C. Leiserson) Reading material: Chapter 1 of Algorithm design, Chapter 17 of Introduction to Algorithms  Week 2 : Problem hardness  Lecture 3: Problem hardness: Polynomail-time reduction; Lec3.pdf  Lecture 4: NP-Hard problems: sequecing problem, partitioning, coloring, SAT, etc. Lec4.pdf , 2SAT is in P (by D. Moshko ) Reading material: Computer and intractability, Chapter 8 of Algorithm design, Chapter 34 of Introduction to Algorithms  Week 3: Basic Algorithm Techniques;  Lecture 5: Divide-and-conquer technique, and the combination with randomization; Lec5.pdf ; demo merge (by K. Wayne) ; demo merge inversion (by K. Wayne) Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design  Lecture 6: Dynamic programming technique; Lec6.pdf ; RNA secondary structure prediction (by Sarah Aerni) ; Edit distance (by Andrew McCallum) Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design  Week 4: More on basic algorithm techniques;  Lecture 7: Greedy technique Lec7.pdf ; demo of Dijkstra’s algorithm (by K. Wayne) ; demo of Interval Scheduling algorithm (by K. Wayne) Reading material: Chapter 2,15,16,7,33.4 of Introduction to Algorithms, Chapter 5,4,6 of Algorithm design  Lecture 8: Linear programming: Simplex algorithm Lec8.pdf Reading material: Chapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity.  Week 5: Linear programming and network flow;  Lecture 9: Linear programming: duality; Lec9.pdf Reading material: Chapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity.  Lecture 10: Network flow and its applications; Lec10.pdf , Network-flow applications (by K. Wayne) , Network-flow research history (by A. Schrijver) , demo of Ford-Fulkeson algorithm Reading material: Chapter 26 of Introduction to Algorithms, Chapter 7 of Algorithm design, Combinatorial optimization: algorithm and complexity.  Week 6: Solving hard problems: approximation and randomization  Lecture 11: Approximation algorithm: a brief introduction; Lec11.pdf , Parameteric pruning algorithm for K-Center problem (by P. Potikas) Reading material: Chapter 35 of Introduction to Algorithms, Chapter 11 of Algorithm design, Approximation algorithm by V. Vazirani.  Lecture 12: Randomized algorithm: a brief introduction; Lec12.pdf , Hashing (by K. Wayne) Reading material: Chapter 35 of Introduction to Algorithms, Chapter 13 of Algorithm design, Randomized Algorithm by R. Motwani and P. Raghavan.  Week 7: Solving hard problems: special cases and heuristics  Lecture 13: Extending limits of tractability; Lec13.pdf Reading material: Chapter 10 of Algorithm design, and lecturs by D. P. Williamson.  Lecture 14: Heuristics (local search strategy);  Lec14 Local Search (by K. Wayne) Reading material: Chapter 11 of Algorithm design, and Combinatorial optimization: algorithm and complexity.  Week 8: String matching problem, Selection problem, and Paging problem.  Lecture 15: Selection problem: linear deterministic algorithm, randomized divide-and-conquorer algo, and random sampling; Lec15.pdf , Two papers on the selection problem (by BFPRT, and FR)  Lecture 16: Cache paging problem: FF, LRU, and randomized algo; Lec16.pdf  Lecture 17: String matching problem: DFA, KMP method, randomized finger-print, and Karp-Rabin algo; Lec17.pdf  Week 9: Closest string and substring problem, Bi-clustering problemRandomization algorithms  Lecture 18: Closest string and substring problems: random rounding and random sampling; Lec18.pdf  Lecture 19: Bi-Clustering problem: random rounding, a new random sampling idea; Lec19.pdf  Week 10: MaxCut problem  Lecture 20: MaxCut problem: Hardness, Local search algorithm, randomization algorithom, derandomiziation, and SDP approach; Lec20.pdf