Thread: Rather beginner level programming; need assistance.

I am trying to code my program to populate three different text files with randomly generated integers. The amount of integers in the text files are 10, 10 000, and 1 000 000. So the 'ten.txt' file will have 10 different, randomly generated numbers between 1 and 9. The '10k.txt' file will have 10,000 randomly generated numbers between 1 and 9,999 (and so on for the million file).

My program first populates the text files and then reads them back into three respective arrays. Each array is then ran three times against each of the four algorithms that I am including with my code. I then need to take an average of the three different running times for each of the three arrays (we are studying algorithm analysis).

I have always had difficulty understanding constructors so I would expect mine to be suspect.

I currently have the 10k and 1m text files properly filled, but for some reason, my 10-integer file stays blank. I am also having trouble reading the working files (10k/1m) back into their respective arrays.

I have two classes, ,my driver (main) and Algorithm (methods/algorithms). My main is by far still a rough draft as I recently made huge changes to accommodate the changing assignment.

Refer to post 3 for code.

import java.io.IOException;
 
 
public class driver {
 
	public static void main(String[] args) throws IOException{
 
		long startTime, endTime, average;
		System.out.println("Started.");
 
		//create new algorithm object and populate text files
		Algorithm algo = new Algorithm();
		algo.populateFiles();
 
		System.out.println("Starting algorithms.");
 
		//uses 10.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(algo.tenArray);
			maxSubSum2(algo.tenArray);
			maxSubSum3(algo.tenArray);
			maxSubSum4(algo.tenArray);
			endTime = System.currentTimeMillis();
			System.out.println("Algorithm 1 took " + (endTime - startTime) + " nanoseconds.");
			average += endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " nanoseconds.");
 
		//uses 10k.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(algo.tenkArray);
			maxSubSum2(algo.tenkArray);
			maxSubSum3(algo.tenkArray);
			maxSubSum4(algo.tenkArray);
			endTime = System.currentTimeMillis();
			System.out.println("Algorithm 2 took " + (endTime - startTime) + " nanoseconds.");
			average += endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " nanoseconds.");
 
		//uses 10m.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(algo.tenmArray);
			maxSubSum2(algo.tenmArray);
			maxSubSum3(algo.tenmArray);
			maxSubSum4(algo.tenmArray);
			endTime = System.currentTimeMillis();
			System.out.println("Algorithm 3 took " + (endTime - startTime) + " nanoseconds.");
			average += endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " nanoseconds.");
	}				
}

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;
 
 
public class Algorithm {
 
	//create arrays
	int[] tenArray = new int[9];
	int[] tenkArray = new int [9999];
	int[] tenmArray = new int [999999];
 
	//constructor
	public Algorithm(){
 
	}
 
	//algorthm 1
	//cubic maximum contiguous subsequence sum algorithm
	public static int maxSubSum1(int [] a){
		int maxSum = 0;
 
		for(int i = 0; i < a.length; i++){
			for(int j = i; j < a.length; j++){
				int thisSum = 0 ;
 
				for(int k = i; k <= j; k++){
					thisSum += a[k];
 
					if(thisSum > maxSum){
						maxSum = thisSum;
					}
				}
			}
		}
		return maxSum;
	}
 
	//algorithm 2
	//quadratic maximum contiguous subsequence sum algorithm
	public static int maxSubSum2(int [] a){
		int maxSum = 0;
 
		for(int i = 0; i < a.length; i++){
			int thisSum = 0;
 
			for(int j = i; j < a.length; j++){
				thisSum += a[j];
 
				if(thisSum > maxSum){
					maxSum = thisSum;
				}
			}
		}
		return maxSum;
	}
 
	//algorithm 3
	//recursive maximum contiguous subsequence sum malgorithm.
	//finds maximum sum in subarray spanning a[left...right].
	//does not attemmpt to maintain actual best sequence
	private static int maxSumRec(int [] a, int left, int right){
 
		if(left == right){ //base case
			if(a [left] > 0){
				return a[left];
			}
			else {return 0;}
			}
 
		int center = (left + right) /2;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center + 1, right);
 
		int maxLeftBorderSum = 0, leftBorderSum = 0;
		for(int i = center; i >= left; i--){
			leftBorderSum += a[i];
			if(leftBorderSum > maxLeftBorderSum){
				maxLeftBorderSum = leftBorderSum;
			}	
		}
 
