CPS 1006.1Analyzing Algorithms Consider three solutions to SortByFreqs, also code used inAnagram assignment Sort, then scan looking for changes Insert into Set, then count each unique string Find unique elements without sorting, sort these, thencount each unique string We want to discuss trade-offs of these solutions Ease to develop, debug, verify Runtime efficiency Vocabulary for discussionCPS 1006.2Cost“An engineer is someone who can do for a dime what any fool can do for adollar.” Types of costs: Operational Development Failure Is this program fast enough? What’s your purpose? What’s your input data? How will it scale? Measuring cost Wall-clock or execution time Number of times certain statements are executed Symbolic execution times• Formula for execution time in terms of input size Advantages and disadvantages?Some complexity notes courtesy of Paul HilfingerCPS 1006.3Data processing example Scan a large (~ 107 bytes) file Print the 20 most frequently used words together withcounts of how often they occur Need more specification? How do you do it?CPS 1006.4Possible solutions1. Use heavy duty data structures (Knuth) Hash tries implementation Randomized placement Lots o’ pointers Several pages2. UNIX shell script (Doug Mclroy)tr -cs “[:alpha:]” “[\n*]” < FILE | \sort | \uniq -c | \sort -n -r -k 1,1 | \head -20• Which is better? K.I.S.S.?CPS 1006.5Dropping Glass Balls Tower with N Floors Given 2 glass balls Want to determine the lowest floor from which a ball canbe dropped and will break How? What is the most efficient algorithm? How many drops will it take for such an algorithm (as afunction of N)?CPS 1006.6Glass balls revisited Assume the number of floors is100 In the best case how many ballswill I have to drop to determinethe lowest floor where a ball willbreak?1. 12. 23. 104. 165. 176. 187. 208. 219. 5110. 100 In the worst case, how manyballs will I have to drop?1. 12. 23. 104. 165. 176. 187. 208. 219. 5110. 100If there are n floors, how many balls will you have to drop? (r oughly)CPS 1006.7What is big-Oh about? (preview) Intuition: avoid details when they don’t matter, and theydon’t matter when input size (N) is big enough For polynomials, use only leading term, ignorecoefficients y = 3x y = 6x-2 y = 15x + 44 y = x2 y = x2-6x+9 y = 3x2+4x The first family is O(n), the second is O(n2) Intuition: family of curves, generally the same shape More formally: O(f(n)) is an upper-bound, when n islarge enough the expression cf(n) is larger Intuition: linear function: double input, double time,quadratic function: double input, quadruple the timeCPS 1006.8More on O-notation, big-Oh Big-Oh hides/obscures some empirical analysis, but is goodfor general description of algorithm Allows us to compare algorithms in the limit• 20N hours vs N2 microseconds: which is better? O-notation is an upper-bound, this means that N is O(N),but it is also O(N2); we try to provide tight bounds.Formally: A function g(N) is O(f(N)) if there exist constants cand n such that g(N) < cf(N) for all N > ncf(N)g(N)x = nCPS 1006.9Big-Oh calculations from code Search for element in an array: What is complexity of code (using O-notation)? What if array doubles, what happens to time? for(int k=0; k < a.length; k++) { if (a[k].equals(target)) return true; }; return false; Complexity if we call N times on M-element vector? What about best case? Average case? Worst case?CPS 1006.10Big-Oh calculations again Alcohol APT: first string to occur 3 times What is complexity of code (using O-notation)? for(int k=0; k < a.length; k++) { int count = 0; for(int j=0; j <= k; k++) { if (a[j].equals(a[k])) count++; } if (count >= 3) return a[k]; }; return ""; // nothing occurs three times What happens to time if array doubles in size? 1 + 2 + 3 + … + n-1, why and what’s O-notation?CPS 1006.11Amortization: Expanding ArrayLists Expand capacity of list when add() called Calling add N times, doubling capacity as needed What if we grow size by one each time?2m+1around 22m+2-22 m+12m+1 - 2m+181.751485-841.5643-42122210001Capacity AfteraddResizing Costper itemCumulativecostResizing costItem #CPS 1006.12Some helpful mathematics 1 + 2 + 3 + 4 + … + N N(N+1)/2, exactly = N2/2 + N/2 which is O(N2) why? N + N + N + …. + N (total of N times) N*N = N2 which is O(N2) N + N + N + …. + N + … + N + … + N (total of 3N times) 3N*N = 3N2 which is O(N2) 1 + 2 + 4 + … + 2N 2N+1 – 1 = 2 x 2N – 1 which is O(2N ) Impact of last statement on adding 2N+1 elements to a vector 1 + 2 + … + 2N + 2N+1 = 2N+2-1 = 4x2N-1 which is O(2N)CPS 1006.13Running times @ 106 instructions/sec318centuries18.3 hr16.7 min0.0000301,000,000,00011.6 day19.91.00.0000201,000,0002.78 hr1.6610000.100000.000017100,0001.7 min0.1329000.010000.00001310,0001.00.0100000.001000.0000101,0000.10000.0006640.000100.0000071000.00010.0000330.000010.00000310O(N2)O(N log N)O(N)O(log N)NCPS 1006.14Recursion Review Recursive functions have two key attributes There is a base case, sometimes called the exit case,which does not make a recursive call All other cases make recursive call(s), the results ofthese calls are used to return a value when necessary• Ensure that every sequence of calls reaches base case• Some measure decreases/moves towards base case• “Measure” can be tricky, but usually it’s straightforward Example: sequential search in an array If first element is search key, done and return Otherwise look in the “rest of the array” How can we recurse on “rest of array”?CPS 1006.15Sequential search revisited What does the code below do? How would it be calledinitially? Another overloaded function search with 2 parameters?boolean search(String[] a, int index, String target){ if (index >= a.length) return false; else if (a[index].equals(target)) return true; else return search(a,index+1,target);} What is complexity (big-Oh) of this function?CPS 1006.16Recursion and Recurrencesboolean occurs(String s, String x){ // post: returns true iff x is a substring of s if (s.equals(x)) return true; if (s.length() <= x.length()) return false; return occurs(s.substring(1, s.length()), x) || occurs(s.substring(0,
View Full Document
Unlocking...