Category Archives: Lesson

Chapter 8: Merge Sort

Merge Sort
The merge sort algorithm, another recursive sort algorithm, sorts a list by recursively dividing the list in half until each sublist has one element and then recombining these sublists in order.

General Strategy:
• Begin by dividing the list in two roughly equal parts and then recursively calling itself with each of those lists.
• Continue the recursive decomposition of the list until the base case of the recursion is reached, where the list is divided into lists of length one, which are by definition sorted.
• Then, as control passes back up the recursive calling structure, the algorithm merges into one sorted list the two sorted sublists resulting from the two recursive calls.

Example:
Let’s look at the recursive decomposition portion of the algorithm.
The merge portion of the algorithm would then recombine the list.

Merge-sort-example-300px

Merge Sort Code

wiki media

wiki media

Assignment
1. The merge sort: Trace the indices for the given data:
int[] grades = {3,2,5,2};
Is it a stable sort? Explain
Use the code to supports your answer.

Good resources:

Screen Shot 2015-02-09 at 3.01.25 PM

These are two good video with details and mathematical analysis:

Chapter 8: Recursive Binary Search

Program: Implement Binary search in java using recursive algorithm.

A binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Every recursion eliminates half of the remaining possibilities. This makes binary searches very efficient – even for large collections.

Binary search requires a sorted collection. Also, binary searching can only be applied to a collection that allows random access (indexing).

Worst case performance: O(log n)

Best case performance: O(1)

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new array. Typically the array’s size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

Chapter 8: Recursive Thinking

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:
rec1

rec2

Exercise 3:
rec3

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.

Chapter 8: Recursion – x^y & i*j


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.

2. Write a recursive definition of i * j (integer multiplication), where i > 0. Define the multiplication process in terms of integer addition. For example, 4 * 7 is equal to 7 added to itself 4 times.

Chapter 8: Recursion Intro Part 2

Intro to Recursion

A simple example from stackoverflow with OOD:



    class Calculation
    {
        int fact(int n)
        {
            int result;

           if(n==1)
             return 1;

           result = fact(n-1) * n;
           return result;
        }
    }

    public class Factorial
    {
         public static void main(String args[])
         {
           Calculation obj_one = new Calculation();

           int a = obj_one.fact(4);
           System.out.println("The factorial of the number is : " + a);
         }
    }

factorial1

Assignments:
1. Use the same visual representation as the one above for 4!

fibRec

2. Modify the method that calculates the sum of the integers between 1 and N shown in this chapter. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2 + 1) to N. Trace your solution using an N of 7.


3. Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. An iterative version of this method was part of the RationalNumber class presented in Chapter 4.

Rational 


//********************************************************************
//  Rational.java       Author: Lewis/Loftus/Cocking
//
//  Represents one rational number with a numerator and denominator.
//********************************************************************

public class Rational
{
   private int numerator, denominator;

   //-----------------------------------------------------------------
   //  Sets up the rational number by ensuring a nonzero denominator
   //  and making only the numerator signed.
   //-----------------------------------------------------------------
   public Rational (int numer, int denom)
   {
      if (denom == 0)
         denom = 1;

      // Make the numerator "store" the sign
      if (denom < 0)
      {
         numer = numer * -1;
         denom = denom * -1;
      }

      numerator = numer;
      denominator = denom;

      reduce();
   }

   //-----------------------------------------------------------------
   //  Returns the numerator of this rational number.
   //-----------------------------------------------------------------
   public int getNumerator ()
   {
      return numerator;
   }

   //-----------------------------------------------------------------
   //  Returns the denominator of this rational number.
   //-----------------------------------------------------------------
   public int getDenominator ()
   {
      return denominator;
   }

   //-----------------------------------------------------------------
   //  Returns the reciprocal of this rational number.
   //-----------------------------------------------------------------
   public Rational reciprocal ()
   {
      return new Rational (denominator, numerator);
   }

   //-----------------------------------------------------------------
   //  Adds this rational number to the one passed as a parameter.
   //  A common denominator is found by multiplying the individual
   //  denominators.
   //-----------------------------------------------------------------
   public Rational add (Rational op2)
   {
      int commonDenominator = denominator * op2.getDenominator();
      int numerator1 = numerator * op2.getDenominator();
      int numerator2 = op2.getNumerator() * denominator;
      int sum = numerator1 + numerator2;

      return new Rational (sum, commonDenominator);
   }

   //-----------------------------------------------------------------
   //  Subtracts the rational number passed as a parameter from this
   //  rational number.
   //-----------------------------------------------------------------
   public Rational subtract (Rational op2)
   {
      int commonDenominator = denominator * op2.getDenominator();
      int numerator1 = numerator * op2.getDenominator();
      int numerator2 = op2.getNumerator() * denominator;
      int difference = numerator1 - numerator2;

      return new Rational (difference, commonDenominator);
   }

