COP 3337
  Section U05
  Spring 2017



                           HOMEWORK # 3
                           ============

                                         Due date: February 27, 2017


   Do only the problems that are next to your name. Put the 5 static methods
  into a class named Recursion.java and email them to pelina@cis.fiu.edu.

  Problem 1: Write the method
  ----------
         public static boolean isDavis(String in)

  that returns true if the string in is Davis and false if it is not.
  The Davis strings are defined below.   

   1. ab is a Davis string.

   2. cbac is a Davis string.

   3. baccba is a Davis string.

   4. If S is a Davis string, so is SbSa.

   5. If U and V are Davis strings, so is aUbV.

  Here a, b, c are constants and S,U,V are variables. In these rules,
  the same letter represents the same string. So, if S = ab,
  rule 3 tells us that abbaba is a Davis string.
  In rule 5, U and V represent Davis strings, but they may be different.

  Problem 2: Write the method
  ----------
         public static boolean isHuyn(String in)
     that returns true if in is a Huyn string and false otherwise.

  The Huyn strings are defined as follows:

    1. acb is a Huyn string.

    2. bca is a Huyn string.

    3. If S is a Huyn string, so is aSScb.

    4. If U and V are Huyn strings, so is bcUVa.

  Here a, b, c are constants and S,U,V are variables. In these rules,
  the same letter represents the same string. So, if S = acb,
  rule 3 tells us that aacbacbcb is a Huyn string.
  In rule 4, U and V represent Huyn strings, but they may be different.

  Problem 3: Write the  method
  ----------
  public static  double getLargest(double [] a, int low, int high)

   that returns the largest number in the array slice a[low:high].

  If low > high, it throws an IllegalArgumentException. Otherwise, it checks if
  the slice has 1 item. If so, it returns that value.

  If the slice has 2 or more items, it divides the slice into 2 equal subslices,
  computes the largestvalues of the 2 subslices and returns the largest 
  of the 2 values.

  Problem 4:  Write the method
  ----------
     public static void sort(String[] a)

  sorts the array a in increasing order. The method must be
  a short recursive program. Do not use quicksort or merge sort.
  It should be a ;lot shorter.

  Problem 5: Write the method
  ----------
     public static boolean isBalanced(String in)

  that returns true if the string in is a balanced string of
  parantheses and false if it is not.

   We define the balanced parentheses strings as follows:

    1. {} is a balanced parentheses string

    2. [] is a balanced parentheses string

    3. () is a balanced parentheses string

    4. If S is a balanced parentheses string, so is {S}

    5. If S is a balanced parentheses string, so is [S]

    6. If S is a balanced parentheses string, so is (S)

    7. If S and T are  balanced parentheses strings, so is ST

    In rule 7, S and T can be the same string or different ones.


   For example, the strings () , [()] , {([])} ,  ()[]  are 
  4 balanced strings.
  Keep in mind that the empty string is NOT a balanced string.
 
  Problem 6: Make the method
  ----------
     public static int binarySearch(double[] arr, double inq)

   recursive. The method returns -1 if arr == null or
   arr.length == 0. Otherwise, it will call the helper method
   
   private static int binarySearch(double[] a, double inq, int low, 
           int high)

   with low = 1 and high = a.length -1.

   The helper method searches the array slice a[low:high]  for
   an occurrence of inq. If it finds one, return the index i 
   where a[i] = inq.
   If not, return -1. The binary search method will be discussed 
   in class.

  Problem 7: Write the method
  ----------
   public static void printThePowerSet( String[] arr)

   that prints all subsets of arr.  If arr is null or empty,
   print
   {}

    The suggestion is to declare a static array list
   private static ArrayList<String> sets;

   and a helper method

   public static void powerSet( String[] arr, int n)

   Initially, public static void printThePowerSet( String[] arr)
   calls powerSet( arr, int 0);

   powerSet( String[] arr, int n)
   works as follows:

   if n = 0; it creates a ArrayList<String> for sets, adds the string
   {} to it, and calls powerSet( arr, 1);
   else if (n > arr.length) powerSet returns.
   Otherwise, powerSet takes each entry in sets, adds arr[i-1] 
   to the entry, and adds it to sets. Then calls powerSet( arr, n+1 ).

   For example if arr = { "Mark", "Bill", "Ali Baba"};
   when  powerSet( arr, 2 ) starts the execution, sets must be 
   the one below.
   For example if arr = { "Mark", "Bill", "Ali Baba"};
   when  powerSet( arr, 2 ) starts the execution, sets must be the one below.

   sets.get(0) = "{}"
   sets.get(1) = "Mark"

   The method will add arr[2-1] = "Bill" to each of the 2 entries and 
   add then to sets.
   So, when powerSet( arr, 2 ) calls powerSet( arr, 3 )
   sets must be

   sets.get(0) = "{}"
   sets.get(1) = "{\"Mark\"}"
   sets.get(2) = "{\"Bill\"}"
   sets.get(1) = "\"Mark\",\"Bill\"}"

   The size of sets doubles for each call.
   If arr = { 1, 2, 3} the method must print
   {}
   {1}
   {2}
   {1,2}
   {3}
   {1,3}
   {2,3}
   {1,2,3}

  Problem 8: Write the method 
  ----------
         public static void printArray(int[] arr, int i)

  that does the following:
 
  it returns if arr == null or i >= arr.length
  
  it calls printArray(a,0) if i < 0

  it prints recursively a[i], ..., a[a.length-1], each on a separate line, 
  if 0<= i < arr.length

  
  Problem 9: Write the method
  ----------

     public static double sum(double[] arr)

  that computes the sum of the items of the array arr.
  The method checks if arr is null or empty. If so, it throws an
  illegal argument exception otherwise it returns sum(arr, 0).

  The method sum(double[] arr) is not recursive, but the helper method
  private double sum(double[] arr, int i)
  is. The helper method returns the sum of all elements of arr from
  index i to the end of arr.
  You must write both methods.

  Problem 10: Write the method 
  -----------
  public static double powerOf(double x, int n)

  that returns x to the power of n by doing the smallest number of 
  multiplications. The program works as follows:

  if n==0 return 1;
  if n==1 return x;

  Otherwise, recursively compute x to the power n/2 and use it to compute
  x to the power n.   
     
  Below is the problem assignment:

  1.    Ariel Antunez         1, 4, 5, 6, 7 
  2.    Rolans Apinis         2, 4, 6, 8, 10
  3.    Richard Avenarius     1, 3, 5, 7, 9
  4.    David Barahona        2, 3, 5, 6, 8  
  5.    Oscar Barbosa         1, 5, 6, 7, 8

  6.    Jose Beliz Crespo     2, 3, 6, 7, 10
  7.    Yahn Bonet            1, 6, 7, 8, 9
  8.    David Castaneda       2, 3, 7, 8, 10
  9.    Maria Correa          1, 7, 8, 9, 10
 10.    Gabriela Curbelo      2, 4, 5, 7, 9

 11.    Brian Egger           1, 3, 5, 8, 10
 12.    Jacob Ehrlich         2, 4, 6, 7, 9
 13.    Raul Espinosa         1, 4, 6, 8, 10
 14.    Eduardo Gallardo      2, 4, 7, 8, 9
 15.    David Giles           1, 3, 4, 6, 7

 16.    Alexander Gomez       2, 5, 6, 7, 9
 17.    Brian Huici           1, 3, 4, 8, 9 
 18 .   Keegan Lee            2, 5, 6, 8, 10
 19.    Ernesto Leon          1, 4, 5, 7, 8
 20.    Arian Lopez           2, 5, 6, 8, 10

 21.    Joseph Marrero        1, 5, 6, 8, 9
 22.    Roel Marten           2, 5, 7, 8, 10
 23.    Eddy Mogollon         1, 3, 6, 9, 10
 24.    Cesar Nolasco Jr      2, 5, 8, 9, 10
 25.    Austin Nowak          1, 5, 7, 8, 10

 26.    Daniel Perez          2, 6, 7, 8, 9
 27.    Daniel Rivera         1, 3, 4, 5, 7
 28.    Michael Romero        2, 6, 7, 9, 10  
 29.    Kenny Roy             1, 3, 5, 8, 9
 30.    Ramon Sanchez         2, 4, 5, 6, 7

 31.    Isaac Smith           1, 4, 5, 7, 8
 32.    Kenneth Torres        2, 5, 6, 7, 10