What is a Binary Search?Analysis: Algorithms and Data StructuresRecursion and recurrencesWhat’s the complexity of this code?FastFinder.findHelperDifferent measures of complexityMultiplying and adding big-OhHelpful formulaeRecursion ReviewSequential search revisitedWhy we study recurrences/complexity?RecurrencesSolving recurrence relationsComplexity PracticeRecognizing RecurrencesCompSci 100E15.1What is a Binary Search?Magic!Has been used a the basis for “magical” tricksFind telephone number (without computer) in secondsIf that isn’t magic, what is?There are less than 1080 atoms in the universe. If ordered, how long to locate a particular one?Demo!What is the big-Oh?CompSci 100E15.2Analysis: Algorithms and Data StructuresWe need a vocabulary to discuss performance and to reason about alternative algorithms and implementationsIt’s faster! It’s more elegant! It’s safer! It’s cooler!We need empirical tests and analytical/mathematical toolsGiven two methods, which is better? Run them to check.o30 seconds vs. 3 seconds, easy. 5 hours vs. 2 minutes, harderoWhat if it takes two weeks to implement the methods?Use mathematics to analyze the algorithm, The implementation is another matter, cache, compiler optimizations, OS, memory,…CompSci 100E15.3Recursion and recurrencesWhy are some functions written recursively? Simpler to understand, but … Mt. Everest reasonsAre there reasons to prefer iteration?Better optimizer: programmer/scientist v. compilerSix of one? Or serious differenceso“One person’s meat is another person’s poison”o“To each his own”, “Chacun a son gout”, …Complexity (big-Oh) for iterative and recursive functionsHow to determine, estimate, intuitCompSci 100E15.4What’s the complexity of this code? // first and last are integer indexes, list is List int lastIndex = first; Object pivot = list.get(first); for(int k=first+1; k <= last; k++){ Comparable ko = (Comparable) list.get(k); if (ko.compareTo(pivot) <= 0){ lastIndex++; Collections.swap(list,lastIndex,k); } }What is big-Oh cost of a loop that visits n elements of a vector? Depends on loop body, if body O(1) then …If body is O(n) then …If body is O(k) for k in [0..n) then …CompSci 100E15.5FastFinder.findHelperprivate Object findHelper(ArrayList list, int first, int last, int kindex){ int lastIndex = first; Object pivot = list.get(first); for(int k=first+1; k <= last; k++){ Comparable ko = (Comparable) list.get(k); if (ko.compareTo(pivot) <= 0){ lastIndex++; Collections.swap(list, lastIndex,k); } } Collections.swap(list, lastIndex, first); if (lastIndex == kindex) return list.get(lastIndex); if (kindex < lastIndex) return findHelper(list, first, lastIndex-1, kindex); return findHelper(list, lastIndex+1, last, kindex);}CompSci 100E15.6Different measures of complexityWorst caseGives a good upper-bound on behaviorNever get worse than thisDrawbacks?Average caseWhat does average mean? Averaged over all inputs? Assuming uniformly distributed random data?Drawbacks?Best caseLinear search, useful?CompSci 100E15.7Multiplying and adding big-OhSuppose we do a linear search then we do another oneWhat is the complexity?If we do 100 linear searches?If we do n searches on a vector of size n?What if we do binary search followed by linear search?What are big-Oh complexities? Sum?What about 50 binary searches? What about n searches?What is the number of elements in the list (1,2,2,3,3,3)?What about (1,2,2, …, n,n,…,n)?How can we reason about this?CompSci 100E15.8Helpful formulaeWe always mean base 2 unless otherwise statedWhat is log(1024)?log(xy) log(xy) log(2n) 2(log n)Sums (also, use sigma notation when possible)1 + 2 + 4 + 8 + … + 2k = 2k+1 – 1 =1 + 2 + 3 + … + n = n(n+1)/2 =a + ar + ar2 + … + arn-1 = a(rn - 1)/(r-1)=•log(x) + log(y) •y log(x) •nlog(2) = n•2(log n) = nki=02ini=1in-1i=0ariCompSci 100E15.9Recursion ReviewRecursive functions have two key attributesThere is a base case, sometimes called the exit case, which does not make a recursive callAll other cases make recursive call(s), the results of these calls are used to return a value when necessaryoEnsure that every sequence of calls reaches base caseoSome measure decreases/moves towards base caseo“Measure” can be tricky, but usually it’s straightforwardExample: sequential search in an ArrayListIf first element is search key, done and returnOtherwise look in the “rest of the list” How can we recurse on “rest of list”?CompSci 100E15.10Sequential search revisitedWhat is complexity of sequential search? Of code below?boolean search(ArrayList list, int first, Object target) { if (first >= list.size()) return false; else if (list.get(first).equals(target)) return true; else return search(list,first+1,target);}Why are there three parameters? Same name good idea?boolean search(ArrayList list, Object target){return search(list,0,target);}CompSci 100E15.11Why we study recurrences/complexity?Tools to analyze algorithmsMachine-independent measuring methodsFamiliarity with good data structures/algorithmsWhat is CS person: programmer, scientist, engineer?scientists build to learn, engineers learn to buildMathematics is a notation that helps in thinking, discussion, programmingCompSci 100E15.12RecurrencesSumming Numbers int sum(int n) { if (0 == n) return 0; else return n + sum(n-1); }What is complexity? justification?T(n) = time to compute sum for n T(n) = T(n-1) + 1 T(0) = 1 instead of 1, use O(1) for constant timeindependent of n, the measure of problem sizeCompSci 100E15.13Solving recurrence relationsplug, simplify, reduce, guess, verify? T(n) = T(n-1) + 1 T(0) = 1 T(n) = T(n-k) + k find the pattern! Now, let k=n, then T(n) = T(0)+n = 1+n get to base case, solve the recurrence: O(n)T(n-1) = T(n-1-1) + 1T(n) = [T(n-2) + 1] + 1 = T(n-2)+2T(n-2) = T(n-2-1) + 1T(n) = [(T(n-3) + 1) + 1] + 1 = T(n-3)+3CompSci 100E15.14Complexity PracticeWhat is complexity of Build? (what does it do?) ArrayList build(int n) { if (0 == n) return new ArrayList(); // empty ArrayList list = build(n-1); for(int k=0;k < n; k++){ list.add(new Integer(n)); } return list; } Write an expression for T(n)
View Full Document
Unlocking...