   //-----------------------------------------------------------------
   //  Multiplies this rational number by the one passed as a
   //  parameter.
   //-----------------------------------------------------------------
   public Rational multiply (Rational op2)
   {
      int numer = numerator * op2.getNumerator();
      int denom = denominator * op2.getDenominator();

      return new Rational (numer, denom);
   }

   //-----------------------------------------------------------------
   //  Divides this rational number by the one passed as a parameter
   //  by multiplying by the reciprocal of the second rational.
   //-----------------------------------------------------------------
   public Rational divide (Rational op2)
   {
      return multiply (op2.reciprocal());
   }

   //-----------------------------------------------------------------
   //  Determines if this rational number is equal to the one passed
   //  as a parameter.  Assumes they are both reduced.
   //-----------------------------------------------------------------
   public boolean equals (Rational op2)
   {
      return ( numerator == op2.getNumerator() &&
               denominator == op2.getDenominator() );
   }

   //-----------------------------------------------------------------
   //  Returns this rational number as a string.
   //-----------------------------------------------------------------
   public String toString ()
   {
      String result;

      if (numerator == 0)
         result = "0";
      else
         if (denominator == 1)
            result = numerator + "";
         else
            result = numerator + "/" + denominator;
    
      return result;
   }

   //-----------------------------------------------------------------
   //  Reduces this rational number by dividing both the numerator
   //  and the denominator by their greatest common divisor.
   //-----------------------------------------------------------------
   private void reduce ()
   {
      if (numerator != 0)
      {
         int common = gcd (Math.abs(numerator), denominator);

         numerator = numerator / common;
         denominator = denominator / common;
      }
   }

   //-----------------------------------------------------------------
   //  Computes and returns the greatest common divisor of the two
   //  positive parameters. Uses Euclid's algorithm.
   //-----------------------------------------------------------------
   private int gcd (int num1, int num2)
   {
      while (num1 != num2)
         if (num1 > num2)
            num1 = num1 - num2;
         else
            num2 = num2 - num1;

      return num1;
   }
}

[collapse]

In a class called DivisorCalc, define a static method called gcd that accepts two integers, num1 and num2. Create a driver to test your implementation. The recursive algorithm is defined as follows:

gcd (num1, num2) is num2 if num2 <= num1 and num2 divides num1

gcd (num1, num2) is gcd (num2, num1) if num1 < num2

gcd (num1, num2) is gcd (num2, num1%num2) otherwise

4. Design and implement a recursive program, Pascal_YI.java to determine and print the Nth line of Pascal’s Triangle, as shown below. Each interior value is the sum of the two values above it. Hint: use an array to store the values on each line.

pascal

Chapter 8: Rob’s maze solver Inheritance

January 21st, 2014

Maze solver by Robert von der Schmidt

mazesolver

Inheritance

An example:

Screen Shot 2014-01-21 at 12.40.23 AM

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

Screen Shot 2014-01-21 at 12.40.50 AM

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.

Chapter 8: Recursion Intro Part 1


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.

indirectRecursion

Recursion vs. Iteration
There is always a non-recursive solution for all the problems done in this chapter. Recursion has the overhead of multiple method invocations and, in many cases, presents a more complicated solution than its iterative counterpart.

A programmer must learn when to use recursion and when not to use it. Determining which approach is best depends on the problem being solved. All problems can be solved in an iterative manner, but in some cases the iterative version is much more complicated. Recursion, for some problems, allows us to create relatively short, elegant programs.

An example of a recursive method to calculate the factorial of a number:

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

factorial1

Classwork:

Visit edmodo.com to work on the following exercises.

1. Write a class, NSum_YI.java that recursively calculates the sum of numbers 0 to N. Write a driver to test your program.

2. Use paper and pencil
Write a recursive definition of x^y (x raised to the power y), where x and y are integers and y less than or = 0. Trace your recursive definition for x = 2 and y = 3 similar to the illustration above.

3. Write a recursive definition of i * j (integer multiplication), where i less than 0. Define the multiplication process in terms of integer addition. For example, 4 * 7 is equal to 7 added to itself 4 times.

Chapter 7: Abstract Class Exercise

Happy New Year!!
new-year-gif
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

Chapter 7: Inheritance – Abstract Classes

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.

Homework:
Read pages 382 through 419 and do exercises MC 7.1 through 7.10 and SA 7.3 and 7.4

giphy

All source: Java Software Solutions by Lewis, Loftus and Cocking