To Notes

CSC 212 -- 3/6/08

Review Questions

1. What is an abstract class; why would you want to use one?

   Ans: An abstract class is declared with the abstract keyword and cannot be instantiated. Its only use is to serve as the base class of another class that can be instantiated.

2. Write an abstract class named A that defines an abstract method f with signature (String, int) and return value boolean.

   public abstract class A
   {
       public abstract boolean f(String s, int n);
   }
   

3. What is an interface; why would you want to use one?

   Ans: An interface is a specification that a class must satisfy if it is to be compatable with existing software. The class that implements the interface must provide definitions of all the methods that the interface requires.

4. How does an interface differ from an abstract class?

   An interface only specifies required methods, it does not provide implementations. An abstract class may have abstract methods, which work exactly like the methods specified in an interface, but the abstract class may also have normal methods which have implementations that may be inherited or overridden.

5. Write an interface definition B that requires the method g with empty signature and void return value.

   public interface B
   {
      public void g( );
   }
   

6. Draw the recursion diagram and predict the output of this method:

   public static void g(int x, int y)
   {
       if (x + y >= 1)
       {
           g(x - 1, y - 1);
           System.out.println(x + y);
           g(x - 2, y - 1);
           System.out.println(x + " " + y);
           g(x - 2, y - 2);
       } 
   }
   

7. Show that the number of moves needed to solve the Towers of Hanoi puzzle with n disks is 2ⁿ - 1. In particular if the puzzle with 64 disks is solved at 1 second per move, the solution will take
   2⁶⁴ - 1 seconds = 58.5 billion years.

   Ans: Proof by induction. First the base case, which is to prove the result for n = 1. In this case, the number of moves is 2¹ - 1 = 1.

   Next the induction case, which is to assume the result for n - 1 and prove it for n. Now the recursive solution involves moving the top n - 1 disks from the From Peg to the Aux Peg (2^n-1 - 1 moves), moving the bottom ring from the From Peg to the To Peg (1 move) and moving n - 1 disks from the Aux Peg to the To Peg (2^n-1 - 1 moves). The total number of moves is

   (2^n-1 - 1) + 1 + (2^n-1 - 1) = 2 × 2^n-1 - 1 = 2ⁿ - 1

8. What is wrong with this code?

   public static void add(Card theCard)
   {
       for(int i = array.length; i <= 0; i--);
           array[i] = array[i - 1];
       theCard = array[0];
       return theCard;
   }
   

   Ans:
   1. The for loop should be

      for(int i = getCount( ); i >= 0; i--)
      

   2. There should be no semicolon at the end of the for loop line.

   3. There should be no return statement because the method is void.

9. What is wrong with this code?

   Deck playerA, playerB;
   gameOverFlag = playerA.getCount( ) == 0 || 
                  playerB.getCount == 0;
   

   Ans: playerA and playerB must be instantiated:

   playerA = new Deck( );
   playerB = new Deck( );
   

Project Proj6

• Go over the War and RunWar classes of Project Proj6.

More about Recursion

• The Hanoi2 Example shows a graphical display of the solution for up to 8 disks.

• See these examples for more examples of recursive algorithms in the Week 10 Examples:
  Maze1   Maze2   KnightsTour   FloodFill   QuickSort   FamilyTree

Practice Problems

1. Predict the order in which the cells in this maze are searched.
   x=7, y=4 is the start point.

   x=7, y=1 is the end point.

   The search order is left, right, up, down.

               3 
              1*2
               4
    012345678
   0*********
   1*     *E*
   2* * *   *
   3* * *****
   4* *   *S*
   5* * *   *
   6* * * * *
   7* * * * *
   8*********
   

   Stop when you reach the end point.

   Ans: The counting order is like this:

   1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R

               3 
              1*2
               4
    012345678
   0*********
   1*CBAJK*O*
   2*D*9*LMN*
   3*E*8*****
   4*F*765*1*
   5*G* *432*
   6*H* * * *
   7*I* * * *
   8*********
   

2. Predict the order in which the cells in this region are filled with the FloodFill algorithm.
   x=4, y=4 is the seed point.

   The search order is left, right, up, down.

               3 
              1*2
               4
   
    0123456789
   0**********
   1*  ***   *
   2* *   *  *
   3*  *  *  *
   4* * S  * *
   5* **  ** *
   6*   **   *
   7*        *
   8**********
   

   Stop when the entire region is filled.

   Ans: The counting order is like this:

   1 2 3 4 5 6 7 8 9 A B

    0123456789
   0**********
   1*  ***   *
   2* *768*  *
   3*  *54*  *
   4* *9123* *
   5* **BA** *
   6*   **   *
   7*        *
   8**********