مبانی ساختمان داده ها و الگوریتم ها ۲

مبانی ساختمان داده ها و الگوریتم ها ۲

اسلاید 1: 0CS 130 A: Data Structures and AlgorithmsFocus of the course:Data structures and related algorithmsCorrectness and (time and space) complexityPrerequisitesCS 20: stacks, queues, lists, binary search trees, … CS 40: functions, recurrence equations, induction, …CS 60: C, C++, and UNIX

اسلاید 2: 1Course OrganizationGrading:See course web pagePolicy:No late homeworks.Cheating and plagiaris: F grade and disciplinary actionsOnline info: Homepage: www.cs.ucsb.edu/~cs130aEmail: cs130a@cs.ucsb.edu Teaching assistants: See course web page

اسلاید 3: 2IntroductionA famous quote: Program = Algorithm + Data Structure.All of you have programmed; thus have already been exposed to algorithms and data structure. Perhaps you didnt see them as separate entities;Perhaps you saw data structures as simple programming constructs (provided by STL--standard template library). However, data structures are quite distinct from algorithms, and very important in their own right.

اسلاید 4: 3ObjectivesThe main focus of this course is to introduce you to a systematic study of algorithms and data structure. The two guiding principles of the course are: abstraction and formal analysis.Abstraction: We focus on topics that are broadly applicable to a variety of problems.Analysis: We want a formal way to compare two objects (data structures or algorithms). In particular, we will worry about always correct-ness, and worst-case bounds on time and memory (space).

اسلاید 5: 4TextbookTextbook for the course is: Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss But I will use material from other books and research papers, so the ultimate source should be my lectures.

اسلاید 6: 5Course OutlineC++ Review (Ch. 1)Algorithm Analysis (Ch. 2)Sets with insert/delete/member: Hashing (Ch. 5) Sets in general: Balanced search trees (Ch. 4 and 12.2)Sets with priority: Heaps, priority queues (Ch. 6)Graphs: Shortest-path algorithms (Ch. 9.1 – 9.3.2)Sets with disjoint union: Union/find trees (Ch. 8.1–8.5)Graphs: Minimum spanning trees (Ch. 9.5)Sorting (Ch. 7)

اسلاید 7: 6130a: Algorithm Analysis Foundations of Algorithm Analysis and Data Structures. Analysis:How to predict an algorithm’s performance How well an algorithm scales upHow to compare different algorithms for a problemData StructuresHow to efficiently store, access, manage data Data structures effect algorithm’s performance

اسلاید 8: 7Example AlgorithmsTwo algorithms for computing the Factorial Which one is better?int factorial (int n) { if (n <= 1) return 1; else return n * factorial(n-1);}int factorial (int n) { if (n<=1) return 1; else { fact = 1; for (k=2; k<=n; k++) fact *= k; return fact; }}

اسلاید 9: 8Examples of famous algorithmsConstructions of EuclidNewtons root findingFast Fourier TransformCompression (Huffman, Lempel-Ziv, GIF, MPEG)DES, RSA encryptionSimplex algorithm for linear programmingShortest Path Algorithms (Dijkstra, Bellman-Ford)Error correcting codes (CDs, DVDs)TCP congestion control, IP routingPattern matching (Genomics)Search Engines

اسلاید 10: 9Role of Algorithms in Modern WorldEnormous amount of data E-commerce (Amazon, Ebay)Network traffic (telecom billing, monitoring)Database transactions (Sales, inventory)Scientific measurements (astrophysics, geology)Sensor networks. RFID tagsBioinformatics (genome, protein bank)Amazon hired first Chief Algorithms Officer (Udi Manber)

اسلاید 11: 10A real-world ProblemCommunication in the InternetMessage (email, ftp) broken down into IP packets.Sender/receiver identified by IP address.The packets are routed through the Internet by special computers called Routers.Each packet is stamped with its destination address, but not the route.Because the Internet topology and network load is constantly changing, routers must discover routes dynamically.What should the Routing Table look like?

اسلاید 12: 11IP Prefixes and RoutingEach router is really a switch: it receives packets at several input ports, and appropriately sends them out to output ports.Thus, for each packet, the router needs to transfer the packet to that output port that gets it closer to its destination.Should each router keep a table: IP address x Output Port?How big is this table?When a link or router fails, how much information would need to be modified?A router typically forwards several million packets/sec!

