CIS 121 April 14, 2000

RECALL!!!!! This is the last day of advising for Juniors, Seniors, and Graduate Students. Freshmen and Sophomores have one more week. But don't wait until the last minute.

Recall the ACM Banquet is April 22nd on the USS Alabama. ACM Elections are Monday.
We need to make a couple of other observations about linked lists. We have looked so far at a list in which each node had a pointer to the next node. We indicate the end of the list by the node whose pointer is null. In the examples we looked at we only considered adding a node at the front of the list (Stack) or at the end of the list (Queue). We did not take into account the datum field. So our lists were unordered lists.

To order the list we can use a similar approach to the task of deleting a node. When we delete a node, we start at the head of the list and traverse through the list until we find the node we are looking for. We had a Node variable called previous to keep track of the last node we examined. The Node variable current kept track of the current node we are examining. If we want to insert a datum into the list, then we can use this same idea to find the position where it should be inserted.

For example, if we want to place a node into the list in alphabetical order, then we would search until the datum we want to insert into the list is alphabetically between the datum in the node pointed to by previous and the node pointed to by current. Then we create a new node, have it point to the node pointed to by current, and then have the previous node point to the new node.

Another feature of the lists we looked at was there there was only one link field in each node. When we have only one link field in each node in the list, then the linked list is referred to as a singly-linked list. In many instances it would help if there were a way we could move backwards in the list. To do this we could create two link fields in each node, one to point to the previous node, and one to point to the next node. If we implement a list in which nodes have this property, then the linked list is referred to as a doubly-linked list. This gives us more flexibility.

Recursion

Recall that a very powerful feature of programming languages is recursion, the ability of a method to call itself. However, to understand recursion, one must first understand recursion.

There are three features of a well-formed recursive method.
  1. It calls itself (directly or indirectly).
  2. It has exit criteria by which it does something without making the recursive call.
  3. It works with a "smaller" problem or value each time that it is called so that it can make progress towards the exit criteria!
Let us look at some examples of recursion.

Factorial

Recall that n! is defined to be the product of all positive integers less than or equal to itself.

For example, 
2! = 2*1 = 2,
3! = 3*2*1 = 6,
4! = 4*3*2*1 = 24,
5! = 5*4*3*2*1 = 120
Notice that this function grows very fast, in fact it grows much faster than an exponential function.

We can implement this function very simply with a for loop. 
public class Fact {
   int n;
   int product;

   public Fact(int n) {
      this.n = n;
      product = 1;
   }

   public String toString() {
      for (int i=1;i<=n;i++)
         product *= i;
      return(n + "! = " + product);
   }

   public static void main(String[] args) {
      Fact myFact;

      myFact = new Fact(2);
      System.out.println(myFact);
      myFact = new Fact(3);
      System.out.println(myFact);
      myFact = new Fact(4);
      System.out.println(myFact);
      myFact = new Fact(5);
      System.out.println(myFact);

   }
}
You may download this Source Code to experiment with it.

The output of this program is the following. 

2! = 2
3! = 6
4! = 24
5! = 120
The factorial function can be defined in another way. Let n be a positive integer.

1) 1! = 1, and
2) n! = n*(n-1)! if n > 1.


It is clear that this definition produces the same results as the previous definition. 

2! = 2*1! = 2*1 = 2,
3! = 3*2! = 3*2 = 6,
4! = 4*3! = 4*6 = 24,
5! = 5*4! = 5*24 = 120
The second definition of n! is a recursive definition. Therefore the factorial of a positive integer can be computed recursively. Let us consider how this would work.

Recall that a method is recursive if it calls itself.

Consider a conversation between yourself and a method called factorial.

You: factorial, what is the value of 5!?

factorial: The value of 5! is 5 times the value of 4!.

You: factorial, what then is the value of 4!?

factorial: The value of 4! is 4 times the value of 3!.

You: factorial, we seem to be going in circles. What is the value of 3!?

factorial: Hey, I'm just doing what I'm told. The value of 3! is 3 times the value of 2!.

You: factorial, I'm really getting angry! What is the value of 2!?

factorial: Hey, don't blame me! The value of 2! is 2 times the value of 1!.

You: factorial, this is it! You better give me an answer! What is 1!?

factorial: Well, actually the value of 1! is 1.

You: Finally! So the value of 1! is 1.

factorial: That is correct.

factorial: Since the value of 2! is 2 times the value of 1!, and 1! is 1, 2! = 2.

You: Hey, cool!

factorial: Since the value of 3! is 3 times the value of 2!, and 2! is 2, 3! = 6.

You: Now we're getting somewhere!

factorial: Since the value of 4! is 4 times the value of 3!, and 3! is 6, 4! = 24.

You: Ok, now I get what you're doing!

factorial: Since the value of 5! is 5 times the value of 4!, and 4! is 24, 5! = 120.

You: Thank you, factorial.

factorial: You're welcome.

Let us implement the recursive definition of n!. 
public class Factorial {
   private int n;
   private int product;

   public Factorial(int n) {
      this.n = n;
   }

   public int factorial(int num) {
      if (num == 1)
         return(1);
      else 
         return(num*factorial(num-1));
   }

   public String toString() {
      return(String.valueOf(factorial(n)));
   }

   public static void main(String[] args) {
      Factorial myFactorial;

      myFactorial = new Factorial(2);
      System.out.println(myFactorial);
      myFactorial = new Factorial(3);
      System.out.println(myFactorial);
      myFactorial = new Factorial(4);
      System.out.println(myFactorial);
      myFactorial = new Factorial(5);
      System.out.println(myFactorial);
   }
}
You may download the Source Code.

