PPT《*》

4 s

100 <

1 s <

1 s <

1 s

1 s

18 min year 1,000 <

1 s <

1 s

1 s

18 min Very long Very long 10,000 <

1 s <

1 s

2 min

12 day Very long Very long

1 s

20 s

12 days

31710 year Very long Very long n

2 n

3 n l o g n n

2 n n !

1 0

2 5

1 0

6 * */74 Sorting 输入:A sequence of n number 输出:排列(permutation ) <

a

0 1 , a

0 2 , … , a

0 n >

使得: a

0 1 keydoA[i+1] ← A[i]i ← i C 1A[i+1] = key pseudocode i j key sorted A:

1 n * */74 Analyzing algorithms Need a computational modelRandom-access machine (RAM) modelInstructions are executed one after another. No concurrent operations.Arithmetic: add, subtract, multiply, divide, remainder, floor, ceilingData movement: load, store, copyControl: conditional/unconditional branch, subroutine call and return.Each of these instructions takes a constant amount of time. * */74 Running time Running time: The running time of an algorithm on a particular input is the number of primitive operations or steps executed.line consists only of primitive operations and takes constant timeInput size: number of items the total number of bits.more than one number: Graph the number of vertices and the number of edges * */74 The input size of sorting problem is n.Worst-case running time of Insert sort is O(n2). Example: * */74 Running time The running time depends on the input: an already sorted sequence is easier to sort. Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones.Generally, we seek upper bounds on the running time, because everybody likes a guarantee. * */74 Map of Algorithm Design Off-line problem Polynomial NP-C problem Improve cost running time Exact Algorithm Heuristic Approximate Algorithm Improve cost running time QualityAppro. ratio On-line problem New problem QualityAppro. ratio Polynomial * */74 课程内容 1. 数学基础1.1 算法基础 1.2 和(SUMS) 集合运算 (Sets) 1.3 特殊数 (Stirling numbers, Harmonic numbers, Eulerian numbers et al.)2. 基本算法2.1 分治 (Divide-and-Conquer)* 2.1.1 Mergesort * 2.1.2 自然数相乘(Multiplication)* 2.1.3 矩阵相乘(Matrix multiplication) 2.1.4 Discrete Fourier transform and Fast Fourier transform * */74 2.2 动态规划 (Dynamic Programming) 2.2.1 背包问题(Knapsack problem) 2.2.2 最长递增子序列(Longest increasing subsequence) 2.2.3 Sequence alignment 2.2.4 最长相同子序列(Longest common subsequence) 2.3.5 Matrix-chain multiplication 2.3.6 树上的独立集 (Max Independent set in tree) 课程内容 * */74 2.3 贪婪算法 (Greedy) 2.3.1 区间规划(Interval scheduling)2.3.2 集合覆盖(Set cover)2.3.3 拟阵(Matroids) 2.4 NP 问题 (NP-completeness) 2.4.1 The classes P and NP 2.4.2 NP-completeness and reducibility 2.4.3 NP-complete problems * 课程内容 * */74 2.5 近似算法 (Approximate Algorithm) 2.5.1 顶点覆盖问题 (Vertex cover) 2.5.2 负载平衡问题 (Load balancing) 2.5.3 旅行商问题 (Traveling salesman problem) 2.5.4 子集和问题 (Subset sum problem) 课程内容 * */74 3. 算法的应用3.1 局部搜索 (Local Search) 3.1.1 The Metropolis Algorithm and Simulated Annealing 3.1.2 Local Search to Hopfield Neural Networks(Nash Equilibria) 3.1.3 Maximum Cut Approximation via Local Search 课程内容 * */74 3.2 图论 (Graph Theorem) *3.2.1 图论的基本知识 (Fundamental)3.2.2 线性规划 (Linear Programming) 网络流(Network Flow),二分图,完全图的匹配 3.3计算几何学 (Computational Geometry)*3.3.1 基本概念与折线段的性质 (Line-segment ) 3.3.2 线段的一些性质 (Segments intersects )3.3.3 凸包问题 (Convex Hull )3.3.4 最近点对问题 (The closet pair of points)3.3.5 多边形三角剖分 (Polygon Triangulation) 课程内容 * */74 3.4 随机算法 (Randomized Algorithm) 3.4.1 随机变量与期望 3.4.2 A Randomized MAX-3-SAT 3.4.3 Randomized Divide-and-Conquer 3.5 在线算法(Online Algorithm) 3.5.1 Online Skying 3.5.2 Online Hiring 课程内容 *:备选内容 * */74 课程内容 * */74 教材 Textbook: Introduction to algorithms, Second Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. The MIT Press, 2001. ISBN: 0262032937.Recommended: Algorithm Design. Jon Kleinberg, ?va Tardos. Addison Wesley, 2005. ISBN: 0-321-29535-8. Rolf Nevanlinna Prize,