算法设计英文版课件：ALG_review

1、The design and Analysis of Computer AlgorithmsReviewThe design and Analysis of Computer AlgorithmsOutlineThe type of problems in the final exam. Key contents in every chapter.The type of problems in the final exam.1. Ask you to answer simple questions, such as: What is the difference between algorit

2、hm and problem? 2. Algorithm question and its calculation, such as: Use Strassens algorithm to compute the product of .Key contents in every chapterChapter 1 IntroductionWhat is an algorithm? And its properties. What is an algorithmAn algorithm is composed of a set of steps for solving a specific pr

3、oblem. It should satisfy the following properties:Finiteness (the number of steps should be finite)Definiteness (to compute 5/0 is not definite)Effectiveness (to compute 1/3 as an infinite decimal is not effective)Zero or more inputs and one or more outputsTermination (OS is not an algorithm)Analysi

4、s of algorithmsMeasure the goodness of algorithmsefficiencyasymptotic notations: e.g. O(n2)worst caseaverage caseamortizedMeasure the difficulty of problemsNP-completeundecidablelower boundKey contents in every chapterChapter 2 The complexity of Algorithms and The lower Bounds of ProblemsWhat is the

5、 goodness of an algorithm? To understand the complexities of some famous algorithms, such as: Divide-and-Conquer, some sort algorithms, 2-D ranking finding, and so on. The goodness of an algorithm Time complexity (more important)Space complexityFor a parallel algorithm :time-processor productFor a V

6、LSI circuit :area-time (AT, AT2)2.1 The time complexity of an algorithm Measure the goodness of an algorithm Time complexity of an algorithmefficient (algorithm)worst-caseaverage-caseAmortizedThe goodness of an algorithm Time complexity (more important)Space complexityFor a parallel algorithm :time-

7、processor productFor a VLSI circuit :area-time (AT, AT2)2.1 The time complexity of an algorithm Measure the goodness of an algorithm Time complexity of an algorithmefficient (algorithm)worst-caseaverage-caseAmortizedWe can use the number of comparisons to measure a sorting algorithm.Key contents in

8、every chapterChapter 3 The GREEDY METHODWhat is The greedy method? Some algorithms to be solved by the greedy method, such as: Shortest paths on a multi-stage graph, Minimum spanning trees (MST) algorithms, include: Kruskals algorithm for finding MST, Prims algorithm for finding MST, Knapsack proble

9、m, Huffman algorithm. An example of Kruskals algorithm(1,2) - 10 (3,5) - 35(3,6) - 15 (2,5) - 40(4,6) - 20 (1,5) - 45(2,6) - 25 (2,3) - 50(1,4) - 30 (5,6) - 55An example for Prims algorithm(1,2) - 10 (3,5) - 35(3,6) - 15 (2,5) - 40(4,6) - 20 (1,5) - 45(2,6) - 25 (2,3) - 50(1,4) - 30 (5,6) - 55The se

10、t A 1, 2 1, 2, 6 1, 2, 6, 3 1, 2, 6, 3, 4 1, 2, 6, 3, 4, 5An example for Prims algorithmThe set B=V-A 3, 4, 5, 6 3, 4, 5 4, 5 5 The set V (Include all vertices): 1, 2, 3, 4, 5, 6Step 1Step 2Step 3Step 4Step 5An example of Huffman algorithmSymbols: A, B, C, D, E, F, G freq. : 2, 3, 5, 8, 13, 15, 18Hu

11、ffman codes:A: 10100B: 10101 C: 1011 D: 100 E: 00 F: 01G: 11Huffman codesKey contents in every chapterChapter 4 The Divide-and-Conquer StrategyWhat is the Divide-and-Conquer Strategy? What is the general steps used in this kinds of Algorithms? Some kinds of problems solved by the Divide-and-Conquer

12、algorithms, such as: 2-D maxima finding problem, The closest pair problem, The convex hull problem, The Voronoi diagram problem, Matrix multiplication (Strassens matrix multiplicaiton), Fast Fourier transform (FFT) . Divide-and-conquer for maxima findingThe maximal points of SL and SR P = (A11 + A22

13、)(B11 + B22)Q = (A21 + A22)B11R = A11(B12 - B22)S = A22(B21 - B11)T = (A11 + A12)B22U = (A21 - A11)(B11 + B12)V = (A12 - A22)(B21 + B22).C11 = P + S - T + VC12 = R + TC21 = Q + SC22 = P + R - Q + UStrassens matrix multiplicaiton C11 = A11 B11 + A12 B21 C12 = A11B12 + A12 B22 C21 = A21 B11 + A22 B21

14、C22 = A21 B12 + A22 B22 Fast Fourier transform (FFT) Fourier transform Inverse Fourier transform Discrete Fourier transform(DFT) Given a0, a1, , an-1 , compute Inverse DFT: FFT algorithmFFT algorithm when n=4 n=4, w=ei2/4 , w4=1, w2=-1 b0=a0+a1+a2+a3 b1=a0+a1w+a2w2+a3w3 b2=a0+a1w2+a2w4+a3w6 b3=a0+a1

15、w3+a2w6+a3w9 another form: b0=(a0+a2)+(a1+a3) b2=(a0+a2w4)+(a1w2+a3w6) =(a0+a2)-(a1+a3) When we calculate b0, we shall calculate (a0+a2) and (a1+a3). Later, b2 van be easily calculated. Similarly, b1=(a0+ a2w2)+(a1w+a3w3) =(a0-a2)+w(a1-a3) b3=(a0+a2w6)+(a1w3+a3w9) =(a0-a2)-w(a1-a3). Key contents in

16、every chapterChapter 5 Three Searching StrategyTo understand what kinds of problem could be solved by this Three Searching Strategy? To understand what are Breadth-first search (BFS), Depth-first search (DFS), Best-first search strategy, Branch-and-bound strategy?Some problems solved by this algorit

