Recursive Thinking

Classwork
Exercise 1:
Consider the following recursive algorithm for painting a square:

1. Given a square.
2. If the length of a side is less than 2 feet, then stop.
3. Divide the square into 4 equal size squares (i.e.,
draw a “plus” sign inside the square).
4. Paint one of these 4 small squares.
5. Repeat this procedure (start at step 1)
for each of the 3 unpainted squares.

If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

Exercise 2:

Exercise 3:

Exercise 4:
Consider the following recursive function.

public static int mystery(int a, int b) {
   if (b == 0)     return 0;
   if (b % 2 == 0) return mystery(a+a, b/2);
   return mystery(a+a, b/2) + a;
}

What are the values of mystery(2, 25) and mystery(3, 11)? Given positive integers a and b, describe what value mystery(a, b) computes. Answer the same question, but replace + with * and replace return 0 with return 1.

Programming Exercise:
Binary representation. Write a program IntegerToBinary_YI.java that takes a positive integer N (in decimal) from the command line and prints out its binary representation. Recall, you can use the method of subtracting out powers of 2. Instead, use the following simpler method: repeatedly divide 2 into N and read the remainders backwards. First, write a while loop to carry out this computation and print the bits in the wrong order. Then, use recursion to print the bits in the correct order.

Today

Recursion

Classwork: Paper and pencil
1. Write a recursive definition of xy (x raised to the power y), where x and y are integers and y > 0. Trace your recursive definition for x = 2 and y = 3.

January 21st, 2014

Maze solver by Robert von der Schmidt

Inheritance

An example:

A UML class diagram showing an inheritance relationship

public class Words
{
   //-----------------------------------------------------------------
   //  Instantiates a derived class and invokes its inherited and
   //  local methods.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      Dictionary webster = new Dictionary();

      System.out.println ("Number of pages: " + webster.getPages());

      System.out.println ("Number of definitions: " +
                          webster.getDefinitions());

      System.out.println ("Definitions per page: " +
                          webster.computeRatio());
   }
}

public class Book
{
   protected int pages = 1500;

   //----------------------------------------------------------------
   //  Pages mutator.
   //----------------------------------------------------------------
   public void setPages (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages accessor.
   //----------------------------------------------------------------
   public int getPages ()
   {
      return pages;
   }
}

public class Dictionary extends Book
{
   private int definitions = 52500;

   //-----------------------------------------------------------------
   //  Prints a message using both local and inherited values.
   //-----------------------------------------------------------------
   public double computeRatio ()
   {
      return (double) definitions/pages;
   }

   //----------------------------------------------------------------
   //  Definitions mutator.
   //----------------------------------------------------------------
   public void setDefinitions (int numDefinitions)
   {
      definitions = numDefinitions;
   }

   //----------------------------------------------------------------
   //  Definitions accessor.
   //----------------------------------------------------------------
   public int getDefinitions ()
   {
      return definitions;
   }
}

Inheritance Notes

• Inheritance is the process of deriving a new class from an existing one.
• One purpose of inheritance is to reuse existing software.
• The original class is called the parent class, superclass, or base class.
• Inheritance creates an “is-a” relationship between the parent and child classes.
• Java uses the reserved word extends to indicate that a new class is being derived from an existing class.
• Inheritance is a one-way street.

Visibility Modifiers

• Private methods and variables of the parent class cannot be referenced in the child class or through an object of the child class.
• Public visibility allows a derived class to reference it, but violates the principle of encapsulation.
• Protected visibility allows the class to retain some encapsulation properties.
• Protected visibility provides the best possible encapsulation that permits inheritance. However, the encapsulation is not as tight as if the variable or method were declared private, but it is better than if it were declared public.
• Modifiers list:
• public – visible anywhere
• protected – can only be applied to inner classes. Visible to any classes in the package and to children classes.
• private – can only be applied to inner classes. Visible enclosing class only.
• no modifier – default – visible to any classes in the same package.
• For the AP Computer Science A Exam a design question may required a student to develop a solution that includes all data declared private.

The Super keyword

• The reserved word super can be used in a class to refer to its parent class.
• Using the super reference, we can access a parent’s members.
• Like the this reference, what the word super refers to depends on the class in which it is used.
• A parent’s constructor can be invoked using the super reference. ( First line in the constructor )
• If no such call exists, Java will automatically make a call to super() at the beginning of the constructor.
• The super reference can also be used to reference other variables and meth- ods defined in the parent’s class.

public class Words2
{
   //-----------------------------------------------------------------
   //  Instantiates a derived class and invokes its inherited and
   //  local methods.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      Dictionary2 webster = new Dictionary2 (1500, 52500);

