To Notes

CSC 212 -- 3/4/08

Review Question

1. Find the errors?

   Scanner s = new Scanner("flights.txt");
   String origToFind = s.nextLine( );
   for(int i = 0; i <= f.length && f[i] != null; j++)
       if (f.getOrig( ) == origToFind)
           System.out.println(f.arrive);
   

   Ans:
   1. The Scanner constructor call should pass not pass in "flights.txt", it should pass in new FileReader("flights.txt");

   2. f.length should be f.length -1.

   3. j++ should be i++.

   4. Don't use == for comparing strings, use equals like this
      if (f.getOrig( ).equals(origToFind))

   5. Don't use f.arrive (arrive is private), use f.getArrive( ).

Project Proj6

• Go over the ShuffleableDeck class of Project Proj6.

Abstract Classes

• An abstract class is a class that is declared with the abstract keyword; it cannot instantiate objects.

• An abstract class is used as a base class to define derived classes. These derived classes can instantiate objects (provided that they are not themselves defined as abstract).

• For example, the class Reader in the java.io package is an abstract class.

• The Reader class defines the read and close methods that are inherited by any derived classes.

• Classes derived from the Reader class in the JCL:
  BufferedReader   CharArrayReader   FileReader   FilteredReader

  InputStreamReader   PipedReader   StringReader

• The Speaker Example: Animal.java   Speaker.java   Cat.java   Dog.java   TestSpeaker.java

• See the Java Class Libraries for other examples of interfaces.

Interfaces

• An interface is a way to inforce a sort of uniformity among a set of, at first glance, disparate classes.

• An interface is a contract to insure that a class is compatible with existing software.
  1. The class agrees to provide definitions for each method required by the interface.

  2. The software provider insures that if the methods of the interface are implemented, the software will work as advertised.

• The ArraySort Example: Person.java   ArraySort.java

• To allow the Arrays.sort method to sort the Person array p, the class Person must implement the Comparable interface; the Comparable interface requires that a compareTo method is supplied for the class.

• The Arrays class insures that if a objects are instantiated from a class that implements Comparable, Arrays.sort (the existing software) can sort the array.

• See the Java Class Libraries for other examples of interfaces.

• The Speaker Example: Animal.java   Speaker.java   Cat.java   Dog.java   TestSpeaker.java

• A class may implement more than one interface.

• An interface may inherit a base interface.

• Interfaces are a substitute for multiple inheritance.

Recursion

• Recursion is the practice of allowing a method to call itself. A recursive method is a method that calls itself.

• List Example:   List.java

• The List Example recursion diagram. An output is shown to the left if it occurs before a recursive call; it is listed to the right if it occurs after a recursive call.

• To determine the order of activations, terminations and outputs
  1. Pretend that you are an ant crawling around the tree counterclockwise.

  2. Keep a left leg always in contact with the tree.

  3. List an activation the first time the recursive call is encountered.

  4. List an output when it is encountered.

  5. List a termination the last time the recursive call is encountered.

• What happens if the order of the two statements

  printList(n - 1);
  System.out.println(n);
  

  in the if statement is reversed? Here is the recursive diagram for the reversed case.

• To avoid an infinite loop, each recursive function call must have a case where it does not call itself.

• The goal of the Towers of Hanoi puzzle is to move the disks from Peg1 to Peg2, using Peg3 as an auxilliary peg. A disk can never be placed on a disk that is smaller than itself.

• Here is a recursive solution for n disks:
  1. Move the top n - 1 disks from Peg 1 to Peg 3.

  2. Move the bottom disk from Peg 1 to Peg 2.

  3. Move the n - 1 disks from Peg 3 to Peg 2.

• The Hanoi1 Example computes the solution recursively.

• Predict the output of Hanoi1. Here is are recurrence diagrams for two disks and three disks. These links also show the sequence of activations, terminations and outputs.

• The Hanoi2 Example shows a graphical display of the solution.

• Predict the output of this RecursiveTrace.java with its recurrence diagram.

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

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.

   Stop when you reach the end point.

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.

   Stop when the entire region is filled.

3. Use the QuickSort algorithm to sort this list:
   70   15   92   51   39   45   63