Computer Science 15-100 (Sections T & U), Spring 2008
Homework 10b
Due:  Fri 11-Apr-2008 at 10am (online submission) and at recitation (physical copy)
(no late submissions accepted <-- really!)

Note that both parts of hw10 are due on Friday.  Do not leave this whole assignment until Thursday night!!!  We still recommend that you complete Part A by Tuesday, and we will still provide Monday night office hours.  You are strongly advised to take advantage of them.

• Be sure to include your name, your Andrew ID, and your section (T or U) clearly on the top of each file in your assignment.
• Name your program and your methods exactly as indicated.
  • You will have one program for both part A and part B combined:
    1. Hw10.java
• Use well-named variables, proper indenting, reasonable commenting, etc.  Do not use magic numbers!
• Provide complete (but concise) test cases!
• Provide the UI exactly as indicated.  File-based UI should not include prompts.
• Submit printed solutions in class.  Your printed solutions must be identical copies of your emailed solutions!
• Even though you are not always provided with a test method, you must write an appropriate test method for every method you write!

Exercise 1:  Postfix

In this exercise, you will write a Java method that evaluates postfix expressions (also known as Reverse Polish Notation, or RPN).  You can read all about them at the RPN Wikipedia page.

A postfix expression places the operator after the operands.  For example, "3 4 +" will add 3 and 4 to get 7.  Simple enough.  But what about "2 3 4 + *"?  The '+' will add the preceding two values, to get 7, then the '*' will multiply the preceding two values (2 and now 7) to get 14.  See?

More generally, to evaluate a postfix expression, we use a stack (which is why we are doing it here, while we study the Java Collection Framework, which happens to include a Stack class, as mentioned during lecture).

Recall that a stack is much like a stack of dishes (hence the name).  You can place an element on the top (or "push" an element onto the stack), and you can remove an element from the top (or "pop" an element off the stack).  You can also check if the stack is empty.  Here is Java code that demonstrates the basic use of a Stack:

    Stack stack = new Stack();
    verify(stack.isEmpty() == true);
    stack.push("abc");
    stack.push("def");
    verify(stack.isEmpty() == false);
    verify(stack.pop().equals("def")); // last in, first out!
    verify(stack.pop().equals("abc"));
    verify(stack.isEmpty() == true);

Now, to evaluate a postfix expression:  first, create an empty stack.  Next, for each element in the expression (from left-to-right):  if the element is a number (and we will limit ourselves to integers here), simply push it on the stack.  If the element is an operator, pop the preceding two numbers from the stack, apply the operator to these numbers, and push the result back onto the stack.  If the expression is "well-formed", then when we are done the stack will contain exactly one element:  the final answer.

So let's see how we would evaluate "2 3 4 + 5 * -":

• Start with an empty stack:  Stack = [ ]
• Push 2 onto the stack:  Stack = [ 2 ]
• Push 3 onto the stack:  Stack = [ 2 3 ]  <-- 3 is on the top, 2 on the bottom
• Push 4 onto the stack:  Stack = [ 2 3 4 ]
• Pop previous 2 values (3 4), apply '+' to find 3+4 = 7, push result onto stack.  Stack = [ 2 7 ]
• Push 5 onto the stack:  Stack = [ 2 7 5 ]
• Pop previous 2 values (7 5), apply '*' to find 7*5 =35, push result onto stack.  Stack = [ 2 35 ]
• Pop previous 2 values (2 35), apply '-' to find 2-35= -33, push result onto stack.  Stack = [ -33 ]
• Finally, we are done, so pop the final answer off the stack.  Answer = -33, Stack = [ ].

Your task:  Write a Java method, evalPostfix, that takes on parameter -- a String containing a well-formed postfix expression consisting of integers and the operators +, -, *, /, and % -- and returns the int value that this expression evaluates to.  You can assume the expression is well-formed and you can ignore overflow.  Here is the start of a test method:

  public static void testEvalPostfix() {
    System.out.print("Testing evalPostfix()...  ");
    verify(evalPostfix("2 3 +") == 5);
    verify(evalPostfix("2 3 -") == -1);
    verify(evalPostfix("2 3 *") == 6);
    verify(evalPostfix("2 3 /") == 0);
    verify(evalPostfix("2 3 ^") == 8);
    verify(evalPostfix("2 3 4 * +") == 14);
    verify(evalPostfix("2 3 4 * 5 % -") == 0);
    verify(evalPostfix("2 3 4 + 5 * -") == -33);
    System.out.println("Passed all tests!");
  }

Hint: create a scanner object to scan from the parameter string.  Then, you must keep iterating so long as the scanner has any input (scanner.hasNext() is true).  Then, you can check if the next value in the string is an int using the scanner's hasNextInt method.  If it is an int, read it in and push it on the stack.  If it's not an int, read it in using scanner.next rather than scanner.nextInt, and follow the rules to apply this operator to the preceding two values on the stack and push the result back onto the stack.

