PowerPoint PresentationClip Art SourcesWhat The Course Is AboutSlide 4PrerequisitesWeb SiteAssignments, Tests, & GradesGrades (Rough Cutoffs)Kinds Of ComplexityQuick SortSlide 11Slide 12Task SequenceSlide 14Slide 15Amortized ComplexitySlide 17Slide 18Slide 19Potential FunctionArithmetic StatementsSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Complexity Of processNextSymbolOverall Complexity (Conventional Analysis)Ways To Determine Amortized ComplexityAggregate MethodSlide 32Slide 33Slide 34Advanced Data StructuresSartaj SahniClip Art Sources•www.barrysclipart.com•www.livinggraphics.com•www.rad.kumc.edu•www.livinggraphics.comWhat The Course Is About•Study data structures for:External sortingSingle and double ended priority queuesDictionariesMultidimensional searchComputational geometryImage processingPacket routing and classificationWhat The Course Is About•Concerned with:Worst-case complexityAverage complexityAmortized complexityPrerequisitesAsymptotic ComplexityBig Oh, Theta, and Omega notationsUndergraduate data structuresStacks and QueuesLinked listsTreesGraphsC++ (reading knowledge at least)Web Sitewww.cise.ufl.edu/~sahni/cop5536My office data.Handouts, syllabus, text, readings, assignments, past exams, past exam solutions, TAs, Internet lectures, PowerPoint presentations, etc.Assignments, Tests, & Grades•25% for assignmentsThere will be three assignments.•25% for each testThere will be three tests.Grades (Rough Cutoffs)•A >= 82%•B+ >= 75%•B >= 70%•C+ >= 65%•C >= 60%Kinds Of ComplexityWorst-case complexity.Average complexity.•Amortized complexity.Quick Sort•Sort n distinct numbers.•Worst-case time is (say) 10n2 microseconds on some computer.•This means that for every n, there is a sequence of n numbers for which quick sort will take 10n2 microseconds to complete.•Also, there is no sequence of n numbers for which quick sort will take more than 10n2 microseconds to complete.Quick Sort•Average time is (say) 5n log2n microseconds on some computer.•Consider any n, say n = 1000.•Add up the time taken to sort each of the 1000! possible 1000 element sequences.•Divide by 1000!.•The result is 5000 log21000.Quick Sort•What if we sort only 500 of these 1000! sequences?•We can only conclude that the total time for these 500 sequences will be <= 500*(worst-case time) = 500*(10n2)•We cannot conclude that the time will be 500*(average time).Task Sequence•Suppose that a sequence of n tasks is performed.•The worst-case cost of a task is cwc.•Let ci be the (actual) cost of the ith task in this sequence.•So, ci <= cwc, 1 <= i <= n.•n * cwc is an upper bound on the cost of the sequence.•j * cwc is an upper bound on the cost of the first j tasks.Task Sequence•Let cavg be the average cost of a task in this sequence.•So, cavg = ci/n.•n * cavg is the cost of the sequence.•j * cavg is not an upper bound on the cost of the first j tasks.•Usually, determining cavg is quite hard.Task Sequence•At times, a better upper bound than j * cwc or n * cwc on sequence cost is obtained using amortized complexity.Amortized Complexity•The amortized complexity of a task is the amount you charge the task.•The conventional way to bound the cost of doing a task n times is to use one of the expressions  n*(worst-case cost of task)worst-case costof task i•The amortized complexity way to bound the cost of doing a task n times is to use one of the expressionsn*(amortized cost of task)amortized cost of task iAmortized Complexity•The amortized complexity/cost of individual tasks in any task sequence must satisfy:actual costof task i  amortized cost of task i•So, we can use  amortized cost of task i as a bound on the actual complexity of the task sequence.Amortized Complexity•The amortized complexity of a task may bear no direct relationship to the actual complexity of the task.Amortized Complexity•In conventional complexity analysis, each task is charged an amount that is >= its cost.actual cost of task iworst-case cost of task i)•In amortized analysis, some tasks may be charged an amount that is < their cost.actual cost of task iamortized cost of task i)Potential Function•P(i) = amortizedCost(i) – actualCost(i) + P(i – 1)• (P(i) – P(i–1)) = (amortizedCost(i) –actualCost(i))•P(n) – P(0) = (amortizedCost(i) –actualCost(i))•P(n) – P(0) >= 0•When P(0) = 0, P(i) is the amount by which the first i tasks/operations have been over charged.Arithmetic Statements•Rewrite an arithmetic statement as a sequence of statements without using parentheses.•a = x+((a+b)*c+d)+y; is equivalent to the sequence: z1 = a+b; z2 = z1*c+d; a = x+z2+y;Arithmetic Statements•The rewriting is done using a stack and a method processNextSymbol.•create an empty stack; for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol();a = x+((a+b)*c+d)+y;Arithmetic Statements•processNextSymbol extracts the next symbol from the input statement.•Symbols other than ) and ; are simply pushed on to the stack.a = x+((a+b)*c+d)+y; a=x+((a+bArithmetic Statements•If the next symbol is ), symbols are popped from the stack up to and including the first (, an assignment statement is generated, and the left hand symbol is added to the stack.a = x+((a+b)*c+d)+y; a=x+((a+bz1 = a+b;Arithmetic Statementsa = x+((a+b)*c+d)+y; a=x+(z1z1 = a+b;*c+dz2 = z1*c+d;•If the next symbol is ), symbols are popped from the stack up to and including the first (, an assignment statement is generated, and the left hand symbol is added to the stack.Arithmetic Statementsa = x+((a+b)*c+d)+y; a=x+z2z1 = a+b;z2 = z1*c+d;+y•If the next symbol is ), symbols are popped from the stack up to and including the first (, an assignment statement is generated, and the left hand symbol is added to the stack.Arithmetic Statements•If the next symbol is ;, symbols are popped from the stack until the stack becomes empty. The final assignment statement a = x+z2+y; is generated.a = x+((a+b)*c+d)+y;z1 = a+b; a=x+z2+yz2 = z1*c+d;Complexity Of processNextSymbol•O(number of symbols that get popped from stack)•O(i), where i is for loop index.a = x+((a+b)*c+d)+y;Overall Complexity (Conventional