ColorTitleWhat is an Adversary?Important RestrictionMax and MinWhen comparing x and yAccumulating InformationResultsLargest and Second LargestSecond Largest: AdversaryWhen x is compared to yAccumulation of WeightResultsBlack and WhiteTitleWhat is an Adversary?Important RestrictionMax and MinWhen comparing x and yAccumulating InformationResultsLargest and Second LargestSecond Largest: AdversaryWhen x is compared to yAccumulation of WeightResultsAdversary ArgumentsA method for obtaining lowerA method for obtaining lowerboundsboundsWhat is an Adversary?nnA Second Algorithm Which InterceptsA Second Algorithm Which InterceptsAccess to Data StructuresAccess to Data StructuresnnConstructs the input data only asConstructs the input data only asneededneedednnAttempts to make original algorithmAttempts to make original algorithmwork as hard as possiblework as hard as possiblennAnalyze Adversary to obtain lowerAnalyze Adversary to obtain lowerboundboundImportant RestrictionnnAlthough data is created dynamically, itAlthough data is created dynamically, itmust return consistent results.must return consistent results.nnIf it replies that x[1]<x[2], it can neverIf it replies that x[1]<x[2], it can neversay later that x[2]<x[1].say later that x[2]<x[1].Max and MinnnKeep values and status codes for allKeep values and status codes for allkeyskeysnnCodes:Codes:N-never usedN-never usedW-won once but never lostW-won once but never lostL-lost once but never wonL-lost once but never wonWL-won and lost at least onceWL-won and lost at least oncennKey values will be arranged to makeKey values will be arranged to makeanswers to come out rightanswers to come out rightWhen comparing x and yStatusStatusResponseResponseNewStatNewStatInfoInfoN,NN,Nx>yx>yW,LW,L22W,NW,Nx>yx>yW,LW,L11WL,NWL,Nx>yx>yWL,LWL,L11L,NL,Nx<yx<yL,WL,W11W,WW,Wx>yx>yW,WLW,WL11L,LL,Lx>yx>yWL,LWL,L11W,L; WL,L; W,WL x>yW,L; WL,L; W,WL x>yN/CN/C00L,W; L,WL; WL,W x<yL,W; L,WL; WL,W x<yN/CN/C00WL,WLWL,WLConsistentConsistentN/CN/C00Accumulating Informationnn2n-2 bits of information are required to2n-2 bits of information are required tosolve the problemsolve the problemnnAll keys except one must lose, all keysAll keys except one must lose, all keysexcept one must winexcept one must winnnComparing N,N pairs gives n/2Comparing N,N pairs gives n/2comparisons and n bits of infocomparisons and n bits of infonnn-2 additional bits are requiredn-2 additional bits are requirednnone comparison each is neededone comparison each is neededResultsnn3n/2-2 comparisons are needed3n/2-2 comparisons are needed(This is a lower bound.)(This is a lower bound.)nnUpper bound is given by the followingUpper bound is given by the following––Compare elements pairwise, put losers inCompare elements pairwise, put losers inone pile, winners in another pileone pile, winners in another pile––Find max of winners, min of losersFind max of winners, min of losers––This gives 3n/2-2 comparisonsThis gives 3n/2-2 comparisonsnnThe algorithm is optimalThe algorithm is optimalLargest and Second LargestnnSecond Largest must have lost toSecond Largest must have lost tolargestlargestnnSecond Largest is Max of thoseSecond Largest is Max of thosecompared to largestcompared to largestnnTournament method gives n-1+lg nTournament method gives n-1+lg ncomparisons for finding largest andcomparisons for finding largest andsecond largestsecond largestSecond Largest: AdversarynnAll keys are assigned weights w[i]All keys are assigned weights w[i]nnWeights are all initialized to 1Weights are all initialized to 1nnAdversary replies are based on weightsAdversary replies are based on weightsWhen x is compared to yWeightsWeightsReplyReplyChangesChangesw[x]>w[y]w[x]>w[y]x>yx>yw[x]:=w[x]+w[y]; w[y]:=0;w[x]:=w[x]+w[y]; w[y]:=0;w[x]=w[y]>0w[x]=w[y]>0x>yx>yw[x]:=w[x]+w[y]; w[y]:=0;w[x]:=w[x]+w[y]; w[y]:=0;w[y]>w[x]w[y]>w[x]y>xy>xw[y]:=w[y]+w[x]; w[x]:=0;w[y]:=w[y]+w[x]; w[x]:=0;w[x]=w[y]=0w[x]=w[y]=0ConsistentConsistentNoneNoneAccumulation of WeightnnSolution of the problem requires allSolution of the problem requires allweight to be accumulated with one keyweight to be accumulated with one keynnAll other keys must have weight zeroAll other keys must have weight zeronnSince weight accumulates to highestSince weight accumulates to highestweight, weight can at most double withweight, weight can at most double witheach comparisoneach comparisonnnlg n comparisons are required tolg n comparisons are required toaccumulate all weightaccumulate all weightResultsnnThe largest key must be compared withThe largest key must be compared withlg n other keyslg n other keysnnFinding the second largest requires atFinding the second largest requires atleast lg n comparisons after finding theleast lg n comparisons after finding thelargestlargestnnThis is a lower boundThis is a lower boundnnThe tournament algorithm is optimalThe tournament algorithm is optimalAdversary ArgumentsA method for obtaining lowerboundsWhat is an Adversary?n A Second Algorithm Which InterceptsAccess to Data Structuresn Constructs the input data only asneededn Attempts to make original algorithmwork as hard as possiblen Analyze Adversary to obtain lowerboundImportant Restrictionn Although data is created dynamically, itmust return consistent results.n If it replies that x[1]<x[2], it can neversay later that x[2]<x[1].Max and Minn Keep values and status codes for allkeysn Codes: N-never usedW-won once but never lostL-lost once but never wonWL-won and lost at least oncen Key values will be arranged to makeanswers to come out rightWhen comparing x and yStatus Response NewStat InfoN,N x>y W,L 2W,N x>y W,L 1WL,N x>y WL,L 1L,N x<y L,W 1W,W x>y W,WL 1L,L x>y WL,L 1W,L; WL,L; W,WL x>y N/C 0L,W; L,WL; WL,W x<y N/C 0WL,WL Consistent N/C 0Accumulating Informationn 2n-2 bits of information are required tosolve the problemn All keys except one must lose, all keysexcept one must winn Comparing N,N pairs gives n/2comparisons and n bits of infon n-2 additional bits are requiredn one comparison each is neededResultsn 3n/2-2 comparisons are needed(This is a lower bound.)n Upper bound is given by the following– Compare elements pairwise, put losers inone pile, winners in another pile– Find max of winners, min of losers– This gives 3n/2-2 comparisonsn The algorithm is optimalLargest and Second Largestn Second Largest must have lost tolargestn Second Largest is Max of thosecompared to largestn Tournament method gives n-1+lg ncomparisons for