Thursday July 27, 2000

Quiz 29 - Final Quiz!

1. In an array of size n, about how many subarrays will have to be examined in order to find the element we are looking for using the Binary Search technique?

2. What is the Big-O measure of the BubbleSort?

3. What is the Big-O measure of the QuickSort?

4. When an array is sent as a parameter to a method, is it sent by value or by reference?
































Let's reiterate some of the things we said yesterday. Recall that I mentioned a couple of example methods using pass by reference.

Problem

Given two int arrays of the same size, form the sum of those arrays, that is form a third array whose entries are the sum of the corresponding entries in the other two arrays.

We looked at the following two methods for solving this problem.

One way was with the following method. 

public void add(int[] a,int[] b,int[] c) {
   for (int counter=0;counter<a.length;counter++)
      c[counter] = a[counter] + b[counter];
}
So if we have two int arrays of the same size, a and b, and an empty array of that size, c, then we would make the following call. 

add(a,b,c);
Note that I have deliberately used the same name for the formal parameters and the actual parameters. This is not a problem because the lifetime of the formal parameters is the lifetime of the method. That is, formal parameters only have block scope.

Another more intuitive way of writing this method would be the following. 

public int[] add(int[] a,int[] b) {
   int[] c = new int[a.length];

   for (int counter=0;counter<a.length;counter++)
      c[counter] = a[counter] + b[counter];

   return(c);
}
Let's see these two in action. 

public class Example1 {

   public static void add(int[] a,int[] b,int[] c) {
      for (int counter=0;counter<a.length;counter++)
         c[counter] = a[counter] + b[counter];
   }

   public static int[] add(int[] a,int[] b) {
      int[] c = new int[a.length];

      for(int counter=0;counter<a.length;counter++)
         c[counter] = a[counter] + b[counter];

      return(c);
   }

   public static void main(String[] args) {
      int[] a = {1,2,3};
      int[] b = {2,0,1};

      int[] c = new int[a.length];

      Example1.add(a,b,c);

      for (int counter=0;counter<c.length;counter++)
         System.out.println("c[" + counter + "] = " + c[counter] + ".");

      c = Example1.add(a,b);

      for (int counter=0;counter<c.length;counter++)
         System.out.println("c[" + counter + "] = " + c[counter] + ".");
   }

}
The output of this code is 

c[0] = 3.
c[1] = 2.
c[2] = 4.
c[0] = 3.
c[1] = 2.
c[2] = 4.
We have also talked about the Binary Search technique. Let's reiterate the important parts of this technique.

We begin with a sorted array.

We examine the element in the middle of the array to see if it is the element we are looking for. If it not, then by comparison we can determine if the element is at a smaller smaller than the middle or larger than the middle. When then examine the half that has the element we are looking for and look in the middle of it. We repeat this process until we find the element we are looking for or the low marker passes the high marker, that is the element is not in the array.

So the algorithm would be 

1. Let low be the position of the first element in the array.

2. Let high be the position of the last element in the array.

3. Repeat the following steps until the element is found or low > high

      Let middle be the average of low and high

      If the element located at that position of the array is the one
      we're looking for, then stop.

      If the element we are looking for is before the element in the
      middle then
         let high = middle
      else if the element we are looking for is after the element in
      the middle then
         let low = middle
Starting with an array of n elements we will have to search through approximately log2n subarrays until we find the element we are looking for.

To see another example of using arrays (which may be a bonus question) consider the following problem.

Four friends, Evariste, Niels Henrik, Fred, and Esther are standing outside a store. Evariste goes into the store and returns with 3 eggs, 4 peices of gum, and 1 bag of flour. Esther asks him how much each of the items costs, but Evariste won't tell her. All that he will tell her is that he spent $4.50.

Niels Henrik then goes into the store and returns with 4 eggs, 2 peices of gum, and 1 bag of flour. Again, he won't tell Esther how much each item costs. He will only tell her that he spent $3.33.

Fred then goes into the store and returns with 1 egg, 2 peices of gum, and 2 bags of flour. He won't tell Esther how much each item costs, but will tell her that he spent $2.60.

The guys think they have successfully kept Esther from figuring out how much each item costs. But much to their surprise she pulls out a peice of paper and a pencil and in a few minutes tells the guys approximately how much each items costs.

How does she do it?

We can answer that question by making the following definitions.

Let x be the price of one egg in cents.

Let y be the price of one peice of gum in cents.

Let z be the prices of one bag of flour in cents.

Then the following equations represent the three purchases. 

3x + 4y +  z = 450
4x + 2y +  z = 333
 x +  y + 2z = 260
One technique used to solve for x, y, and z is called Gauss-Jordan elimination. It involves taking the coefficients from these equations and placing them into an array. 

3 4 1 450
4 2 1 333
1 1 2 260
We may perform each of the following actions without disturbing the values of x, y, and z.

  • We may multiply any row by a non-zero constant.

  • We may replace any row by its sum with a non-zero multiple of another row. Using this technique we can transform the first three rows and columns into the following array. 

    1 0 0
0 1 0
0 0 1
    Then the entries in the fourth column will be, respectively, x, y, and z.