Notice the important method here is factorial.

Within this method, we carry out the important parts of the above conversation. When we make a call to this method and send it a positive integer greater than 1, the method calls itself and sends 1 less than the value. This continues until the integer sent to the method is 1.

The Fibonacci Sequence

Another important mathematical concept that is well-suited to recursion is the Fibonacci Sequence.

The Fibonacci Sequence, Fn, is defined as follows.
1) F0 = 1
2) F1 = 1
3) If n > 1, then Fn = Fn-1 + Fn-2
We can easily implement an array to give n terms in the Fibonacci Sequence. 

public class Fibonacci {
   private int number;
   private int[] sequence;

   public Fibonacci(int n) {
      number = n;
      sequence = new int[n+1];
   }

   public void fibonacci() {
      sequence[0]=1;
      sequence[1]=1;
      for (int i=2;i<=number;i++) {
         sequence[i] = sequence[i-1] + sequence[i-2];
      }
      for (int i=0;i<=number;i++)
         System.out.println(sequence[i]);
   }

   public static void main(String[] args) {
      Fibonacci myFibonacci = new Fibonacci(5);

      myFibonacci.fibonacci();
   }
}
You may download the Source Code.

It is also natural to display the terms in this sequence using recursion since the sequence has a recursive definition. 
public class FibonacciSequence {
   int number;

   public FibonacciSequence(int n) {
      number = n;
   }

   public int fibonacci(int num) {
      if ((num==0) || (num==1))
         return(1);
      else
         return(fibonacci(num-1) + fibonacci(num-2));
   }

   public void displaySequence() {
      for (int i=0;i<=number;i++)
         System.out.println(String.valueOf(fibonacci(i)));
   }

   public static void main(String[] args) {
      FibonacciSequence myFibonacciSequence = new FibonacciSequence(5);

      myFibonacciSequence.displaySequence();
   }
}
You may download the Source Code.

Power

We can calculate the integer power of an integer using methods we have already used. Here is an example of a program to find the integer power of an integer. 
public class Power {
   int number;
   int exponent;
   int power;

   public Power(int n,int exponent) {
      number = n;
      this.exponent = exponent;
   }

   public String toString() {
      int power = number;

      for (int i=1;i<=exponent-1;i++)
         power *= number;

      return(String.valueOf(power));
   }

   public static void main(String[] args) {
      Power myPower = new Power(5,2);

      System.out.println(myPower);
   }
}
You may download the Source Code.

We can also implement it recursively. 
public class RecursivePower {
   int number;
   int exponent;
   int power;

   public RecursivePower(int n,int exponent) {
      number = n;
      this.exponent = exponent;
   }

   public int power(int exp) {
      if (exp==1)
         return(number);
      else
         return(number*power(exp-1));
   }

   public String toString() {
      return(String.valueOf(power(exponent)));
   }

   public static void main(String[] args) {
      RecursivePower myRecursivePower = new RecursivePower(5,2);

      System.out.println(myRecursivePower);
   }
}
You may download the Source Code.

Writing a String backwards

We can also recursively write a string backwards. 
public class WriteBackwards {
   String inputString;

   public WriteBackwards(String s) {
      inputString = s;
   }

   public void writeBackwards(String s,int index) {
      if (index>=0) {
         System.out.println(s.charAt(index));
         writeBackwards(s,index-1);
      }
   }

   public void display() {
      writeBackwards(inputString,inputString.length()-1);
   }

   public static void main(String[] args) {
      WriteBackwards myWriteBackwards = new WriteBackwards("galois");

      myWriteBackwards.display();
   }
}
You may download the Source Code.

Towers of Hanoi 
public class TowersOfHanoi {
   int numberOfDisks;

   public TowersOfHanoi(int n) {
      numberOfDisks = n;
   }

   public void tower(String fromTower,
                     String toTower,
                     String auxTower,
                     int n) {
      if (n==1)
         System.out.println("Move disk 1 from tower " + fromTower + " to tower " + toTower + ".");
      else {
         tower(fromTower,auxTower,toTower,n-1);
         System.out.println("Move disk " + n + " from tower " + fromTower + " to tower " + toTower + ".");
         tower(auxTower,toTower,fromTower,n-1);
      }
   }

   public static void main(String[] args) {
      TowersOfHanoi myTowersOfHanoi = new TowersOfHanoi(3);

      myTowersOfHanoi.tower("A","C","B",3);
   }
}
You may download the Source Code.

This is the output of the program. 
Move disk 1 from tower A to tower C.
Move disk 2 from tower A to tower B.
Move disk 1 from tower C to tower B.
Move disk 3 from tower A to tower C.
Move disk 1 from tower B to tower A.
Move disk 2 from tower B to tower C.
Move disk 1 from tower A to tower C.

Efficiency Measures of Algorithms

There are many ways to solve a particular problem. For example you saw last semester that there were different ways of sorting an array, bubble sort, selection sort, quicksort, etc.

However some methods are more efficience than others.

There is a mathematical notation that is used to describe how efficient an algorithm is. This is the Big O notation.

The big O notation gives us a way of comparing how efficient one algorithm is compared to another.

There are five major big O classifications that we will consider.
  1. O(1)
  2. O(N)
  3. O(log N)
  4. O(N log N)
  5. O(N2)
On Monday we will examine these classifications carefully. To prepare for this concept read Sections 12.2 and 12.3 in your textbook.