COP 3337
  Section U05
  Spring 2017



                         MIDTERM EXAM ANSWERS
                         ====================

  QUESTIONS
  ---------

  Question 1. (15 points)

   // remove all figures in the array list list that are not squares
    public static void nothingButSquares(ArrayList<Figure> list)
    {
        // check for null list
        if (list == null)
            return;

        // we use the variable size because the size of the list
        // decreases after each removal
        int size = list.size();
        for (int i = 0; i < size; )
        {
            // get the figure at i
            Figure f = list.get(i);
            if ( ! (f instanceof Square))
            {
                // it is not a square
                list.remove(i);
                size--;
                // don't increase i because now i points to the next figure
                // in the list
            }
            else
                // all items up to and including i are squares
                i++; // increase i
        }

    } // end nothingButSquares


  Grading Criteria:
  -----------------

  The important thing in this problem is not to increase i when you
  remove an item beacuse when you remove item i, the old item i+1 
  is moved to location i. By increasing i, you don't process it.
 
  1. Skipping items: -6 points
  2. Treating lists like arrays, i.e. writing list[i], using
     length instead of lize, etc. : -3 points
  3. No loop: -5 points
  4. Not testing for null list: -2 points
  5. Style errors: up to -1.5 points
  6. Just trying : 2 points



  PS: If you think that your program works, try the driver below:


    public static void main(String[] args)
    {

        // form an array list
        ArrayList<Figure> pile = new ArrayList<>();
        pile.add(new Square(10.0));
        pile.add(null);
        pile.add(new Circle(10.0));
        pile.add(null);
        pile.add(new Circle(5.0));
        pile.add(null);
        pile.add(new Square(15.0));
        pile.add(null);

        // call the method
        nothingButSquares(pile);

        // print the reduced list
        for (Figure f : pile)
        {
            if (f == null)
                System.out.println("null");
            else if (f instanceof Square)
                System.out.println("Square");
            else
                System.out.println("Not a square");
        }
    } // end main


  Question 2. (20 points)

  1. F  2. T  3. F  4. F   5. T  6. F  7. F  8. T  9. F  10. T  11. T

  12. F  13. F  14. F  15. T  16. F  17. F  18. F  19. T  20. F

  Grading Criteria:
  -----------------

  1 point for each correct answer

  Question 3. (30 points)

  // this method recognizes if a string is Clarke
    public static boolean isClarke(String in)
    {
        // reject the null string
        if (in == null)
            return false;
        // accept the 2 base cases
        if (in.equals("bc") || in.equals("abab"))
            return true;
        // reject all other strings of length < 8,
        // the strings of odd length,
        // the strings that don't start with ab and all strings
        // that don't end in c
        int len = in.length();
        if (len < 8 || len % 2 == 1)
            return false;
        if ( ! in.substring(0,2).equals("ab") || in.charAt(len -1) != 'c')
            return false;
        
        // check rule 3
        
        // extract the 2 S's
        int mid = in.length() / 2;
        if (in.charAt(mid) == 'a')
        {
            // extract s1 and s2
            String s1 = in.substring(2,mid);
            String s2 = in.substring(mid+1, len -1);
            if (s1.equals(s2) && isClarke(s1))
                return true;
        }   
        
        // Check rule 4
        if (in.substring(len-2).equals("bc"))
        
            for (int i = 4; i < len - 4; i += 2)
            {
                //extract u and v
                String u = in.substring(2,i);
                String v = in.substring(i,len-2);
                if (isClarke(u) && isClarke(v))
                    return true;
            }    
        
        // in is not Clarke
        return false;
    }        

  Grading Criteria:
  -----------------

   1. Checking for null: 2 points
   2. The base cases: 2.5 points
   3. Rejecting the other small strings: 2 points
   4. Rejectiong odd strings: 2 points
   5. Case 3: 7.5 points
      5.1. Checking that in begins with "ab", has 'a' at the midpoint and
           'c' at the end : 2.5 points
      5.2. Extracting s1 and s2 correctly: 2.5 points
      5.3. The check for equality and the Clarkeness of s1 : 2.5 points 
   6. Case 4: 10 points
      6.1. Checking that in begins with "ab", and ends with "bc" : 2 points
      6.2. The loop: 3 points: -1 points for increment 1 
      6.3. Extract u and v : 2.5 points
      6.3. The recursive calls for u and v: 2.5 points 
   7. The final return false: 2 points
   8. Style: 2 points
   9. Syntax erros: -1 point for each occurrence
  10. Logical errors: at least -2 points per occurrence
  11. Useless statements: -1 point for each one
        
  Question 4. (15 points) 

  guess(6,4) = 360  

  Grading Criteria:
  -----------------

  1. For 360 : 15 points

  2. Wrong result, could be one error in simulation or calculation: 5 points

  3. Just trying : 2 points