To Notes

CSC 212 -- 3/11/08

Review Questions

1. Draw the recursion tree for Towers of Hanoi with three disks.

   Ans: Here is the solution.

2. In what order does the FloodFill algorithm fill this region?

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

   The start point is x=5,y=5 and the fill order is left, down, right, up.

   Ans: If counting is in this order:

   123456789ABCDEFGH

   and the fill order is
   4 1*3 2
   this is the solution:

    0123456789
   0**********
   1* *      *
   2**H***   *
   3*BCEFG*  *
   4*65432*  *
   5*7A**1*  *
   6*89* *   *
   7****     *
   8*        *
   9**********
   

3. Draw the family tree produced by this java code. What is the output?

   public static void main(String[ ] args)
   {
       Person p = new Person("R");
       p.addChild(new Person("M"));
       p.addChild(new Person("Q"));
       p.getChild(1).addChild(new Person("L"));
       p.getChild(1).getChild(0).addChild(new Person("Y"));
       p.addChild(new Person("A"));
       p.getChild(2).addChild(new Person("K"));
       p.getChild(1).addChild(new Person("X"));
       p.getChild(0).addChild(new Person("J"));
       p.getChild(0).addChild(new Person("W"));
       p.getChild(0).getChild(0).addChild(new Person("B"));
       p.getChild(0).getChild(1).addChild(new Person("U"));
       p.getChild(1).getChild(0).addChild(new Person("T"));
       System.out.println(p);
   }
   

   Ans: Indentation means child:

                          R
             ____________/|\_____________
            0|           1|            2|
             M            Q             A
           0/1\         0/1\           0| 
           /   \        /   \           |  
          J     W      L     X          K
          |     |     / \               
          B     U    Y   T
   

   Output: R M J B W U Q L Y T X A K, one letter per line.

The KnightsTour Example

• Look at the KnightsTour Example: KnightsTour.java

Review for Final

• Final Review Guide

• Final Review Questions

• Sample Final Exam