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