		int maxRightBorderSum = 0, rightBorderSum = 0;
		for(int i = center + 1; i <= right; i++){
			rightBorderSum += a[i];
			if(rightBorderSum > maxRightBorderSum){
				maxRightBorderSum = rightBorderSum;
			}
		}
		return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
	}
 
	private static int max3(int a, int b, int c) {
	    return a > b ? (a > c ? a : c) : (b > c ? b : c);
	}
 
	//driver for divide-and-conquer maximum contiguous subsequence sum algorithm
	public static int maxSubSum3(int [] a){
		return maxSumRec(a, 0, a.length - 1);
	}
 
	//algorithm 4
	//linear-time maximum contiguous subsequence sum algorithm
	public static int maxSubSum4(int [] a){
		int maxSum = 0, thisSum = 0;
 
		for(int j = 0; j < a.length; j++){
			thisSum += a[j];
 
			if(thisSum > maxSum){
				maxSum = thisSum;
			}
			else if(thisSum < 0){
				thisSum = 0;
			}
		}
		return maxSum;
	}
 
	//method for reading from the text files into arrays
	public void readFiles() throws IOException{
 
		int i;
		String fileName = null;
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(new File(fileName));
 
		i = 0;
		fileName = "10.txt";
		while (scan.hasNext()){
			tenArray[i] = scan.nextInt();
			i++;
		}
 
		i = 0;
		fileName = "10k.txt";
		while (scan.hasNext()){
			tenkArray[i] = scan.nextInt();
			i++;
		}
 
		i = 0;
		fileName = "1m.txt";
		while (scan.hasNext()){
			tenmArray[i] = scan.nextInt();
			i++;
		}
	}
 
	//method for printing to the text files
	public void populateFiles() throws IOException{
		String fileName = "10.txt";
 
		//create new randomgenerator object
		Random randomGenerator = new Random();
 
		//populate 10.txt
		@SuppressWarnings("resource")
		PrintWriter tenOut = new PrintWriter(fileName);
		for(int i = 0; i < 10; i++){
			tenOut.println(randomGenerator.nextInt(10));
		}
 
		//populate 10k.txt
		fileName = "10k.txt";
		@SuppressWarnings("resource")
		PrintWriter tenkOut = new PrintWriter(fileName);
		for(int i = 0; i < 10000; i++){
			tenkOut.println(randomGenerator.nextInt(10000));
		}
 
		//populate 1m.txt
		fileName = "1m.txt";
		@SuppressWarnings("resource")
		PrintWriter tenmOut = new PrintWriter(fileName);
		for(int i = 0; i < 1000000; i++){
			tenmOut.println(randomGenerator.nextInt(1000000));
		}
	}
}

I do not believe I am closing the files as I have no idea what you are talking about.

edit- norm, please note i also just updated my driver class with a more final approach.

figured it out using common sense and also using your suggestion to close scanners that are no longer needed. let me do some more poking with my main class and I will come back with any questions. Thank you sooooo much for your help!

Ok, under my algorithm methods that I have in my main class, I am getting a error that says 'this method is undefined for type driver.' Do you know anything about that?

Originally Posted by Norm

Please explain what the problems are.

It's not running when I call the algorithm methods. I get a 'this method [insert algorithm method here] is undefined for type driver.'

Exception in thread "main" java.lang.Error: Unresolved compilation problems:
The method maxSubSum1(int[]) is undefined for the type driver
The method maxSubSum2(int[]) is undefined for the type driver
The method maxSubSum3(int[]) is undefined for the type driver
The method maxSubSum4(int[]) is undefined for the type driver
The method maxSubSum1(int[]) is undefined for the type driver
The method maxSubSum2(int[]) is undefined for the type driver
The method maxSubSum3(int[]) is undefined for the type driver
The method maxSubSum4(int[]) is undefined for the type driver
The method maxSubSum1(int[]) is undefined for the type driver
The method maxSubSum2(int[]) is undefined for the type driver
The method maxSubSum3(int[]) is undefined for the type driver
The method maxSubSum4(int[]) is undefined for the type driver

at driver.main(driver.java:22)

--- Update ---

will try moving the class when I wake up.

I moved everything into one class and now the program is partially working. The algorithms run on the 10.txt file in 0 nanoseconds; all three times. Idk if that is normal or not. The algorithms run a second time on the 10k.txt file and take around 2 minutes. The problem lies in the third. I have left the computer running for over 30 minutes, but it doesnt seem to finish.

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;
 
 
public class driver {
 
		//create arrays
		static int[] tenArray = new int[10];
		static int[] tenkArray = new int [10000];
		static int[] tenmArray = new int [1000000];
 
	public static void main(String[] args) throws IOException{
 
		//temporal measurement variables
		long startTime, endTime, average;
 
		System.out.println("Started.");
 
		//create and fill files
		populateFiles();
		readFiles();
 
		System.out.println("Starting algorithms.");
 
		//uses 10.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(tenArray);
			maxSubSum2(tenArray);
			maxSubSum3(tenArray);
			maxSubSum4(tenArray);
			endTime = System.currentTimeMillis();
			System.out.println("This round of algorithms using n = 10 took " + (endTime - startTime) + " milliseconds.");
			average = endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " nanoseconds.");
 
