Lecture 15: 7/13/00. Michael Brudno

Whenever you look at a program you should be asking yourself two
questions: "How fast does this program run?" and "Can we design faster
programs that do the same thing?" Let us consider a few examples where
we try to evolve from some none-ideal solution to a perfect one.

Lets write the iterative function "power" 

int pow (int base, int power) { 
    int result = 1; 
    for (int i = 1; i < power; i++) 
       result = result * base; 
    return result; 
  } 

Pretty trivial stuff. And it works in linear time, in general that is
a good speed. But say we were using BigIntegers rather than ints. Then
each multiplication would take a while and the algorithm may not look
as great. So we look for a more efficient way to implement
exponentiation. Going back to middle school and Algebra 1 we recall
that x^(2n) = (x^2)^n. This allows us to halve the size of the input
without too much effort. When evaluating x^n for even n we just use
the formula above. Otherwise we multiply the result by x, and then use
the formula. The following is our resulting code:

 int qpow(int base, int power) { 
    int result = 1; 
    while(power > 0) { 
      if(power %2 == 1) 
        result = result * base; 
      base = base * base; 
      power = power/2; 
    } 
    return result; 
 } 

This implementation takes log n time rather than linear time. If all
you are dealing with is small integers, than this doesn't really
matter, but when you get into BigIntegers and the like, the difference 
is quite noticeable. 

Let's go back to one of the first things you did in 61a: 

Write a function to return nth Fibonacci number. 

 int Fibo(int n) { 
   if ((n == 1) || n == 2) 
     return 1; 
   return Fibo(n - 1) + Fibo(n - 2); 
 } 

This runs in about 2^n time, because of every next value of n you call
the function recursively twice more (It is actually 1.7^n, because one
of the calls is with n-2 rather than with n-1). However it should be
clear to you that we can do better. We don't need to recalculate all
the values, just store the last 2 and add them to get the next. The
following is the implementation of this algorithm:

Lets write the above problem with a linear algorithm 

 int FiboLin(int n) { 
   int first = 0; 
   int second = 1; 
   for (i = 0; i < n; i++) { 
     temp = first; 
     first = second; 
     second = first + temp; 
     } 
   return first; 
 } 

This is a linear algorithm: O(n). The loop will be executed n times. 

At this point computer science becomes powerless and we turn to the
mathematicians, who back in the 17th century came up with Binet's (De
Moivre's) formula. It allows us to calculate the nth Fibonacci number
without first figuring out the ones which come before it.

if a = (sqrt(5) + 1) / 2 ( The golden Ratio)

Fib(n) = ((a^n) - (-a ^(-n))) / (sqrt(5)) 

At first glance we might think that this is a O(1) algorithm, that
it's running speed does not depend on n, but then we should remember
that taking a^n will take log(n) time, so calculating the whole
formula would be O(log n).

However this formula would be useless unless we had figured out a way
to do exponentiation in log time: if we were using the linear time
program to do exponents than the running speed for figuring out this
formula would be the same as for the linear solution above.

Side note: In 61a you did this problem using memoization, and the 
resulting algorithm was called "efficient." Was it though? Each
lookup in a 61a table actually took O(n) time, with n the size of
the table because you had to traverse pointers to get to the right
entry. Hence the running time was actually n^2. 

Vectors

Java has a class called java.util.Vector. It will be useful to you for
your project. Lets take a look at how this class works "under the
hood."

The following are a subset of the methods defined in the class:

  addElement(Object) 
     Adds the specified component to the end of this vector, increasing 
     its size by one. 
  elementAt(int) 
     Returns the component at the specified index. 
  setElementAt(Object, int) 
     Sets the component at the specified index of this vector to be the 
     specified object. 
  insertElementAt(Object, int) 
     Inserts the specified object as a component in this vector at the 
     specified index. 
  setSize(int) 
     Sets the size of this vector. 
  size() 
     Returns the number of components in this vector. 

