CSC152 2004F, Class 24: Algorithm Analysis (1) Admin: * No more daily homework before break * Project assignment due next Tuesday * Extra credit for attending convo Overview * Motivating example: Exponentiation * Comparing Algorithms * Problems Evaluting Running Time * Asymptotic Analysis * Asymptotic Analysis in Practice * Eliminating Constants /Choose a Project * World Model Group A Gaurav Leigh Brad Group B Eric Eryn * User Interfaces: Angeline Kyle Michael * Network: Read http://java.sun.com/docs/books/tutorial/networking/ Billups Brett Louisa * AI Kevin Observations: * The Event Manager seems uninteresting * Almost everyone wants to do the world /Problem: Compute x to the yth power/ * Assume y is a non-negative integer * Assume x is a BigDecimal * Compute x * x * x * ... * x (y x's) * Use some sort of loop (while or for loop) * Count i from 1 to y (or 0 to y-1) * At each step, multiply the previous result by x public BigDecimal exp(Double x, int y) { BigDecimal result = new BigDecimal(1.0); for (int i = 0; i < y; i++) { result = result.multiply(x); } return result; } * Are there other strategies? * Does BigDecimal include an exp method? * Use the wonder of logarithms e^(log(x)*y) * Sorry, Java doesn't include those for BigDecimals * Look toward standard algorithm design techniques * Divide and conquer: Break the problem in half, solve one or both halves, combine into result * E.g.,: Binary Search, Merge Sort (Split in half, sort each half, merge together) * Apply divide-and-conquer to this algorithm. * Assume y is even Does computing x^(y/2) help us compute x^y? Yes, x^y = square(x^(y/2)) /Which algorithm is better?/ * Are both correct for "every case" (or at least every case we care about)? * Which one is faster? * Which is more readable? Someone may have to maintain or modify our code. (Better documentation may help.) * Which permits the best error recovery? * Which uses more memory? /How do you decide which algorithm is faster?/ * See how much time each one takes. * Suppose I have two algorithms, one of which I'm going to run on an input of size 10000000000. I know it will take at least a day to run. How do I decide which one to use? * Look at smaller problems and see which is better on smaller problems. (E.g., fib) * Often a good idea * However, small problems can be misleading * Next solution: Attempt to figure out the "curve" (running time as a function of input size) for each algorithm * Problem: Figuring out these curves through simple data analysis can be hard. * Solution: Look at the algorithm and figure out what the curve should be. * Observation: The "look at the algorithm" will give us a general shape, but not a particular formula. /For our two algorithms/ * expi has the shape of m*exponent+b 1000: 31 2000: 50 3000: 93 4000: 117 6000: 186 20000: 1423 * expr has the shape? 1000: 1 2000: 18 3000: 1 4000: 2 6000: 5 10000: 36 20000: 72 100000: 1240 Hmmm ... * Confounding problem: Multiplication takes longer as the number gets bigger Why does the time vary with different X's? * Some quite similar computations take less time than others (it's easier to multiply 2 x 2 than 1.000123123123123 by the same number) Why does the time vary with the same X? * Because my computer is doing more than just running the Java program