		//uses 10k.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(tenkArray);
			maxSubSum2(tenkArray);
			maxSubSum3(tenkArray);
			maxSubSum4(tenkArray);
			endTime = System.currentTimeMillis();
			System.out.println("This round of algorithms using n = 10,000 took " + (endTime - startTime) + " milliseconds.");
			average += endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " milliseconds.");
 
		//uses 10m.txt
		average = 0;
		for (int i=0; i < 3; i++){
			startTime = System.currentTimeMillis();
			maxSubSum1(tenmArray);
			maxSubSum2(tenmArray);
			maxSubSum3(tenmArray);
			maxSubSum4(tenmArray);
			endTime = System.currentTimeMillis();
			System.out.println("This round of algorithms using n = 1,000,000 took " + (endTime - startTime) + " milliseconds.");
			average += endTime-startTime;
		}
		System.out.println("The average running time for the three runs was " + (average/3) + " milliseconds.");
 
	}
 
	//algorthm 1
	//cubic maximum contiguous subsequence sum algorithm
	public static int maxSubSum1(int [] a){
		int maxSum = 0;
 
		for(int i = 0; i < a.length; i++){
			for(int j = i; j < a.length; j++){
				int thisSum = 0 ;
 
				for(int k = i; k <= j; k++){
					thisSum += a[k];
 
					if(thisSum > maxSum){
						maxSum = thisSum;
					}
				}
			}
		}
		return maxSum;
	}
 
	//algorithm 2
	//quadratic maximum contiguous subsequence sum algorithm
	public static int maxSubSum2(int [] a){
		int maxSum = 0;
 
		for(int i = 0; i < a.length; i++){
			int thisSum = 0;
 
			for(int j = i; j < a.length; j++){
				thisSum += a[j];
 
				if(thisSum > maxSum){
					maxSum = thisSum;
				}
			}
		}
		return maxSum;
	}
 
	//algorithm 3
	//recursive maximum contiguous subsequence sum malgorithm.
	//finds maximum sum in subarray spanning a[left...right].
	//does not attemmpt to maintain actual best sequence
	private static int maxSumRec(int [] a, int left, int right){
 
		if(left == right){ //base case
			if(a [left] > 0){
				return a[left];
			}
			else {return 0;}
			}
 
		int center = (left + right) /2;
		int maxLeftSum = maxSumRec(a, left, center);
		int maxRightSum = maxSumRec(a, center + 1, right);
 
		int maxLeftBorderSum = 0, leftBorderSum = 0;
		for(int i = center; i >= left; i--){
			leftBorderSum += a[i];
			if(leftBorderSum > maxLeftBorderSum){
				maxLeftBorderSum = leftBorderSum;
			}	
		}
 
		int maxRightBorderSum = 0, rightBorderSum = 0;
		for(int i = center + 1; i <= right; i++){
			rightBorderSum += a[i];
			if(rightBorderSum > maxRightBorderSum){
				maxRightBorderSum = rightBorderSum;
			}
		}
		return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
	}
 
	private static int max3(int a, int b, int c) {
	    return a > b ? (a > c ? a : c) : (b > c ? b : c);
	}
 
	//driver for divide-and-conquer maximum contiguous subsequence sum algorithm
	public static int maxSubSum3(int [] a){
		return maxSumRec(a, 0, a.length - 1);
	}
 
	//algorithm 4
	//linear-time maximum contiguous subsequence sum algorithm
	public static int maxSubSum4(int [] a){
		int maxSum = 0, thisSum = 0;
 
		for(int j = 0; j < a.length; j++){
			thisSum += a[j];
 
			if(thisSum > maxSum){
				maxSum = thisSum;
			}
			else if(thisSum < 0){
				thisSum = 0;
			}
		}
		return maxSum;
	}
 
	//method for reading from the text files into arrays
	public static void readFiles() throws IOException{
 
		int i;
		String tenFile = "10.txt";
		String tenkFile = "10k.txt";
		String onemFile = "1m.txt";
 
		Scanner tenScan = new Scanner(new File(tenFile));
		i = 0;
		while (tenScan.hasNext()){
			tenArray[i] = tenScan.nextInt();
			i++;
		}
		tenScan.close();
 
		Scanner tenkScan = new Scanner(new File(tenkFile));
		i = 0;
		while (tenkScan.hasNext()){
			tenkArray[i] = tenkScan.nextInt();
			i++;
		}
		tenkScan.close();
 
		Scanner onemScan = new Scanner(new File(onemFile));
		i = 0;
		while (onemScan.hasNext()){
			tenmArray[i] = onemScan.nextInt();
			i++;
		}
		onemScan.close();
	}
 
	//method for printing to the text files
	public static void populateFiles() throws IOException{
		String fileName = "10.txt";
 
		//create new randomgenerator object
		Random randomGenerator = new Random();
 
		//populate 10.txt
		fileName = "10.txt";
		PrintWriter tenOut = new PrintWriter(fileName);
		for(int i = 0; i < 10; i++){
			tenOut.println(randomGenerator.nextInt(10));
		}
		tenOut.close();
 
		//populate 10k.txt
		fileName = "10k.txt";
		PrintWriter tenkOut = new PrintWriter(fileName);
		for(int i = 0; i < 10000; i++){
			tenkOut.println(randomGenerator.nextInt(10000));
		}
		tenkOut.close();
 
		//populate 1m.txt
		fileName = "1m.txt";
		PrintWriter tenmOut = new PrintWriter(fileName);
		for(int i = 0; i < 1000000; i++){
			tenmOut.println(randomGenerator.nextInt(1000000));
		}
		tenmOut.close();
	}
}

