CS 211 ASSIGNMENT 5 SOLUTION 

1.
public static int coeffs(int n, int k)
{
	if ( k == 0 )
		return 1;
	else if ( k == n )
		return 1;
	else return coeffs(n-1,k) + coeffs(n-1,k-1);
}

2.
public class Parser
{

 private static CS211In fpe;
 private static CS211Out outfile;
 private String result;

 // this is our recursive descent parsing routine
 // the fpe is assumed to be correct, no error checking in this version
 public static String evalFpe()
 {
	 switch (fpe.peekAtKind()) {
	 case fpe.INTEGER: {
		 int num = fpe.getInt();
		 return "PUSHIMM " + num + "\n"; // string concatenation
		 }

	 case fpe.OPERATOR: {
		 char op = fpe.getOp(); // get the left parentheses
		 String arg1 = evalFpe(); // recursive call to deal with
					  // first argument
		 op = fpe.getOp(); // get the arithmetic operator
		 String arg2 = evalFpe(); // deal with second argument
		 char op2 = fpe.getOp(); // move past right parentheses
		 String arith = "";
		 switch (op) {
		 case '+': arith = "ADD " + "\n";
		 case '-': arith = "SUB " + "\n";
		 case '*': arith = "TIMES " + "\n";
		  }
		 return arg1 + arg2 + arith;
		 }
	}
 }

 public static void main(String[] args)
 {
	if (args.length == 1 )
		fpe = new CS211In(args[0]); // cmd line entry
	else {
		System.out.println("Usage: Parser <filename>");
		return;
	}

	result = evalFpe() + "STOP " + "\n"; // last SaM cmd
	outfile.println(result);
	outfile.close;
 }
}





3.
(a)
   (i). At time t = n hours there are 2^n bacteria if no bacterium ever
	dies before reproducing.
   (ii).If there is a single Arborus Arborus at t = 0, the number of
	bacteria will be larger than 10^80 when 2^n > 10^80 or when
	2^n > (2^(log2(10)))^80; thus when n > 80*log2(10), or when n >= 266.
	( Here log2(x) denotes the base 2 logarithm of x. )

   (iii).If a bacterium is treated as distinct from the two bacteria
         that result when it undergoes fission, the total number of
	 bacteria that have ever existed at or before time n is given by
	 1 + 2 + 4 + .... + 2^(n-1) + 2^n =  2^(n+1) - 1.

(b)
   (i). If some bacteria die before reproducing, all could die out. Thus
	the smallest number of bacteria that can exist at time t = n hours
	is 0 bacteria.
   (ii) On the other hand, it is possible that ( by chance ) none die out;
	we know that in this case the maximal number of bacteria at time
	t = n is 2^n.
   (iii)Assume at least one bacterium is alive at time t = n. Then it
	must have had a predecessor at time t = n-1; this predecessor gave
        rise to another "child" bacterium ( which may now be dead ).
	Apply this same reasoning to the situation of the predecessor
        bacterium at time t = n-1.  It must have had a predecessor at time
	t = n-2; this bacterium had a second "child" as well.  Continuing
	in this fashion we see that the smallest number of bacteria that
	could have existed at or before time t = n is given by 2n + 1.