Exercise 2:  The Birthday Problem

In this exercise, you will solve the famous Birthday Problem.  You can read all about this on the Birthday Problem Wikipedia page

In its simplest form, the problem asks:  how many people must be in a room before it is more likely than not that at least two of them share the same birthday (just the day and month, not the year)?  Ignoring leap years (which we will throughout the problem), the answer is 23, which is surprisingly low to many people.  Of course, with fewer than 2 people in the room, the odds of a duplicate are 0%, and with 366 or more people in the room, the odds are 100% (right?).  But we are chiefly concerned with when the odds  become greater than 50%, and that happens with 23 people in the room.

How will we solve this problem?  Certainly not by learning the math involved to solve it!  Instead, we will use Monte Carlo techniques to approximate the solution.  That is, to determine the odds of a duplicate birthday given N people in the room, we'll just run a whole bunch (a million, actually) of tests, placing N people in a room where we pick birthdays randomly for each person, and seeing how many times there is a duplicate.  If out of the 1 million tests, say 500,000 of them result in duplicates, then we conclude the odds are 500,000 / 1m, or 50%.  In general, if out of 1 million tests we have K of them with duplicates, then the conclude that the odds of a duplicate among N people is K/1m.  We run this test for varying numbers of people (N) in the room, and in that way we can find the odds for any number of people.  Now, we have to run 1 million tests for each N, so this can take a while (several minutes for one of our test methods), but that's ok!

In the first step of this problem, you should write a method, duplicateBirthdays, that takes an int N and returns a boolean.  This method will run ONE TEST, placing N people in a room, each assigned a random birthday, and returning true if there in fact was a duplicate among them.  To do this, your method must work as such:  first, create a new empty set (actually, a HashSet).  This will contain all the birthdays so far assigned, where a birthday will be a random number between 0 (inclusive) and 365 (exclusive).  Do you see why encoding the birthday in this way is very convenient for solving this problem?  In any case, run a counter from 0 (inclusive) to N (exclusive), and find a new random birthday, and if it is not in the set, add it to the set.  On the other hand, if a new birthday is already in the set, we have a duplicate, so return true from the method immediately.  If you add all N birthdays and have no duplicates, then you should return false.  This method requires about 9 lines of code.

Next, write a method, duplicateBirthdayOdds, that takes an int N and returns a double containing the odds that N people in a room would have at least one duplicate birthday.  This method simply calls duplicateBirthdays (from above) one million times, counting how many times duplicates occur, and returning the ratio of duplicate-occurrences to overall tests (1 million), as a double.  This method requires about 8 lines of code.

Note that, due to our Monte Carlo methods, our answers can vary a bit.  For this reason, you should use a relaxed version of almostEqual, such as this that allows answers within 0.005 (one-half of 1%) to be equal:

  public static boolean almostEqual(double d1, double d2) {
    return Math.abs(d1-d2)<0.005;
  }

Using this relaxed almostEqual method, here is the start of a test method for duplicateBirthdayOdds:

  public static void testDuplicateBirthdayOdds() {
    System.out.print("Testing duplicateBirthdayOdds()...  ");
    verify(almostEqual(duplicateBirthdayOdds(10),0.116)); // 11.6% chance
    verify(almostEqual(duplicateBirthdayOdds(20),0.412)); // 41.2% chance
    verify(almostEqual(duplicateBirthdayOdds(23),0.507)); // 50.7% chance
    verify(almostEqual(duplicateBirthdayOdds(30),0.707)); // 70.7% chance
    System.out.println("Passed all tests!");
  }

From this we see that with 10 people in a room, there is only an 11.6% chance that there will be a duplicate birthday.  Between 20 and 30 people, however, this number rises quickly from 41.2% to 70.7%.

Now, the birthday problem asks how many people must be in the room for there to be at least a 50% chance of a duplicate, and the answer is 23.  But we will generalize this problem in the method "birthdayProblem", which will take a double p between 0.0 and 1.0, and returns an int that is the fewest number of people that must be in the room so that the odds of a duplicate are greater than p.  Of course, this method will repeatedly use the duplicateBirthdayOdds method we just wrote, and so only requires only 6 lines of code.  Here is the start of a test method (which can take quite a while to run to completion, which is why it prints out feedback as it goes):

  public static void testBirthdayProblem() {
    System.out.println("Testing birthdayProblem() (this can take a while)...  ");
    verify(birthdayProblem(0.40) == 20);
    System.out.println("Passed test #1");
    verify(birthdayProblem(0.50) == 23);
    System.out.println("Passed test #2");
    verify(birthdayProblem(0.70) == 30);
    System.out.println("Passed test #2");
    System.out.println("Passed all tests!");
  }

As you can see, birthdayProblem(0.50) returns 23, clearly confirming (though not technically proving) that the answer to the classic Birthday Problem is in fact 23 people.

Carpe diem!