CS 61B Data Structures and Programming Methodology Programming Methodology July 14, 2008David SunAnnouncement• Project 1 Due Tomorrow at 11:00a.m.• Due to technical problems, for HW1 everyone will get credit.Today• More on asymptotic analysisAnalysis Example 1• Problem 1– Given a set of p points, find the pair closest to each other.• Algorithm 1: – Calculate the distance between each pair; return the minimum.doubleminDistance =point[0].distance(point[1]);/*Visitapair(i,j)ofpoints.*//*Visitapair(i,j)ofpoints.*/for(int i =0;i <point.length;i++){for(int j=i +1;j<point.length;j++){doublethisDistance = point[i].distance(point[j]);if(thisDistance <minDistance){minDistance =thisDistance;}}}• There are p (p - 1) / 2 pairs, and each pair takes constant time to examine. Therefore, worst- and best-case running times are in Ѳ(p2).Iterates p timesIterates p/2 times on averageAnalysis Example 2• Problem 2: – remove consecutive duplicates from an ints array of length N• Algorithm 2: int i =0,j=0;while(i <ints.length){ints[j]=ints[i];do{i++;Iterates up to p times, Iterates up to p times i++;}while((i <ints.length)&&(ints[i]==ints[j]));j++;}• Although we have a nest loop the running-time is not Ѳ(N2). Why?• The outer loop can iterate up to ints.length times, and so can the inner loop. But the index i advances on every iteration of the inner loop. It can't advance more than ints.length times before both loops end. • So the worst-case running time of this algorithm is Ѳ(N) time. Iterates up to p timesAnalysis Example 3• Problem 3– Given 2 strings, tests if the second string is a substring of the first.• Algorithm 3:boolean occurs(StringS,StringX){if(S.equals (X))returntrue;if(S.length ()<=X.length ())returnfalse;returnoccurs(S.substring (1),X)||occurs(S.substring(0,S.length()-1),X);occurs(S.substring(0,S.length()-1),X);}• What’s the best case? • What’s the worst case? • What’s the complexity of the worst case?• Consider a fixed size of N, N0Let C(N) be the worst-case cost of the algorithm. • C(N) grows exponentiallyAlgorithm 4• Problem 4– Finds if a String is in a sorted array of Strings.• Algorithm 3:boolean isIn (StringX,String[]S,int L,int U){if(L>U)returnfalse;int M=(L+U)/2;int direct=X.compareTo (S[M]);if(direct<0)returnisIn (X,S,L,M-1);elseif(direct>0)returnisIn (X,S,M+1,U);elsereturntrue;}• Consider a fixed size of D. Let C(D) be the worst-case cost of the algorithm• The problem size is cut by half each time.Functions of Several VariablesAnalysis Example 5• Problem 5: – A matchmaking program for w women and m men. • Algorithm 5: – Compare each woman with each man. Decide if they're compatible. • Suppose each comparison takes constant time then the running time, T(w, m), is in Ѳ(wm). running time, T(w, m), is in Ѳ(wm). – There exist constants c, d, W, and M, such that: d wm ≤ T(w, m) ≤ c wm for every w ≥ W and m ≥ M. • T(w, m) is NOT in O(w2), nor in O(m2), nor in Ω(w2), nor in Ω(m2). • Every one of these possibilities is eliminated either by choosing w >> m or m >> w. Conversely, w2is in neither O(wm) nor Ω(wm).Analysis Example 6• Problem 6: – Suppose you have an array containing n music albums, sorted by title. You request a list of all albums whose titles begin with "The Best of"; suppose there are k such albums. • Algorithm 6: Search for the first matching album with binary search. Walk (in both directions) to find the other matching albums. •Worst case:log n k•Worst case:– Binary search: log n steps.– The complete list of k matching albums is found, each in constant time. Thus, the worst-case running time is in Ѳ(log n + k). • Can we simplify?– Because k can be as large as n, it is not dominated by the log n term.– Because k can be as small as 0 , it does not dominate the log n term.– Hence, there is no simpler expression.– The algorithm is output-sensitive, because the running time depends partly on the size k of the output.• Best case: – Finds a match right away, Ѳ (1+ k) = Ѳ(k).Analysis Example 7• Problem 7: Find the k-th item in an n-node doubly-linked list. • Algorithm 7: If k < 1 or k > n, report an error and return.Otherwise, compare k with n-k.If k <= n-kstart at the beginning of the list and walk forward k-1 nodes.start at the beginning of the list and walk forward k-1 nodes.Otherwisestart at the end of the list and walk backward n-k nodes.• If 1 ≤ k ≤ n, this algorithm takes Ѳ(min{k, n-k}) time (in all cases) • This expression cannot be simplified: without knowing kand n, we cannot say that k dominates n-k or that n-kdominates k.Some Intuition• How big a problem can you solve in a given
View Full Document
Unlocking...