اسلاید 13: 12Data StructuresThe IP packet forwarding is a Data Structure problem!Efficiency, scalability is very important.Similarly, how does Google find the documents matching your query so fast?Uses sophisticated algorithms to create index structures, which are just data structures.Algorithms and data structures are ubiquitous.With the data glut created by the new technologies, the need to organize, search, and update MASSIVE amounts of information FAST is more severe than ever before.

اسلاید 14: 13Algorithms to Process these DataWhich are the top K sellers?Correlation between time spent at a web site and purchase amount?Which flows at a router account for > 1% traffic?Did source S send a packet in last s seconds?Send an alarm if any international arrival matches a profile in the databaseSimilarity matches against genome databasesEtc.

اسلاید 15: 14Max Subsequence ProblemGiven a sequence of integers A1, A2, …, An, find the maximum possible value of a subsequence Ai, …, Aj.Numbers can be negative.You want a contiguous chunk with largest sum.Example: -2, 11, -4, 13, -5, -2The answer is 20 (subseq. A2 through A4).We will discuss 4 different algorithms, with time complexities O(n3), O(n2), O(n log n), and O(n).With n = 106, algorithm 1 may take > 10 years; algorithm 4 will take a fraction of a second!

اسلاید 16: 15int maxSum = 0;for( int i = 0; i < a.size( ); i++ )for( int j = i; j < a.size( ); j++ ){int thisSum = 0;for( int k = i; k <= j; k++ )thisSum += a[ k ];if( thisSum > maxSum )maxSum = thisSum;}return maxSum;Algorithm 1 for Max Subsequence SumGiven A1,…,An , find the maximum value of Ai+Ai+1+···+Aj0 if the max value is negative Time complexity: O(n3)

اسلاید 17: 16Algorithm 2Idea: Given sum from i to j-1, we can compute the sum from i to j in constant time. This eliminates one nested loop, and reduces the running time to O(n2).into maxSum = 0;for( int i = 0; i < a.size( ); i++ )int thisSum = 0;for( int j = i; j < a.size( ); j++ ){ thisSum += a[ j ]; if( thisSum > maxSum ) maxSum = thisSum;}return maxSum;

اسلاید 18: 17Algorithm 3This algorithm uses divide-and-conquer paradigm.Suppose we split the input sequence at midpoint.The max subsequence is entirely in the left half, entirely in the right half, or it straddles the midpoint.Example:left half |right half4 -3 5 -2 | -1 2 6 -2 Max in left is 6 (A1 through A3); max in right is 8 (A6 through A7). But straddling max is 11 (A1 thru A7).

اسلاید 19: 18Algorithm 3 (cont.)Example:left half |right half4 -3 5 -2 | -1 2 6 -2Max subsequences in each half found by recursion.How do we find the straddling max subsequence?Key Observation: Left half of the straddling sequence is the max subsequence ending with -2.Right half is the max subsequence beginning with -1.A linear scan lets us compute these in O(n) time.

اسلاید 20: 19Algorithm 3: AnalysisThe divide and conquer is best analyzed through recurrence:T(1) = 1T(n) = 2T(n/2) + O(n)This recurrence solves to T(n) = O(n log n).

اسلاید 21: 20Algorithm 4Time complexity clearly O(n)But why does it work? I.e. proof of correctness.2, 3, -2, 1, -5, 4, 1, -3, 4, -1, 2int maxSum = 0, thisSum = 0;for( int j = 0; j < a.size( ); j++ ){thisSum += a[ j ];if ( thisSum > maxSum )maxSum = thisSum;else if ( thisSum < 0 )thisSum = 0;}return maxSum;}

اسلاید 22: 21Proof of CorrectnessMax subsequence cannot start or end at a negative Ai.More generally, the max subsequence cannot have a prefix with a negative sum. Ex: -2 11 -4 13 -5 -2Thus, if we ever find that Ai through Aj sums to < 0, then we can advance i to j+1Proof. Suppose j is the first index after i when the sum becomes < 0The max subsequence cannot start at any p between i and j. Because Ai through Ap-1 is positive, so starting at i would have been even better.

اسلاید 23: 22Algorithm 4int maxSum = 0, thisSum = 0;for( int j = 0; j < a.size( ); j++ ){thisSum += a[ j ];if ( thisSum > maxSum )maxSum = thisSum;else if ( thisSum < 0 )thisSum = 0;}return maxSum The algorithm resets whenever prefix is < 0. Otherwise, it forms new sums and updates maxSum in one pass.

