CSC 152 2005F, Class 34: Algorithm Analysis (1)
Admin:
* Walker observes
* About CSC201
* Homework: Answer the questions at the end of today's outline
("I'm really not sure" is acceptable, but only after a few
minutes of thought.)
("I'm a biologist and there's some good evidence that biologists don't even understand algebra.")
Overview:
* Comparing Algorithms
* And some difficulties
* Informal Analysis
* Experimental analysis: Let's pretend we're a science
Comparing Algorithms
* Single problems admit large numbers of algorithms
* Which of these N solutions do I choose?
* And why?
* To compute x^n
+ Repeatedly multiply by x (n times)
+ Recursion, splitting the expontent in half when even
+ x^n e^(lnx * n)
* To find a particular value in a list/vector
+ Sequential search
for (i = 0 ; i < names.length ; i++) {
if names.get(i).equals("Eryn")
return "Yay";
}
+ Binary search
+ If the Vector is ordered (smallest to largest)
+ Like a tree:
Look in the middle
If what we see matches, stop "Yay"
If what we see is too large, look in the left half
If what we see is too small, look in the right half
* To compute the Nth Fibonacci number
+ Apply the formula fib(n) = fib(n-1) + fib(n-2)
+ Apply the formula, but cache values in a vector
* Delete all elements from a vector, checking whether each meets some criterion and printing it if it does
+ int len = vec.length();
for (int i = 0; i < len; i++) {
String foo = vec.remove(0);
if (check(foo)) {
pen.println(....);
}
}
+ for (int i = vec.length() - 1; i >= 0; i--) {
String foo = vec.remove(i);
if (check(foo)) {
...
}
}
How do we decide which solution to use to each problem?
* Accuracy/Correctness - Gives the result that it should
* Running time: Choose the faster algorithm
* Other attributes, such as memory usage
* Ease of use
* Versatility: Is it adaptable (automatically) to new situations
* Ease of implementation
Our primary analysis: Running time
How do we analyze for running time?
* Count the steps
* Two "steps" may not take the same amount of time
Multiplication vs. addition
* Need to know steps for subroutines/other methods
* Counting is sometimes hard
* Number of steps is not consistent for the same input size
* Conditionals affect running time
Normal CS strategy: Approximate and bound
* Goal: Find the "shape" of a curve that provides upper bound on running time
First technique: Count
* Each basic operation: 1
* Sequence of operations: Sum cost
* Loop: Multiply the cost of the body by the number of reps
* Conditional: Assume worst case
(test plus worst of two branches)
* Subroutines: Use analysis of those subroutines
After counting, throw away constants
Example, sequential search
int i = 0; // 1
while // n repetitions n = names.length
(i < names.length()) { // 1 + 1
if names.get(i).equals("Eryn") // 1 + 1 + 1
return "Yay"; // 1
i++; // 1
}
Approximately: 1 + n * 7 steps
It's really c + d*n
+ int n = vec.length(); // 1
for (int i = 0; i < n ; i++) { // n repetitions
// 3 steps
String foo = vec.remove(0); // n steps
if (check(foo)) { // 1 step
pen.println(....); // 1 step
}
}
Approximately 1 + n(5 + n) steps
Or c + dn + en^2
+ for (int i = vec.length() - 1; i >= 0; i--) {
String foo = vec.remove(i);
if (check(foo)) {
...
}
}
(define sum
(lambda (lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst))))))
(define sum
(lambda (lst)
(if (null? lst)
0
(if (all-numbers? lst)
(+ (car lst) (sum (cdr lst)))
(error "I can't sum lists with non numbers")))))
Experimental analysis
* Annotate your implementation to count steps
* Compare to the formula
* If the formula and the data points match
* Your analysis is likely to be correct
* If the formula and the data points don't match
New homework
* Implement the two versions of remove-all
* Figure a way to time them compratively (wall clock, etc.)