The underlying datastructure is an array, and consequently several of
these methods may take some time to run: insertElementAt, as you know
from HW1 runs in linear time. Not so, however, with addElement()!  The
trick is that instead of growing the array one by one, as you are used
to doing (for instance for the heap problem) you can double it.

Well, that's intuitive enough, but how big will be your savings?  Just
last lecture I said that we only care about the worst case time, and
the worst case time is still the same: when you have to grow the array
it will still cost you O(n) if your array is full. Plus, instead of
doubling the array we could instead just grow it by 100 elements: we
will be saving space (at most only 100 extra elements allocated
instead of double using the other method, and we'll get a hundred fold
increase in speed!

That's all great, but its actually better to double the size. First,
the savings in space using the latter method are minimal: 2n is in
O(n) just like n+100. Second, lets examine how many operations are
required to insert n elements into an array with (initially) 0
elements. Let's assume it takes no work to allocate an array. Then:
 
1. If we were to increase the array one at a time, we would need 1
step for the first element, two for the second, three for the third,
etc.  1+2+3+...+n = n*(n-1)/2 is in O(n^2).

2. If we were to grow the array by 100 elems, we would use 1 step for
elems 1-99, 100 steps for 100, 1 for 101-199, 200 for 200, etc.  So
the first 100 elems require 200 steps, the next 100 require 300, the
next 400. The sum is 
100*( n/100 )( n/100 - 1 )/2 = n*( n/100-1 )/2 ~= (n^2)/200
is still O(n^2).

3. If we were to double the array each time, we would get a cost of
O(1) for all but lg k insertions. The other ones cost 
k + k/2 + k/4+...+1 = 2k combined. Hence the total time, 3n, is in O(n),
and additions turn out to be constant time!

On the newsgroup someone (you know who) asked whether there would be a
time difference if instead of doubling it, we grew the array to the
next fibonacci number. This is equivalent with replacing the 2 with a
1.7. The series will still converge to a multiple of k, hence the
running time is unaffected.

Furthermore, here we assumed that allocating a new array is free. In
fact it is very expensive, in some cases it may cost as much as
O(n^3).  In these you will feel the savings that much more.

The method we are using above is known as ammortized analysis: instead
of looking at how long one operation may take, we look at how long it 
will take to do k operations and divide by k. This is not looking at
average case time.

Problem: maximal subsequence: Given an array of n integers, determine
indices i,j such that the sum of the elements between i and j (inclusive)
is maximal.
Trivial approach: look at all sub-sequences. 
 
int[] maxsub(int[] a) {
  int[] res = new int[2];
  int max = a[0];
  for (int i = 0; i < a.length; i++) {
    int count = 0;
    for (int j = i; j < a.length; j++) {
      count += a[j];
      if (count > max) {
         max = count;
	 res[0] = i;
	 res[1] = j;
      }
    }
  }
  return res;
}

However, we can do better! The key observation is that once the sum 
goes below zero, it can never help us in the future. Hence we can just 
throw it out!
The elegant, linear solution:

int[] maxsub(int[] a) {
  int[] res = new int[2];
  int max = a[0];
  int count = a[0];
  int begin = 0;
  for (int i = 1; i < a.length; i++) {
    count += a[i];
    if (count > max) {
      max = count;    
      res[0] = begin;
      res[1] = i;
    }
    if (count < 0) {
      begin = i+1;
      count = 0;
    }
  }
  return res;
}

At this point I mention stuff on Theta and Omega. Read yesterday's 
notes by Professor Hilfinger.

The running time actually makes a difference: I once wrote a program that 
worked in quadratic time ( O(n^2)) and it took 3 hours on input of size
1000. Changing the algorithm to n lg n reduced the running time to 3 
minutes. In my research area, computational genomics, O(n^2) algorithms
generally are considered inefficient: the human DNA has 3 billion base 
pairs, while the simplest bacteria have several million.