I added in some code to print to console as the 3rd set of algorithms execute and it turns out the 3rd and 4th algorithms are working properly. It is the 1st and 2nd that are hanging it up. Where could I put some code in the first and second algorithms to properly print to the console?

Also, I changed the first set of algorithms to nanoseconds and they do in fact seem to be operating properly. It's just that 3rd set...

Btw, thank you so much for your help already.

Edit- Apparently everyone in my class is having trouble with the million file. I will just ask my instructor as I no longer believe it is a programming issue.

Originally Posted by Norm

To get messages printed as the code executes the loops, add a counter and if statement to print a message every so often:

int cntr = 0;  //  define counter outside the loops
 ....
//  inside the loops:
if(cntr++ % 10000 == 0) System.out.println("cntr="+cntr); // show a message every 10000 loops

Okay, I will play around with that.

One final thing, my instructor just told me to just add some time that 'times out' when the program gets stuck for more than 10 minutes. I would need to encase the first two algorithms for the third set. How would I add this feature when the program just seems to freeze?

Originally Posted by Norm

Why do you think the code is "freezing"?
Add the println I suggested and see if the code continues to print something or if it stops printing (freezes)


If the 10000 is too small and creates too much printout, try it with a larger number.

I think it is freezing because I have a pretty stout computer and left it for a few hours and didn't receive anything back. Either way, I will add that line to my code when I get out of class. Thanks.

I have not. I input the loop counter into my code and now it shows that it works AND completes rather quickly. Here is the new code with the counter.

	//algorthm 1
	//cubic maximum contiguous subsequence sum algorithm
	public static int maxSubSum1(int [] a){
		int cntr = 0, maxSum = 0;
 
		for(int i = 0; i < a.length; i++){
			if (cntr++ % 10000 == 0){
				System.out.println("cntralg1loop1="+cntr);  //conter variable to ensure progress
				for(int j = i; j < a.length; j++){
					if (cntr++ % 10000 == 0){
						System.out.println("cntralg1loop2="+cntr);
						int thisSum = 0 ;
 
						for(int k = i; k <= j; k++){
							if (cntr++ % 10000 == 0){
								System.out.println("cntralg1loop3="+cntr);
								thisSum += a[k];
 
								if(thisSum > maxSum){
									maxSum = thisSum;
								}
							}
						}
					}
				}
			}
		}
		return maxSum;
	}
 
	//algorithm 2
	//quadratic maximum contiguous subsequence sum algorithm
	public static int maxSubSum2(int [] a){
		int maxSum = 0, cntr = 0;
 
		for(int i = 0; i < a.length; i++){
			if (cntr++ % 10000 == 0){
				System.out.println("cntralg2loop1="+cntr);
				int thisSum = 0;
 
				for(int j = i; j < a.length; j++){
					if (cntr++ % 10000 == 0){
						System.out.println("cntralg2loop2="+cntr);
						thisSum += a[j];
 
						if(thisSum > maxSum){
							maxSum = thisSum;
						}
					}
				}
			}
		}
		return maxSum;
	}

Wouldn't that cause it to only process every 10,000th integer?

Edit- I have to turn this in tomorrow morning. My instructor said that we could just implement some sort of 'time-out' for the computation with the 1m.txt file. How would I do that? Have a method-level variable that stores the currentTimeMillis when the method is called then have integer inside each loop that constantly updates every time the loop runs and then subtract that time from the start time and have that run until the difference is greater than some predetermined time? Sorry for the incredible run-on, lol.

Well that explains that. I think I have the timeout feature figured out. Thanks for all of your help yet again.