binomial

function americanPut(T, S, K, r, sigma, q, n) 
{ 
  '  T... expiration time
  '  S... stock price
  '  K... strike price
  '  q... dividend yield
  '  n... height of the binomial tree
  deltaT := T / n;
  up := exp(sigma * sqrt(deltaT));
  p0 := (up*exp(-q * deltaT) - exp(-r * deltaT)) / (up^2 - 1);
  p1 := exp(-r * deltaT) - p0;
  ' initial values at time T
  for i := 0 to n {
      p[i] := K - S * up^(2*i - n);
      if p[i] < 0 then p[i] := 0;
  }
  ' move to earlier times
  for j := n-1 down to 0 {
      for i := 0 to j {
          ' binomial value
          p[i] := p0 * p[i+1] + p1 * p[i];   
          ' exercise value
          exercise := K - S * up^(2*i - j);  
          if p[i] < exercise then p[i] := exercise;
      }
  }
  return americanPut := p[0];
}