      System.out.println ("Number of pages: " + webster.getPages());

      System.out.println ("Number of definitions: " +
                          webster.getDefinitions());

      System.out.println ("Definitions per page: " +
                          webster.computeRatio());
   }
}

public class Book2
{
   protected int pages;

   //----------------------------------------------------------------
   //  Constructor: Sets up the book with the specified number of
   //  pages.
   //----------------------------------------------------------------
   public Book2 (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages mutator.
   //----------------------------------------------------------------
   public void setPages (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages accessor.
   //----------------------------------------------------------------
   public int getPages ()
   {
      return pages;
   }
}

public class Dictionary2 extends Book2
{
   private int definitions;

   //-----------------------------------------------------------------
   //  Constructor: Sets up the dictionary with the specified number
   //  of pages and definitions.
   //-----------------------------------------------------------------
   public Dictionary2 (int numPages, int numDefinitions)
   {
      super(numPages);

      definitions = numDefinitions;
   }

   //-----------------------------------------------------------------
   //  Prints a message using both local and inherited values.
   //-----------------------------------------------------------------
   public double computeRatio ()
   {
      return (double) definitions/pages;
   }

   //----------------------------------------------------------------
   //  Definitions mutator.
   //----------------------------------------------------------------
   public void setDefinitions (int numDefinitions)
   {
      definitions = numDefinitions;
   }

   //----------------------------------------------------------------
   //  Definitions accessor.
   //----------------------------------------------------------------
   public int getDefinitions ()
   {
      return definitions;
   }
}

Overriding Notes

• A child class can override (redefine) the parent’s definition of an inherited 
method.
• Constructors, however, are not inherited and cannot be overridden.
• Method overriding is a key element in object-oriented design.
• Method overriding allows two objects that are related by inheritance to use the same naming conventions for methods that accomplish the same general task in different ways.
• A method can be defined with the final modifier. A child class cannot override a final method. This technique is used to ensure that a derived class uses a particular definition of a method.
• The final modifier can also be applied to an entire class. A final class cannot be extended at all.

Shadowing

• If a variable of the same name is declared in a child class, it is called a shadow variable.
• To avoid confusion and logical errors, shadowing variables should be avoided.

Class Hierarchy

A UML class diagram showing a class hierarchy

• The child of one class can be the parent of one or more other classes, creating a class hierarchy.
• Common features should be located as high in a class hierarchy as is reasonably possible.
• All Java classes are derived, directly or indirectly, from the Object class.
• The toString and equals methods are inherited by every class in every 
Java program.
• Inheritance can be applied to interfaces so that one interface can be derived from another.
• Private members are inherited by the child class, but cannot be referenced directly by name. They may be used indirectly, however.
• Java’s approach to inheritance is called single inheritance.

Abstract Classes

• It represents a concept on which other classes can build their definitions.An abstract class cannot be instantiated.
• A class derived from an abstract parent must override all of its parent’s abstract methods, or the derived class will also be considered abstract.
• An abstract class is similar to an interface in some ways.
• However, unlike interfaces, an abstract class can contain methods that are not abstract.
• An abstract class can also contain data declarations other than constants.
• A class is declared as abstract by including the abstract modifier in the class header.
• Any class that contains one or more abstract methods must be declared as abstract.
• In abstract classes (unlike interfaces), the abstract modifier must be applied to each abstract method.
• A class declared as abstract does not have to contain abstract methods.
• Abstract classes serve as placeholders in a class hierarchy.
• If a child of an abstract class does not give a definition for every abstract method that it inherits from its parent, then the child class is also considered abstract.
• Note that it would be a contradiction for an abstract method to be modified as final or static.
• Because abstract methods have no implementation, an abstract static method would make no sense.

Interface Hierarchies

• The concept of inheritance can be applied to interfaces as well as classes.
• One interface can be derived from another interface.
• These relationships can form an interface hierarchy, which is similar to a class hierarchy.
• When a parent interface is used to derive a child interface, the child inherits all abstract methods and constants of the parent.
• Any class that implements the child interface must implement all of the methods.
• There are no visibility issues when dealing with inheritance between interfaces (as there are with protected and private members of a class), because all members of an interface are public.
• Class hierarchies and interface hierarchies do not overlap. That is, an interface cannot be used to derive a class, and a class cannot be used to derive an interface.

Designing for inheritance
▪ Every derivation should be an is-a relationship. The child should be a more specific version of the parent.
▪ Design a class hierarchy to capitalize on reuse, and potential reuse in the future.
▪ As classes and objects are identified in the problem domain, find their commonality. Push common features as high in the class hierarchy as appropriate for consistency and ease of maintenance.
▪ Override methods as appropriate to tailor or change the functionality of a child.
▪ Add new variables to the child class as needed, but don’t shadow (redefine) any inherited variables.
▪ Allow each class to manage its own data. Therefore use the super reference to invoke a parent’s constructor and to call overridden versions of methods if appropriate.
▪ Use interfaces to create a class that serves multiple roles (simulating multiple inheritance).
▪ Design a class hierarchy to fit the needs of the application, with attention to how it may be useful in the future.
▪ Even if there are no current uses for them, override general methods such as toString and equals appropriately in child classes so that the inherited versions don’t cause unintentional problems later.
▪ Use abstract classes to specify a common class interface for the concrete classes lower in the hierarchy.
▪ Choosing which classes and methods to make abstract is an important part of the design process. You should make such choices only after careful consideration. By using abstract classes wisely, you can create flexible, extensible software designs.
▪ Use visibility modifiers carefully to provide the needed access in derived classes without violating encapsulation.
▪ Using the final modifier to restrict inheritance abilities is a key design decision.

Homework:
Visit edmodo.com to write a paragraph about the recursive function algorithm used to solve the maze.

Recursion

Recursion

We say that a method is recursive when it calls itself.

A good analogy would be when we define a word with the word itself. Take a look at this example:

companion: A person who accompanies or associates with another; a comrade.

In algebra: composite function f(f(x))

A recursive program requires two parts:
1. The non-recursive part, the base case, which lets the recursion eventually end.
2. The recursive part: calling itself.

Indirect recursion: a method invokes another method, eventually resulting in the original method being invoked again.

    public int factorial(int num)
    {
        if ( num "less than or equal to" 1 ) return 1;
        else return (num * factorial(num-1));
    }

Happy New Year!!

Welcome back!

Classwork:

“Abstract Classes” already posted.

Students presentation/discussions about the following assignments:

1. Create a class DataSet of BankAccounts. The constructor creates an ArrayList. Write the test class to add, delete and print bank accounts.

2. Create a class Purse that contains an ArrayList of Coin(s). Write the test class to add, delete, and print coins.
Modify the Purse class to be implemented with ArrayList class and to use a for-each loop.
Implement the following methods in the Purse class:

/**
      Counts the number of coins in the purse
      @return the number of coins
   */
   public int count()
   {
     
   }

   /**
      Tests if the purse has a coin that matches
      a given coin.
      @param aCoin the coin to match
      @return true if there is a coin equal to aCoin
   */
   public boolean find(Coin aCoin)
   {

   }

   /**
      Counts the number of coins in the purse that match
      a given coin.
      @param aCoin the coin to match
      @return the number of coins equal to aCoin
   */
   public int count(Coin aCoin)
   {

   }

   /**
      Finds the coin with the largest value. 
      (Precondition: The purse is not empty)
      @return a coin with maximum value in this purse
   */
   Coin getMaximum()
   {

   }

Homework:
Self-review questions 7.1 through 7.8
1 Question on edmodo.com

Inheritance
Method behavior

Base and Derived classes are simple classes with one constructor and two methods

Constructors and Methods

Study the code and the output from the driver class. Make conclusions and post them in edmodo.com

Constructor behavior

Study the code and the output from the driver class. Make conclusions and post them in edmodo.com

Classwork:
Implement an application similar to the one above to show:

1. Calls to constructors with and without “super”
2. Calls to methods with and without “super”
3. Polymorphism – late binding
4. Do not forget to keep your code well documented with clear explanations

Assignments:
Self-Review 7.1 through 7.8
Programming Project 7.5

Visit edmodo.com