Report # 1

    Problem

This problem comes from the area of computer science known as pattern-matching and was originally faced in its two dimensional form by Ulf Grenander at Brown University in 1977. While the one dimensional case has a "fast" solution, a "fast" solution to the two dimensional analog still remains an open problem. For the purposes of comparison of algorithms, we will look at the one dimensional case.

The input is a vector x of n floating-point numbers. The output is the maximum sum found in any contiguous sub-vector of the input. For instance, if the input vector contains the following ten elements

INDEX VALUE
0 31
1 -41
2 59
3 26
4 -53
5 58
6 97
7 -93
8 -23
9 84

then the program returns the sum of x[2..6], or 187. The problem is easy when all the numbers are positive; the maximum sub-vector is the entire input vector. It's also easy when all the inputs are negative; the maximum sub-vector is the empty vector, which has a sum of zero. The difficulty comes when some of the numbers are positive and some are negative: should we include a negative number in hopes that the positive numbers on either side will compensate for it?

An obvious program for this task iterates over all the pairs of integers i and j where 0<=i<=<n; for each pair the program computes the sum of x[i..j] and checks wheter that sum is greater than the maximum so far.

    Assignment

Design a solution to the above problem embodied in a Java method. Before you implement and run the solution, try to reason about how long it should take depending on the size of the array.

Implement the obvious, simple algorithm as a method in a JAVA application. Test your algorithm on the example above, on a vector of all positive number, and on a vector of all negative numbers. Generate random, floating-point vectors of reasonable size. What is "reasonable" -10, 100, 1000, 10000, 100000, 1000000, 10000000? (Note, an array of 10 million java floats will take up 40MB of swap space. You may have to use the -Xms, -Xmx flags to run memory intensive programs. See the java documentation.) At some point, you may realize that this algorithm isn't worth waiting around for. You need to generate a reasonable number (40?) of data points in a "reasonable" range. The definition of reasonable will depend on your algorithm, the computer you use, the other available memory, the load on the computer. So, you will need to experiment to arrive at a range. If you choose n to small, your data will be dominated by system overhead. If you choose n to large, you will be waiting around for a long, long time. Use the data points that you are able to get in a reasonable time to project estimates for larger values. Plot the data and include the plots in your report. 

Hand in a written report which includes:

    Rough Benchmarking

 

We will discover, in the course of the semester, that asymptotic charaterization is normally the first and best way to describe the execution-time behavior of a complex algorithm. However, actually measuring the time involved in a programs execution can give some practical insight into the more abstract analytical techniques.

Measuring the time involved in running a program is quite simple, doing it well is quite complex. We will use some simple measurement techniqes. The simplest idea is to record the time before running a program, then run the program, then record a second time measurement. If we subtract the first measurement from the second we have the elapsed time. The JAVA program below contains a method that searches an array for a specific value. We record the time with System.currentTimeMillis().

 

import java.util.* ;
public class BM {
    public static void main(String args[]) {
  
	int Asize = 1000000;
  	int Ainc =   100000;
  	for (int i = 0 ; i < 40 ; i++){
  	    
	    float count, sum, average;
  	    count = sum = average = 0 ;
  	    long startTime, endTime;
	    for(int j = 0 ; j < 3; j++) { // take the average of 3 runs
  		count += 1.0 ;
                //initialize a random array
  		float testvect[] = new float[Asize];
  		for(int k = 0; k < testvect.length;k++)
  		    testvect[k] = (float) ((2.0 * Math.random()) - 1.0);
		// clean things up
  		System.gc(); 
		startTime = System.currentTimeMillis(); // measure time 
  		boolean found = searchfor(((float)Math.random()),testvect);
  		endTime = System.currentTimeMillis();   // measure time
		// calculate elapsed time
  		sum  +=  (float) (endTime - startTime);
	    }
  	    System.out.println((sum/count) + " , ");
  	    Asize += Ainc;
  	}
    }
    static boolean searchfor(float value, float[] inArry) {
	boolean returnvalue = false;
  	for (int i = 0 ; i < inArry.length;i++)
  	    if (value == inArry[i]) returnvalue = true;
  	return returnvalue;
      }
}

 

When we plot the data generated by this experiment and fit a line to the data, we find that our "model" of linear (O(n)) execution time tracks the data. According to a linear fit of the data, 

msec = 0.00005694809365*n + 7.5

The above program's last data point was at an array of n==4900000 floats. Can we use our model to predict the run time at n = 10,000,000 floats? What will it be? How accurate will that prediction be when we compare it to a measured result?