اسلاید 24: 23Why Efficient Algorithms MatterSuppose N = 106A PC can read/process N records in 1 sec.But if some algorithm does N*N computation, then it takes 1M seconds = 11 days!!!100 City Traveling Salesman Problem. A supercomputer checking 100 billion tours/sec still requires 10100 years! Fast factoring algorithms can break encryption schemes. Algorithms research determines what is safe code length. (> 100 digits)

اسلاید 25: 24How to Measure Algorithm Performance What metric should be used to judge algorithms?Length of the program (lines of code)Ease of programming (bugs, maintenance)Memory requiredRunning timeRunning time is the dominant standard.Quantifiable and easy to compareOften the critical bottleneck

اسلاید 26: 25AbstractionAn algorithm may run differently depending on:the hardware platform (PC, Cray, Sun)the programming language (C, Java, C++)the programmer (you, me, Bill Joy)While different in detail, all hardware and prog models are equivalent in some sense: Turing machines. It suffices to count basic operations.Crude but valuable measure of algorithm’s performance as a function of input size.

اسلاید 27: 26Average, Best, and Worst-CaseOn which input instances should the algorithm’s performance be judged?Average case:Real world distributions difficult to predictBest case:Seems unrealistic Worst case:Gives an absolute guaranteeWe will use the worst-case measure.

اسلاید 28: 27ExamplesVector addition Z = A+Bfor (int i=0; i<n; i++)Z[i] = A[i] + B[i];T(n) = c nVector (inner) multiplication z =A*Bz = 0;for (int i=0; i<n; i++)z = z + A[i]*B[i];T(n) = c’ + c1 n

اسلاید 29: 28ExamplesVector (outer) multiplication Z = A*BTfor (int i=0; i<n; i++) for (int j=0; j<n; j++) Z[i,j] = A[i] * B[j];T(n) = c2 n2;A program does all the above T(n) = c0 + c1 n + c2 n2;

اسلاید 30: 29Simplifying the BoundT(n) = ck nk + ck-1 nk-1 + ck-2 nk-2 + … + c1 n + cotoo complicatedtoo many termsDifficult to compare two expressions, each with 10 or 20 terms Do we really need that many terms?

اسلاید 31: 30SimplificationsKeep just one term! the fastest growing term (dominates the runtime)No constant coefficients are keptConstant coefficients affected by machines, languages, etc.Asymtotic behavior (as n gets large) is determined entirely by the leading term.Example. T(n) = 10 n3 + n2 + 40n + 800If n = 1,000, then T(n) = 10,001,040,800error is 0.01% if we drop all but the n3 termIn an assembly line the slowest worker determines the throughput rate

اسلاید 32: 31SimplificationDrop the constant coefficientDoes not effect the relative order

اسلاید 33: 32SimplificationThe faster growing term (such as 2n) eventually will outgrow the slower growing terms (e.g., 1000 n) no matter what their coefficients! Put another way, given a certain increase in allocated time, a higher order algorithm will not reap the benefit by solving much larger problem

اسلاید 34: 33Complexity and Tractability Assume the computer does 1 billion ops per sec.

اسلاید 35: 342nn2n log nnlog nlog nnn log nn2n3n32n

اسلاید 36: 35Another ViewMore resources (time and/or processing power) translate into large problems solved if complexity is lowT(n)Problem size solved in 103 secProblem size solved in 104 secIncrease in Problem size100n10100101000n110105n214453.2N310222.22n10131.3

اسلاید 37: 36AsympoticsThey all have the same “growth” rate

اسلاید 38: 37CaveatsFollow the spirit, not the lettera 100n algorithm is more expensive than n2 algorithm when n < 100Other considerations:a program used only a few times a program run on small data setsease of coding, porting, maintenance memory requirements

اسلاید 39: 38Asymptotic NotationsBig-O, “bounded above by”: T(n) = O(f(n))For some c and N, T(n)  c·f(n) whenever n > N.Big-Omega, “bounded below by”: T(n) = W(f(n))For some c>0 and N, T(n)  c·f(n) whenever n > N.Same as f(n) = O(T(n)).Big-Theta, “bounded above and below”: T(n) = Q(f(n))T(n) = O(f(n)) and also T(n) = W(f(n))Little-o, “strictly bounded above”: T(n) = o(f(n))T(n)/f(n)  0 as n  

