introduction to algorithms second edition by - utpa faculty ：算法导论第二版的utpa学院

Introduction to Algorithm,Instructor: Dr. Bin FuOffice: ENGR 3. 280 (Third Floor)Email: Textbook: Introduction to Algorithm (Second Edition) by Cormem, Leiserson, Rivest and Stein,Why study algorithms and performance?,Performance often draws the line between what is feasible and what is impossible. Algorithmic mathematics provides a language for talking about program behavior. (e.g., by using big-O notation) In real life, many algorithms, though different from each other, fall into one of several paradigms (discussed shortly). These paradigms can be studied.,Why these particular algorithms ?,In this course, we will discuss problems, and algorithms for solving these problems.,Why these algorithms (cont.),1. Main paradigms: a) Greedy algorithms b) Divide-and-Conquers c) Dynamic programming d) Brach-and-Bound (mostly in AI ) e) Etc etc.2. Other reasons: a) Relevance to many areas: E.g., networking, internet, search engines,Topics,Recursive EquationsDivide and Conquer MethodDynamic Programming MethodBasic and Advanced Data StructuresGraph AlgorithmsApproximation AlgorithmsNP-Complete TheoryRandomized Algorithms,Grade,4-5 assignments (35%)Midterm (20%)Final (25%)Exercises and Attendance for the class (20%),Advantage for a good algorithm designer,It helps you develop efficient softwareIt is easy to switch from one area to another in computer science,2.2 Analyzing AlgorithmsRAM: Random-access machine, It takes one step for accessing memory once. The instructions are executed one by one sequentiallyRunning time: the total number of steps expressed as the function of input size,The problem of sorting,Input: sequence a1, a2, , an of numbers.Output: permutation of the input numbers: Example: Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,Running time,The running time depends on the input:Parameterize the running time by the size of the input n Seek upper bounds on the running time T(n) for the input size n, because everybody likes a guarantee.,Kinds of analyses,Worst-case: (usually)T(n) = maximum time of algorithm on any input of size n.Average-case: (sometimes) T(n) = expected time of algorithm over all inputs of size n.Need assumption of statistical distribution of inputs.Best-case: (bogus)Cheat with a slow algorithm that works fast on some input.,Machine-independent time,What is insertion sorts worst-case time? It depends on the speed of our computer: relative speed (on the same machine), absolute speed (on different machines).BIG IDEA: Ignore machine-dependent constants. Look at growth of T(n) as n .“Asymptotic Analysis”,Bubble Sort Algorithm,Compare 1st two elements and exchange them if they are out of order.Move down one element and compare 2nd and 3rd elements. Exchange if necessary. Continue until end of array.Pass through array again, repeating process and exchanging as necessary.Repeat until a pass is made with no exchanges.,Bubble Sort Example,Array numlist3 contains,Bubble Sort Example,Array numlist3 contains,Bubble Sort Example,Array numlist3 contains,Bubble Sort Example (continued),After first pass, array numlist3 contains,In order from previous pass,Bubble Sort Example (continued),After second pass, array numlist3 contains,No exchanges, so array is in order,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Sorting Problem,Given a series of integers 7, 2, 5, 3, 6, 9, 8, 1 Arrange them by the increasing order: 1 2 3 5 6 7 8 9,Merge for Sorting,Convert the sorting for 7, 2, 5, 3, 6, 9, 8, 1 into 7, 2, 5, 3, and 6, 9, 8, 1 Sort 7, 2, 5, 3 into 2 3 5 7Sort 6, 9, 8, 1 into 1 6 8 9Merge 2 3 5 7 1 6 8 9 2 3 5 7 3 5 7 5 7 7 6 8 9 6 8 9 68 9 68 9 1 12 123 1235,Merge for Sorting,Merge 2 3 5 7 1 6 8 9 2 3 5 7 3 5 7 5 7 7 6 8 9 6 8 9 68 9 68 9 1 12 123 12357 89 89 12356 123567 12356781,P1,P2,Time analysis,P:T(n)=2T(n/2)+n =2(2T(n/4)+n/2)+n=4T(n/4)+n+n =4(2T(n/8)+n/4)+n+n=8T(n/8)+n+n+n = = =O(n (log n),P1,P2,Every layer costs steps Total #layers is log n. Total time is n (log n)Merge time #Nodes P 1n P1 P2 2n/2 ,Exponentiation Problem,Compute Compute,Polynomial Problem,ComputeCompute a general polynomial:,Exercise,Draw the tree for merge sorting15, 11, 4, 22, 31, 55, 71, 12, 7, 2, 5, 3, 6, 9, 8, 1Point out the number of comparison that you use.,Chapter 3-4,Growth of Functions and Recursion Equations,O-notation: f(n) = O(g(n)，g(n) is an asymptotically upper bound for f(n)。O(g(n) = f(n)| if there are positive constants c and n0 such that 0 f(n) c2 g(n) for all large n n0 ,Example: 3n2 - 6n = O(n2)。,O-notation,Drop low-order terms; ignore leading constants. Example: we say that T(n)= O( g(n) ) iffthere exists positive constants , and such that0 n0Usually T(n) is running time, and n is size of input,Simplified Master Theorem,Letbe a recursive equation on the nonnegative integers, where a 0, b 1, c0, and r=0 are constants,Then,1. If , then2. If , then3. If , then,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.,Sum,SumLet,Sum,FromSo,Sum,Assume that d is a constant.Case 1: d1. (Main term is Right region)Case 2: d=1. (Each term is same )Case 3: d1. Case 2: d=1. Case 3: d 0, b 1, c0, and r0 are constants,Then,1. If , then2. If , then3. If , then,Layers,Layer,Proof.,The number of nodes in the j-th layer isThe size of a node in the j-the layer is The cost of each node in the j-th layer isThe total cost at j-th layer is,Proof.,The number of layers is The total cost at all layers is,Proof.,The total cost at all layers is,Proof.,The total cost at all layers isWhere d is the constant,Proof.,Case 1.So,Therefore, the total cost is,Proof.,Case 2.So,Therefore, the total cost is,Proof.,Case 3.So,Therefore, the total cost is,Simplified Master Theorem,Let Then,1. If , then (The main cost is the bottom layers region) 2. If , then (Every layer has roughly the same cost)3. If , then (The main cost is the top layers region),3.1 Asymptotic notation-notation: f(n) = (g(n)，g(n) is an asymptotically tight bound for f(n)。(g(n) = f(n)| there exists constants c1，c2，and n0 such that 0 c1 g(n) f(n) c2 g(n) for all large n n0 ,Example: Prove 3n2 - 6n = (n2)。,Example: Prove 3n2 - 6n = (n2)。Proof:We need to find constants c1,，c2 and n0 such that:c1n2 3n2 - 6n c2n2，(for all nn0)Divide n2 c1 3 - 6/n c2Select c1=2，c2=3 and n0=6,Note： f(n) = (g(n) iff g(n)= (f(n)，For example: n2=(3n2-6n)O-notation: f(n) = O(g(n)，g(n) is an asymptotically upper bound for f(n)。O(g(n) = f(n)| if there are positive constants c and n0 such that 0 f(n) c2 g(n) for all large n n0 ,(g(n) O(g(n)f(n) = (g(n) implies f(n) = O(g(n)6n = O(n)，6n = O(n2)Computational time O(n2) means the time in the worst case is O(n2),-notation: f(n) = (g(n)，g(n) is an asymptotically lower bound for f(n)。(g(n) = f(n)| there are positive constants c and n0 such that 0 cg(n) f(n) for all n n0 Note： f(n) = (g(n) if and only if (f(n)=O(g(n) & (f(n)= (g(n),tight bound,upper bound,lower bound,o-notation: f(n) = o(g(n) (little-oh of g of n)o(g(n) = f(n)| for every positive constant c，there exists constant n0 0 such that 0 f(n) cg(n) for all n n0 2n = o(n2)，but 2n2 o(n2)f(n) = o(g(n) can be also written,Comparison of functionsfunctions: Oonumbers: = 0, b 1, c0, and r0 are constants,Then,1. If , then2. If , then3. If , then,Layers,Layer,Integer Multiplication,12x 47=564 by the algorithm below 12 47- 84 48- 564,Integer Multiplication,A = 1234567890135798 B = 87654321284820912The elementary school algorithm: a1 a2 an b1 b2 bn (d10) d11d12 d1n (d20) d21d22 d2n (dn0) dn1dn2 dnn Efficiency: n2 one-digit multiplications,Karatsubas Algorithm,Using the classical pen and paper algorithm two n digit integers can be multiplied in O(n2) operations. Karatsuba came up with a faster algorithm.Let A and B be two integers withA = A110k + A0, A0 10kB = B110k + B0, B0 10kC = A*B = (A110k + A0)(B110k + B0) = A1B1102k + (A1B0 + A0 B1)10k + A0B0,A trivial analysis,T(n)=4T(n/2)+O(n)T(n)=O( ),Simplified Master Theorem,Let Then,1. If , then (The main cost is the bottom layers region) 2. If , then (Every layer has roughly the same cost)3. If , then (The main cost is the top layers region),3 Multiplications,Instead this can be computed with 3 multiplicationsT0 = A0B0T1 = (A1 + A0)(B1 + B0) T2 = A1B1C = T2102k + (T1 - T0 - T2)10k + T0,Complexity of Algorithm,Let T(n) be the time to compute the product of two n-digit numbers using Karatsubas algorithm. Assume n = 2k. T(n) = (nlg(3), lg(3) 1.58T(n) 3T(n/2) + cn,Matrix Multiplication,Regular method takes time O(n*n*n),IDEA: r s a b e f = x t u c d g hr =ae+bgs =af +bht =ce+dgu =cf +dh,Strassens algorithm,Multiply 22 matrices with only 7 recursive mults.P1 = a ( f h)P2 = (a + b) hP3 = (c + d) eP4 = d (g e)P5 = (a + d) (e + h)P6 = (b d) (g + h)P7 = (a c) (e + f ),Strassens Algorithm,r = P5 + P4 P2 + P6s = P1 + P2t = P3 + P4u = P5 + P1 P3 P7,Problem,Verify one of the four equations in the Strassens algorithm: u =P5 + P1 P3 P7,Strassen observed 1969 that the product of two matrices can be computed as follows:C00 C01 A00 A01 B00 B01 = *C10 C11 A10 A11 B10 B11 M1 + M4 - M5 + M7 M3 + M5 = M2 + M4 M1 + M3 - M2 + M6,M1 = (A00 + A11) (B00 + B11)M2 = (A10 + A11) B00M3 = A00 (B01 - B11)M4 = A11 (B10 - B00)M5 = (A00 + A01) B11M6 = (A10 - A00) (B00 + B01)M7 = (A01 - A11) (B10 + B11),Analysis of Strassens Algorithm,If n is not a power of 2, matrices can be padded with zeros.Number of multiplications: T(n) = 7T(n/2)+O( ), T(1) = 1Solution: T(n) = nlog 27 n2.807 vs. n3 of brute-force alg.,Problem,Verify two of the four equations in the Strassens algorithm: t = P3 + P4 andu =P5 + P1 P3 P7,Heap,3 7 5 10 11 6Father= childrenThe root is the smallestPerfect binary tree,Heap,3 7 5 10 11 6Father= childrenThe root is the smallestPerfect binary tree (every layer except the bottom is filled up),Heap Operations,Insertion Deletion: Remove root (take the least),Heap Insertion,3 7 5 10 11 6 1,Insertion Adjustment,3 7 1 10 11 6 5Adjust it on the path from new leaf to root,Heap Insertion,1 7 3 10 11 6 5Except new leaf, all adjusted nodes get smaller valuesInsertion does not damage the heap,Deletion (Remove Root),7 3 10 11 6 5,Deletion Adjustment,5 7 3 10 11 6 Take the last leaf to the rootAdjust on the path from root to a leaf,Deletion Adjustment,3 7 5 10 11 6 Deletion does not damage heap,Heap Representation,A heap with no more than n elements uses array h of size n.The children of hi is h2i and h2i+1The hi/2 is the father of hi,Heap Representation,A heap with no more than n elements uses array h of size n.Prove By Induction:lefti=2irighti=2i+1father(i)=i/2,Adjustment for Insertion,Bottom-Up-Adjust(i) if (hihchild) swap between hi and hchild; Top-Down-Adjust(child) ,Delete,Delete(heapsize) move hheapsize to h1; Top-Down-Adjust(1);,Complexity of Heap Operations,A heap has n elements. The depth of heap is O(log n)Insertions takes O(log n) stepsDeletion takes O(log n) steps,Heap Sorting,Input: a1, a2, , anBuild Heap: n insertions Cost: O(nlog n)Remove from heap: n deletions Cost: O(nlog n)Total cost: O(nlog n),ATM Traffic Shaping,Incoming,vc1 queue,vc2 queue,vc3 queue,vcn queue,scheduler,Outgoing,Tele-communication,Phones PhonesEach vc is considered as one phone connection,Gateway,Switch,Traffic in one virtual circuit,Incoming packets:Outgoing packets after shaping:Time:,p1,p2,p3,p4,p5,p6,p7,p1,p2,p3,p4,p5,p7,p6,Interval Packet Delay,Inter packet time gap is big enoughEvery virtual circuit i has minimal inter delay const inter_delay_i inter_delay_itime,Packet 3,Packet 4,A Trivial Algorithm,After a packet in one vc, set the ready time for sending the next packet : ready_time=current_time+inter_delayPeriodic