本课程为计算机应用学科研究生的专业核心课程。本课程讲授和讨论计算机算法前沿研究领域的主要思想和关键技术。主要内容有算法分析技术、分治法、动态规划法、贪心法、线性规划的单纯形法和对偶法、网络流、多项式归约、NP难问题、近似算法、随机算法、参数化算法和树分解、启发式方法（局部搜索）等。
    通过本课程的学习，希望学生能了解计算机算法前沿研究领域，了解算法设计与分析的最新研究成果，掌握基本思想和关键技术，培养学生三个方面的能力，即将实际问题抽象成算法问题的建模能力、观察问题特性并相应设计算法的能力，以及分析算法性能的能力。

数据结构、计算机程序设计

•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. 
 •计划在2015年度形成自编教材

第一章  Introduction to algorithm and basic design techniques
Lecture 1: Introduction to algorithm: some representative problems; 
Lec1.pdf ; demo of Gale-Shapley algorithm (by K. Wayne)
Lecture 3: Divide-and-conquer technique, and the combination with randomization; 
Lec5.pdf ; demo merge (by K. Wayne) ; demo merge inversion (by K. Wayne) 
Reading material:
oChapter 1 of Algorithm design,
oChapter 17 of Introduction to Algorithms,
oLecture 8, 9 of The Design and Analysis of Algorithms,
第二章  Basic algorithm design techniques;
Lecture 4: Dynamic programming technique; 
Lec6.pdf ; RNA secondary structure prediction (by Sarah Aerni) ; Edit distance (by Andrew McCallum); Publick-key cryptosystem (by Charles Clancy) 
Reading material:
oChapter 2,15,16,7,33.4 of Introduction to Algorithms,
oChapter 5,4,6 of Algorithm design,
第三章 Still more on basic algorithm design techniques;
Lecture 5: Greedy technique 
Lec7.pdf ; demo of Dijkstra’s algorithm ; demo of Interval Scheduling algorithm (by K. Wayne), Lec7-Heap.pdf ; BinomialHeaps.pdf (by Kevin Wayne) , FibonacciHeaps.pdf (by Kevin Wayne) ,FibonacciHeaps.pdf (by Kevin Wayne) , DemoBinaryHeap.pdf (by Kevin Wayne) , DemoHeapify.pdf (by Kevin Wayne) ,
Lecture 2: Basic algorithm analysis techniques, worst-case, average-case, and amortized analysis; 
Lec2.pdf , demo of TableInsert (by C. Leiserson),
Reading material:
oChapter 2,15,16,7,33.4 of Introduction to Algorithms,
oChapter 5,4,6 of Algorithm design
第四章  Linear programming
Lecture 6: Linear programming: Simplex algorithm 
Lec8.pdf , an example of cycling in simplex algorithm (given by E. M. L. Beale, 1955), an example of Klee-Minty cube, a script to generate Klee-Minty cube (with noise), a script to generate Klee-Minty cube (without noise), the DIET problem (in.math format) ,
Reading material:
oChapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity.
第五章    Linear programming (cont’d)
Lecture 9: Linear programming: duality; 
Lec9.pdf , A gnuplot script to illustrate Lagrangian dual , Lec9-DIET.math , Lec9-DIET-Dual.math , Lec9-DIET-b1-2001.math , Lec9-DIET-b2-56.math , Lec9-DIET-b3-801.math
Reading material:
oChapter 29 of Introduction to Algorithms,
oCombinatorial optimization: algorithm and complexity.
第六章  Network flow
Lecture 10: Network flow and its applications; 
Lec10.pdf , Network-flow applications , demo of Ford-Fulkerson algorithm , Multiple optimal solutions , demo of Edmonds-Karp algorithm , demo of Dinic algorithm , irrational capacities might lead to endless iterations ,
Reading material:
oChapter 26 of Introduction to Algorithms,
oChapter 7 of Algorithm design, Combinatorial optimization: algorithm and complexity,
第七章Problem intrinsic property: Hardness
Lecture 11: Problem hardness: Polynomial-time reduction; 
Lec3.pdf
Reading material:
oComputer and intractability,
oChapter 8 of Algorithm design,
oChapter 34 of Introduction to Algorithms
第八章NP-Completeness
Lecture 12: NP-Hard problems: packing problem, covering problems, sequencing problem, partitioning, coloring, SAT, numbering problems, etc. 
Lec4.pdf , Turing machine demo (by Zhen Ji) , Turing machine demo (by Andrew Hodges, Turing machine (by K. Wayne) , Computability (by K. Wayne) , 2SAT is in P (by D. Moshko ) ,
Reading material:
oComputer and intractability,
oChapter 8 of Algorithm design,
oChapter 34 of Introduction to Algorithms
第九章Solving hard problems: approximation and randomization
Lecture 11: Approximation algorithm: a brief introduction; 
Lec11.pdf , Parametric pruning algorithm for K-Center problem (by P. Potikas) , Lec11-SetCover-Primal.math , Lec11-SetCover-Dual.math , Lec11-MakeSpan.math ,
Reading material:
oChapter 35 of Introduction to Algorithms,
oChapter 11 of Algorithm design,
oApproximation algorithm by V. Vazirani.
第十章Solving hard problems: approximation and randomization
oLecture 12: Randomized algorithm: a brief introduction; 
Lec12.pdf , Hashing (by K. Wayne)
oReading material:
oChapter 35 of Introduction to Algorithms,
oChapter 13 of Algorithm design,
oRandomized Algorithm by R. Motwani and P. Raghavan.

第十一章：Solving hard problems: special cases and heuristics
Lecture 13: Extending limits of tractability; 
Lec13.pdf , TreePack: rapid side-chain prediction using tree-decomposition 
Reading material:
oChapter 10 of Algorithm design,
olectures by D. P. Williamson.

•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