COMP 1006 - Assignment 9

Due : Wednesday April 3rd, 2013 at 9pm

1. More Recursion: Create a class called Palindromes. Your class should have should have two static methods:

   public static boolean isPalindrome(String s){...}
   // Preconditions: s is not null
   // Postconditions: returns true if s is a palindrome; false otherwise
   //                 - ignore case and whitespace in palindrome determination
   // Examples: (see Assignment #5)
   
   
   public static boolean isPalindrome2(String s, Character c){...}
   // Preconditions: s is not null, c is not null
   // Postconditions: returns true if s is a palindrome, where the character c is considered
   //                 as a wildcard.  That is, c will match any other character non-whitespace character;
   //                 returns false otherwise
   //                 - if c is an empty character or a whitespace character, 
   //                   the behaviour of the function is identical to isPalindrome (above)
   //                 - ignore case and whitespace in palindrome determination
   // Examples: 
   // Palindromes.isPalindrom2("cat", 't') => true
   // Palindromes.isPalindrom2("wows", 's') => false
   

   Your methods must be implemented using recursion.

   Create another class called TestPalindromes that has a main function and shows some testing of you Palindromes class.

   Submit your Palindromes.java file and your TestPalindromes.java file (in your assignment zip file).

   Note: Have a look at the String class in Java here to find useful methods.

2. Even More Recursion: Consider the following Person class:

   public class Person{
      public int     id;     // some identification number unique to the person
      public boolean zombie; // true if the person is a zombie
   
      public ArrayList<Person> friends;  // list of friends
   }
   

   Using this Person class (you can add constructors, attributes and methods as if needed), implement the following class

   public class Zombies{
      public static int countPeople(Person p){...}
      // counts all the people in the tree structure 
      // starting with Person p. 
   
      public static int countZombies(Person p){...}
      // counts all the people in the tree structure
      // starting with Person p that are zombies
   
      public static void draw(Person p){...}
      // draws a diagram of the people in tree structure
      // starting with Person p.
      // each person will be denoted by a P and 
      // person that is a zombie will be denoted by a Z
      //
      // The diagram should illustrate the family tree
      // structure.  Each person will be drawn with 3 minus  
      // signs '-' for each level below p.
      // (See examples below)
   }
   

   Use recursion to complete the three functions in the Zombie class. Create a third class called TestZombie, that tests your zombie functions.

   Submit your Person.java, Zombies.java and TestZombies.java files for this problem (in your assignment zip file).

   Example: If Person q has 3 friends, and each of these friends has exactly 2 friend, a call of draw(q) will look something like (I'll add comments that should not appear in your diagram)

   P          (this is Person q)
   ---P       (this is a friend of q, say q1)
   ------P    (this is a friend of q1)
   ------Z    (this is another friend of q1, who is a zombie)
   ---Z       (this is a friend of q, say q2, who is a zombie)
   ------Z    (this is a friend of q1, who is also a zombie)
   ------P    (this is a friend of q1, who is not a zombie)
   

   When displaying your diagram (just use print and println), you should display all of a persons friends (think children in a family tree) before displaying the next person (sibling in a family tree). Notice above that all of q1's friends are shown before q2 is shown.

   Note: You can create your tree structure so that there are no cross-links. Each Person in the tree structure can exist in only one friend's list and there will be one Person that is in no ones friend's list (the root of the tree). This will allow you to easily terminate your recursive methods (without worrying about having cycles in the structure).

public static void spreadZombie(Person q, double prob){...}
// starting with Person q, if q is not a zombie, 
// the method turns q into a zombie with probability prob.
// If q is a zombie (either initially or just turned into one)
// the method will recursively call itself on 
// each of q's friends, but with probability that is 0.75 times
// the probability prob.