اسلاید 40: 39By PicturesBig-Oh (most commonly used)bounded above Big-Omega bounded belowBig-Thetaexactly Small-onot as expensive as ...

اسلاید 41: 40Example

اسلاید 42: 41Examples

اسلاید 43: 42Summary (Why O(n)?)T(n) = ck nk + ck-1 nk-1 + ck-2 nk-2 + … + c1 n + coToo complicatedO(nk )a single term with constant coefficient droppedMuch simpler, extra terms and coefficients do not matter asymptoticallyOther criteria hard to quantify

اسلاید 44: 43Runtime AnalysisUseful rulessimple statements (read, write, assign)O(1) (constant)simple operations (+ - * / == > >= < <= O(1)sequence of simple statements/operationsrule of sumsfor, do, while loopsrules of products

اسلاید 45: 44Runtime Analysis (cont.)Two important rulesRule of sums if you do a number of operations in sequence, the runtime is dominated by the most expensive operation Rule of productsif you repeat an operation a number of times, the total runtime is the runtime of the operation multiplied by the iteration count

اسلاید 46: 45Runtime Analysis (cont.)if (cond) then O(1)body1 T1(n)elsebody2 T2(n)endifT(n) = O(max (T1(n), T2(n))

اسلاید 47: 46Runtime Analysis (cont.)Method callsA calls BB calls Cetc.A sequence of operations when call sequences are flattenedT(n) = max(TA(n), TB(n), TC(n))

اسلاید 48: 47Examplefor (i=1; i<n; i++)if A(i) > maxVal thenmaxVal= A(i);maxPos= i;Asymptotic Complexity: O(n)

اسلاید 49: 48Examplefor (i=1; i<n-1; i++)for (j=n; j>= i+1; j--)if (A(j-1) > A(j)) thentemp = A(j-1);A(j-1) = A(j);A(j) = tmp;endifendforendforAsymptotic Complexity is O(n2)

اسلاید 50: 49Run Time for Recursive ProgramsT(n) is defined recursively in terms of T(k), k<nThe recurrence relations allow T(n) to be “unwound” recursively into some base cases (e.g., T(0) or T(1)). Examples:FactorialHanoi towers

اسلاید 51: 50Example: Factorial int factorial (int n) { if (n<=1) return 1; else return n * factorial(n-1);}factorial (n) = n*n-1*n-2* … *1n * factorial(n-1) n-1 * factorial(n-2) n-2 * factorial(n-3) … 2 *factorial(1) T(n)T(n-1)T(n-2)T(1)

اسلاید 52: 51Example: Factorial (cont.)int factorial1(int n) { if (n<=1) return 1; else { fact = 1; for (k=2;k<=n;k++) fact *= k; return fact; }}Both algorithms are O(n).

اسلاید 53: 52Example: Hanoi TowersHanoi(n,A,B,C) = Hanoi(n-1,A,C,B)+Hanoi(1,A,B,C)+Hanoi(n-1,C,B,A)

اسلاید 54: 53 // Early-terminating version of selection sort bool sorted = false; !sorted && sorted = true; else sorted = false; // out of orderWorst CaseBest Casetemplate<class T>void SelectionSort(T a[], int n){ for (int size=n; (size>1); size--) { int pos = 0; // find largest for (int i = 1; i < size; i++) if (a[pos] <= a[i]) pos = i; Swap(a[pos], a[size - 1]); }}Worst Case, Best Case, and Average Case

اسلاید 55: 54T(N)=6N+4 : n0=4 and c=7, f(N)=NT(N)=6N+4 <= c f(N) = 7N for N>=47N+4 = O(N)15N+20 = O(N)N2=O(N)?N log N = O(N)?N log N = O(N2)?N2 = O(N log N)?N10 = O(2N)?6N + 4 = W(N) ? 7N? N+4 ? N2? N log N?N log N = W(N2)?3 = O(1)1000000=O(1)Sum i = O(N)?T(N)f(N)c f(N)n0T(N)=O(f(N))

اسلاید 56: 55An Analogy: Cooking RecipesAlgorithms are detailed and precise instructions.Example: bake a chocolate mousse cake.Convert raw ingredients into processed output.Hardware (PC, supercomputer vs. oven, stove)Pots, pans, pantry are data structures.Interplay of hardware and algorithms Different recipes for oven, stove, microwave etc. New advances.New models: clusters, Internet, workstationsMicrowave cooking, 5-minute recipes, refrigeratio