Dropping Glass BallsGlass balls revisited (more balls)What is big-Oh about? (preview)More on O-notation, big-OhWhich graph is “best” performance?Big-Oh calculations from codeAmortization: Expanding ArrayListsSome helpful mathematicsRunning times @ 106 instructions/secLoop InvariantsBean Can gameBean Can AlgorithmBean Can AnalysisThe Game of NimNim AnalysisNim AlgorithmNumbers from EndsPatternsWhat is a pattern?Patterns are discovered, not inventedProgramming ProblemsRemoving DuplicatesOne loop for linear structuresCoding PatternCompSci 100E4.1Dropping Glass BallsTower with N FloorsGiven 2 glass ballsWant to determine the lowest floor from which a ball can be dropped and will breakHow?What is the most efficient algorithm?How many drops will it take for such an algorithm (as a function of N)?CompSci 100E4.2Glass balls revisited (more balls)Assume the number of floors is 100In the best case how many balls will I have to drop to determine the lowest floor where a ball will break?1. 12. 23. 104. 165. 176. 187. 208. 219. 5110. 100In the worst case, how many balls 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? (roughly)CompSci 100E4.3What is big-Oh about? (preview)Intuition: avoid details when they don’t matter, and they don’t matter when input size (N) is big enoughFor polynomials, use only leading term, ignore coefficients y = 3x y = 6x-2 y = 15x + 44 y = x2 y = x2-6x+9 y = 3x2+4xThe first family is O(n), the second is O(n2)Intuition: family of curves, generally the same shapeMore formally: O(f(n)) is an upper-bound, when n is large enough the expression cf(n) is largerIntuition: linear function: double input, double time, quadratic function: double input, quadruple the timeCompSci 100E4.4More on O-notation, big-OhBig-Oh hides/obscures some empirical analysis, but is good for general description of algorithmAllows us to compare algorithms in the limito20N 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 c and n such that g(N) < cf(N) for all N > ncf(N)g(N)x = nCompSci 100E4.5Which graph is “best” performance?CompSci 100E4.6Big-Oh calculations from codeSearch 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?CompSci 100E4.7Amortization: Expanding ArrayListsExpand capacity of list when add() calledCalling add N times, doubling capacity as neededWhat if we grow size by one each time?Item # Resizing costCumulative costResizing Cost per itemCapacity After add1 0 0 0 12 2 2 23-4 4 6 1.5 45-8 8 14 1.75 82m+1 - 2m+12 m+12m+2-2 around 2 2m+1CompSci 100E4.8Some helpful mathematics1 + 2 + 3 + 4 + … + NN(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 vector1 + 2 + … + 2N + 2N+1 = 2N+2-1 = 4x2N-1 which is O(2N) resizing + copy = total (let x = 2N)CompSci 100E4.9Running times @ 106 instructions/secN O(log N) O(N) O(N log N)O(N2)100.000003 0.00001 0.000033 0.00011000.000007 0.00010 0.000664 0.10001,0000.000010 0.00100 0.010000 1.010,0000.000013 0.01000 0.132900 1.7 min100,0000.000017 0.10000 1.661000 2.78 hr1,000,0000.000020 1.0 19.9 11.6 day1,000,000,0000.000030 16.7 min 18.3 hr 318 centuriesCompSci 100E4.10Loop InvariantsWant to reason about the correctness of a proposed iterative solutionLoop invariants provide a means to effectively about the correctness of codewhile !done do // what is true at every step // Update/iterate // maintain invariantodCompSci 100E4.11Bean Can gameCan contains N black beans and M white beans initiallyEmptied according the following repeated processSelect two beans from the canIf the beans are:osame color: put a black bean back in the canodifferent colors: put a white bean back in the canPlayer who chooses the color of the remaining bean wins the gameAnalyze the link between the initial state and the final state Identify a property that is preserved as beans are removed from the canInvariant that characterizes the removal processCompSci 100E4.12Bean Can Algorithmwhile (num-beans-in-can > 1) do pick 2 beans randomly if bean1-color == bean2-color then put-back black bean else put-back white beanodCompSci 100E4.13Bean Can AnalysisWhat happens each turn?Number of beans in can is decreased by oneNumber of white beans is either reduced by 2 or 0Number of black beans is either reduced by 1 or 0Examine the final states for 2 bean and 3 bean initial statesAny guesses for the correct strategy?What is the process invariant?CompSci 100E4.14The Game of NimTwo Piles of counters with N and M counters in each pile2 players take turns:Remove some number of counters (≥ 1) from one pilePlayer who removes last counter winsPropertiesComplete information: could exhaustively search for winning solutionImpartial: same moves are available for each playerCompSci 100E4.15Nim AnalysisDenote state by (x,y): number of counters in each pileWhat about simple case of (1,1)?For whom is (1,1) a “safe” state?How about (1,2) or (1,3)?How about (2,2)?What is the invariant to be preserved by the winning player?CompSci 100E4.16Nim Algorithm// reach a state (x,y) where x=y on opponent’s // turn and then follow below algorithmwhile !empty(pile1) && !empty(pile2) do let opponent remove q counters from a pile remove q counters from other pileodCompSci 100E4.17Numbers from EndsGame begins with some even number of numbers on a line 10 5 7 9 6 12Players take turns removing numbers from the ends while keeping running sum of numbers collected so farPlayer with largest sum winsComplete information but how to win without search?CompSci 100E4.18Patterns"Each pattern describes a problem which
View Full Document
Unlocking...