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