\begin{itemize}

	\item Question: Give an example of a dynamic programming
	algorithm (pseudocode will suffice).  Prove it's correctness
	and establish it's worst case time complexity.

	\item Answer: The typical problem presented when discussing
	dynamic programming is The World Series problem.  Given two
	teams, A and B, for any given game team A will win with
	probability {\it p} ($p \geq 0$, $p \leq 1$), and team B will
	win with probability {\it q} ($q \geq 0$, $q \leq 1$, $p+q=1$).
	What is the probability that team A will win $n$ games before
	team B will win $m$ games.

	Most dynamic programming problems can also be solved
	recursively, but when you decompose the problem into
	subproblems you have overlapping subproblems.  Therefore, you
	wish to design a way that enables you to store previously
	calculated information so you only have to calculate it once
	(as opposed to multiple times).  

	Recursively this problem would be solved as follows:
	$WS(n,m,p) = WS(n-1,m,p)*p + WS(n,m-1,p)*q$, where  $ WS(0,m,p)
	= 1, \forall m$ and $WS(n,0,p) = 0, \forall n$, and $WS(0,0,p)$
	is undefined.

	Dynamically you would build a table (n by m) and fill in the
	probabilities for each cell in a row by row fashion, and then
	return the value of the n,m entry.

	\begin{verbatim}
	float WS(int n,int m,float p){
	   int i,j;
	   float q;
	   float table[100][100];

	   if((n>100) || (m>100)){
	      printf("max values for WS are 100 by 100\n");
	      return(0.0);
	   }
	   for(i=0;i<=m;i++)
	      table[0][i] = 0;
	   for(i=0;i<=n;i++)
	      table[i][0] = 1;
	   for(i=1,i<=n;i++){
	      for(j=1;j<=m;j++){
	         table[i][j] = table[i][j-1]*p + table[i-1][j]*q;
	      }
	   }
	   return(table[n][m]);
	}
	\end{verbatim}

	Proof of correctness is done via a proof by induction on m and
	n.	

	Complexity for this algorithm is $n*m$.
\end{itemize}