17、hm, such as: Satisfiability problem, Hamiltonian circuit problem, Hill climbing, Personnel assignment problem, The traveling salesperson optimization problem, The 0/1 knapsack problem, A* algorithm. The tree representation of whether there exists a Hamiltonian circuit.Breadth-first search (BFS) 8-pu

18、zzle problemThe breadth-first search uses a queue to hold all expanded nodes. All nodes on the level of the tree are examined before the nodes on the next level are examined. Breadth-first search strategy An 8-puzzle problem solved by a best-first search scheme.A solution treeAll possible solutions

19、can be represented by a solution tree.Cost matrixCost matrix Apply the best-first search scheme:Cost matrixReduced cost matrix Reduced cost matrixBranch-and-bound for the personnel assignment problemBounding of sub-solutions: The A* algorithm Used to solve optimization problems.Using the best-first

20、strategy.If a feasible solution (goal node) is obtained, then it is optimal and we can stop.Cost function of node n : f(n)f(n) = g(n) + h(n)g(n): cost from root to node n.h(n): estimated cost from node n to a goal node.h*(n): “real” cost from node n to a goal node.If we guarantee h(n) h*(n), then f(

21、n) = g(n) + h(n) g(n)+h*(n) = f*(n)An example for A* algorithmA graph to illustrate A* algorithm.Stop if the selected node is also a goal node.Step 1:Step 2: Expand node A.Step 3: Expand node C. Step 4: Expand node D. Step 5: Expand node B. Step 6: Expand node F.Node I is a goal node. Thus, the fina

22、l solution has been obtained. Key contents in every chapterChapter 6 Prune-and-searchWhat is the Prune-and-search approach and the general prune-and-search? Some problems solved by Prune-and-search approach, such as: Linear programming with two variables, The 1-center problem. The boundary F(x): F(x

23、) =The optimum solution x0: F(x0) = F(x) Determining the direction of the optimum solutionLet ym = F(xm) = Case 1: ym is on only one constraint. Let g denote the slope of this constraint.If g 0, then x0 xm.If g xm. The cases where xm is on only one constrain.Key contents in every chapterChapter 7 Dy

24、namic ProgrammingWhat is the dynamic programming strategy? To solve a problem by using dynamic programming, we should :Find out the recurrence relations.Represent the problem by a multistage graph.Key contents in every chapterSome problems solved by the dynamic programming strategy, such as: The sho

25、rtest path in multistage graphs(include forward approach, and Backward approach), The resource allocation problem, The longest common subsequence (LCS) problem, 0/1 knapsack problem, Matrix-chain multiplication, Single step graph edge searching. The shortest path in multistage graphsGiven the multis

26、tage graph likes below: Solve it by dynamical programming algorithm with forward and backward approaches. Backward approach (forward reasoning) d(S, A) = 1d(S, B) = 2d(S, C) = 5d(S,D)=mind(S,A)+d(A,D), d(S,B)+d(B,D) = min 1+4, 2+9 = 5 d(S,E)=mind(S,A)+d(A,E), d(S,B)+d(B,E) = min 1+11, 2+5 = 7 d(S,F)

27、=mind(S,B)+d(B,F), d(S,C)+d(C,F) = min 2+16, 5+2 = 7Dynamic programming approach Dynamic programming approach (forward approach): d(S, T) = min1+d(A, T), 2+d(B, T), 5+d(C, T) d(A,T) = min4+d(D,T), 11+d(E,T) = min4+18, 11+13 = 22.The LCS algorithmLet A = a1 a2 am and B = b1 b2 bn Let Li,j denote the

28、length of the longest common subsequence of a1 a2 ai from A and b1 b2 bj from B.L0,0 = L0,j = Li,0 = 0 for 1im, 1jn. We have to calculate for the LCS problem: Lm,nThe dynamic programming approach for solving the LCS problem:Time complexity: O(mn).Tracing back in the LCS algorithme.g. A = b a c a d,

29、B = a c c b a d c bAfter all Li,js have been found, we can trace back to find the longest common subsequence of A and B.LCS of Nonebbabacbac, acaacada1 and Ba2 and Ba3 and Ba4 and Ba5 and Ba0 and B0/1 knapsack problemThe 0/1 knapsack problem can be described by a multistage graph. The dynamic progra

30、mming approachLet fi(Q) be the value of an optimal solution to objects 1,2,3,i with capacity Q.fi(Q) = max fi-1(Q), fi-1(Q-Wi)+Pi The optimal solution is fn(M). Let m(i, j) denote the minimum cost for computing Ai Ai+1 AjComputation sequence :For following example: Their number of row and column are

31、: p1=10, p2=20, p3=50, p4=1, p5=100, according above dynamic algorithm, we can construct the following table: Chapter 8 The THEORY OF NP_COMPLETENESSWhat are the NP, P, NP-hard and NPC problems? What id their relationship? Some concepts of NPC. Proof of NP-Completeness. Some problems solved by NPC a

32、lgorithm, such as: Hamiltonian cycle problem, Traveling salesperson problem, 0/1 knapsack problem. Key contents in every chapterKey contents in every chapterChapter 11 Randomized Algorithms What is the Randomized Algorithm, and introduce its different types. A randomized algorithm for closest pair f

33、inding. A randomized algorithm to test whether a number is prime. A randomized algorithm for pattern matching. Thank you very much! XiaoYang Yan2014, 06, 185 - 23Dr. Yan A solution treeAll possible solutions can be represented by a solution tree.5 - 24Dr. Yan Cost matrixCost matrix Apply the best-first search scheme:5 - 25Dr. Yan Cost matrixReduced cost matrix Reduced cost matri