CSC152 2006S, Class 33: Algorithm Analysis (1)

Admin:
* Guest lecturer - Sam takes notes in this page.
* Exam distributed Friday.
* Reading: Algorithm Analysis
* EC for attending today's talk at 4:30

Overview:
* What makes a good algorithm?
* Computational complexity
* Big-O Notation

/What Makes a Good Algorithm?/

* Student Responses
  * Efficient 
  * Effective
  * General

* Whoops ... it was a trick question.  Good for _what_?
  * Do we care if an algorithm takes 1 millisecond or 1 microsecond if we only run it once a day?
* Observation: The amount of time writing new code is _dwarfed_ by the amount of time you spend reading old code.
  * Clear may be the most important aspect for something that does not get run a lot.
* What if your time is worth a _lot_ more than the computer's time?
  * Then the algorithm should also be easy to implement.
  * Consistent

* Story: Roller Coaster simulator
  * 1000's of objects
  * Need to sort objects during each screen refresh
  * 30 refreshes per second

* So, how do we measure how long an algorithm takes?
  * One answer: Time how long it takes
  * Trick question: How long does it take to compute 3+4 at run time?
    * Answer: Java spec says "Computed at compile time"
  * How long does it take to compute "a+b"?
    * Very little time
    * But it depends on a number of factors.  On modern computers, not all variables are "in cache" (the fast memory).  It may take a while to load it from the disk.
  * So we abstract: x = a + b takes "one addition plus one assignment", even though both operations take different times
  * Now we can compare two algorithms by the total number of additions and assignments

* Example: How do we compute x^n, where x is a double?
  multiply x by itself n times
  * Java code
    double result = 1.0;
    for (int i = 0; i < n; i++) {
      result = result * x;
    }
  * How long does this take?
    * 2*n+2 assignments
    * n additions
    * n multiplications
    * n comparisons
  * A divide-and-conquer solution
    (define (pow x n)
       (cond
          ((zero? n) 1)
          ((odd? n) (* x (pow x (- n 1))))
          (else (let ((tmp (pow x (/ n 2)))) (* tmp tmp)))))
  * How long does this take?
    * Hand waving: 2*log_2(n) recursive calls, at worst
      * Sam inserts: 
        * If we do the odd case, in the next recursive call, we choose the even case
        * In the even case, we divide the exponent by two
        * log_2(n) is, approximately, "the number of times you have to divide n in half until you get 1"
    * Each recursive call includes a few tests, perhaps a let, and a multiplication
    * So 
      * 2*log_2(n) multiplications
      * 2*log_2(n) tests
      * Perhaps log_2(n) lets
      * 2*log_2(n) function calls
* Observation: Given that we don't know about the comparative cost of the different operations, why don't we treat them all the same?
  * The first algorithm takes about 5*n operations
  * The second algorithm takes about 7*log_2(n) operations
* Now, do we really care whether something is 5*n or 4*n or 6*n,
  particularly since we've now merged different operations?  No,
  we really care that it's "some number" times n.
* So, the first algorithm is "some number" times n
* The second algorithm is "some number" times log_2(n)
* How much better is the second?  Let's consider a chart

  n                     | 1 | 10   | 1000  | 10^6   |
  ---------------------------------------------------
  Constant: 1           | 1 | 1    | 1     | 1      |
  Logarithmic: log_2(n) | 0 | 3.2  | 10    | 20     |
  Linear: n             | 1 | 10   | 1000  | 10^6   |
  Quadratic: n^2        | 1 | 100  | 10^6  | 10^12  |
  Cubic: n^3            | 1 | 1000 | 10^9  | 10^18  |
  NlogN: nlog_2(n)      | 0 | 30   | 10000 | 2x10^7 |

* For real problems, the nlogn algorithm is significantly better than an n^2 algorithm
* Problem: What if we're using different representations?
  * For BigDecimal and BigInteger, addition (and multiplication) take time relative to the size of the number (the number of columns)
 
* Question from "the class": Why did you make the improvement to the recursive algorithm?
  * Answer from the class: One recursive call is clearly better than two

* When analyzing algorithms, we often consider: worst case, best case, average case
  * Binary search is
    * Constant in the best case (the thing you're looking for is in the middle)
    * Logarithmic in the worst case
    * Logarithmic in the average case
  * Bubble sort (if you know bubble sort) is
    * Linear in the best case
    * Quadratic in the worst case
    * Quadratic in the average case

Notation: a function is O(n) if it takes times proportional to
n.
* Sam will explain more tomorrow