Description
Our brute force method uses the recursiveHelperBF to traverse the first line of the array from left to right, initially setting the minimum value and route to be the value at index table[0][table.length] thus making only table.length 2 calls to the recursiveBF method. The recursiveHelperBF method also manages the route arrays by assigning the initial indices that are known, reassigning the arrays if a new min is a found, and also resetting the arrays to 0 for the next iteration of the for loop. Our recursiveBF method has an if statement that will check to see if the current index is out of bounds. If it is it will check if the current sum is less than the min, which if that is true it will reassigning the min and the route of the min to be the sum and the route of the sum. The corresponding else statement will update the route for the current index, and then make Current Row Length 2 calls updating the sum during each of those calls. Back in recursiveHelperBF the route will be updated if the sum that is returned from the initial recursiveBF call is less than the current min. In which case the route will be updated as well to this new route. Once the for loop is complete it will reverse the route to make the route into increasing order, then print the min and the route that corresponds to it. The complexity of the recursiveHelperBF method is ● (1) for the declarations. Θ ● for the outer for loop. (n 2)Θ − ∈ (n) Θ ○ (n) for the inner for loop that resets the route values to 0 Θ ○ (1) for the declarations. Θ ○ (1) for the if statement. Θ ■ for the for loop inside the if that copies tempRoute2 onto route. (n)Θ ● for the reversal of route. (n)Θ ● (1) for the final prints. Θ The complexity of the recursiveBF method is ● for the recursiveHelperBF calls. (n)Θ ○ (1) for the declarations. Θ ○ (1) for the if statement checking to see if the current index is out of bounds. Θ ■ (1) for the if statement checking to see if the current sum is less than min. Θ ● (1) for the declarations. Θ ● for for loop inside the if that copies tempRoute onto tempRoute2. (n)Θ ○ (1) for else statement. Θ
■ (n) : where x is the Current Row Length results in ∑ x n = 1 = ( = where x is n 2 = 1 /2)x(x )( +1 x )/2 /2 2 +x (x ) Θ 2 ≤ (n ) Θ 2 ■ (1) for the declarations. Θ ○ (1) for return. Θ
The final complexity comes from the outer loop calls in the recursiveHelperBF method multiplied (n)Θ with the of recursive calls in the recursiveBF method which results in a final complexity of . (n )Θ 2 (n ) Θ 3 3.2 Divide and Conquer Our divide and conquer method uses the recursiveHelperDAC to create the array and tempArray and fills them with Integer.MAX_VALUE and N respectively. Then it makes the initial call to recursiveDAC and after that call is done it will print the min and the route of that min. Our recursiveDAC method has an if statement to check to make sure the current index is within the bounds of our table. If it is it will add that index to the tempRoute, and then make two recursive calls and calculate the min between the two. One of the two calls will be to add the current index to the sum and go to the next index then increment the position, while the other call will be to keep the current sum and then go to the next index but don’t increment the position. The corresponding else statement will add the current index to the sum and update the tempRoute. Then it will check if the current sum is less than our min and if it is it will reassign min to be that value, as well as copying tempRoute onto our min route. The complexity of the recursiveHelperDAC method is ● (1) for the declarations and prints. Θ ● for the filling of the route array with Integer.MAX_VALUE. (n)Θ ● for the filling of the route array with N. (n)Θ The complexity of the recursiveDAC method is ● for the if statement checking to make sure current index is not out of bounds. (1)Θ ○ for the declarations. (1)Θ ○ for the two recursive calls made. (nlogn)Θ ● for the else statement. (1)Θ ○ for the declarations. (1)Θ ○ for the if statement checking to see if the current sum is less than the min. (1)Θ ■ for the declarations. (1)Θ ■ for the if loop checking to see if the stored min in tempRoute[table.length] (1)Θ is less than the stored min in route[table.length]. ● for the for loop reassigning the tempRoute values to route. (n)Θ
● for the return. (1)Θ
The final complexity comes from the recursive calls. Everything else is an addition of (nlogn)Θ complexity and not nested complexities so the final complexity is . (nlogn)Θ 3.3 Dynamic Programming Our dynamic programming algorithm creates a priority queue to hold the values of the paths found. It then makes a value, least, that will be used to track the row of the cheapest path. The object that makes it dynamic is the 2D array used to store the path values. The first row of this array is filled with the same values as the given table. The method then enters a double for loop that walks through all the positions in the table a single time. At each position the array uses a for loop to determine the value of the cheapest path used to get to that location. This value is then stored in the 2D array and used to determine the cheapest path for later values. At the end of each row the value of that path is stored in the priority queue and if that value is the smallest the value least is set to that row. When the loop has finished the algorithm will reconstruct the path using the least value and the values stored in the 2D array. Since this array is built backwards it is reworked by a second loop. The value of the cheapest path as well as its route are then printed to the console. The complexity of the dynamic method is ● for the declarations. (1)Θ ● for the for loop to copy the first row of the table onto our summations array. (n)Θ ● for the for loop to traverse the rows of the table. (n ) Θ −2 ∈ (n) Θ ○ for the declarations. (1)Θ ○ for the loop to traverse the columns of the table. (n)Θ ■ for the declarations. (1)Θ ■ for the for loop to find the smallest value. (n)Θ ○ for adding to the heap. (nlogn)Θ ● for the declarations. (1)Θ ● for the for loop to construct the initial route array. (n ) Θ −2 ∈ (n) Θ ○ for the declarations and updating of route and least. (1)Θ ○ for the for loop to reassign min and position. (n)Θ ■ for the declarations and if statement to determine positions. (1)Θ ● for the for loop to make a new route array without the extra zeroes. (n)Θ ○ for the if and else statements to eliminate the zeroes and copy to finished. (1)Θ ● for the printing of min and the route associated with min. (1)Θ The final complexity comes from the traversal for loops, which is for the rows, for the columns (n)Θ (n) Θ and to find the smallest value. Resulting in a final complexity of (n)Θ (n ) Θ 3
4.1 Dynamic Programming The algorithm we designed will create a s*s box inside of the n*n array with the target position (x,y) being the top left index of our s*s box. Then we will scan through our s*s box traversing it linearly scanning for a TRUE value. If there is no TRUE values then we will return TRUE as the answer. If there is a TRUE value then we will move our s*s box one index to the left. We will repeat this left traversal scanning for TRUE values and repeat the shifting of our s*s box until it gets shifted s1 amount of times in which case we will reset the s*s box so that the box moves upwards in the yaxis now repeating similarly to the xaxis traversal. We will repeat this left traversal scanning for TRUE values and repeat the shifting of our s*s box until it gets shifted s1 amount of times in which case we will reset the s*s box so that the box now moves in a diagonal direction up and to the left. Repeating similarly to the xaxis and yaxis traversals. Once the s*s box is shifting s1 amount of times it will have checked all possible combinations and will have either returned TRUE that a s*s box can be found, or it will return FALSE if it reaches the end and hasn’t found a box yet. FieldAndStones(boolean field[n][n], int targetPosition, int s) { Let result be a boolean value to be updated if there are TRUE values found, initialized to TRUE; Let xShift be an int value to control the shifting of the s*s array in the xaxis. Let yShift be an int value to control the shifting of the s*s array in the yaxis. Let xyShift be an int value to control the shifting of the s*s array in the diagonal direction. if(x,y == TRUE) { return FALSE; } for(int i = x; i < x + s; i++) { for(int j = y; j < y + s; j++) { if(field[i][j] == FALSE) { } else { result == FALSE;
}
}
}
if(result == TRUE) { return TRUE; } result == TRUE;
for(xShift = 1; xShift < s; xShift++) { for(int i = x xShift; i < x xShift + s; i++) { for(int j = y; j < y + s; j++) { if(field[i][j] == FALSE) { } else { result == FALSE; } } } if(result == TRUE) { return TRUE; } result == TRUE; }
for(yShift = 1; yShift < s; yShift++) { for(int i = x; i < x + s; i++) { for(int j = y yShift; j < y yShift + s; j++) { if(field[i][j] == FALSE) { } else {
result == FALSE;
}
}
} if(result == TRUE) { return TRUE; } result == TRUE;
}
for(xyShift = 1; xyShift < s; xyShift++) { for(int i = x xyShift; i < x xyShift + s; i++) { for(int j = y xyShift; j < y xyShift + s; j++) { if(field[i][j] == FALSE) { } else { result == FALSE; } } } if(result == TRUE) { return TRUE; } result == TRUE; } return FALSE;
} The complexity of this algorithm is since the triple for loops result in a complexity of n*n*n which (n )Θ 3 is there are multiple for loops but they are added to each other and not multiplied so it stays at the (n )Θ 3 complexity . (n )Θ 3
Homework 4 By: Brandon Watt and Andrew Gates
BRUTE FORCE - SPACE - TIME recursiveHelperBF - recursiveHelperBF - (9* 4 bytes) Integer Values (n^2) for resetting routes to 0 (4 * 4 bytes * n) 1D Integer Arrays (n^2) for copying to route (4 bytes * n^2) 2D Integer Arrays (n) for reversal of route
recusiveBF - recusiveBF - (7 * 4 bytes * n^2) Integer Values (n^3) for recursiveHelperBF and recursiveBF calls (2 * 4 bytes * n^2) 1D Integer Arrays (n^2) for copying to tempRoute2 (4 bytes * n^2 * n^2) 2D Integer Arrays
Cost (Bytes) n Value Time (Seconds) n Value 96.00 1 5.00 1 292.00 2 22.00 2 3,616.00 5 205.00 5 44,196.00 10 1,310.00 10 1,587,936.00 25 17,525.00 25 25,100,836.00 50 132,550.00 50 400,401,636.00 100 1,030,100.00 100 6,401,603,236.00 200 8,120,200.00 200 102,406,406,436.00 400 64,480,400.00 400 518,414,409,636.00 600 217,080,600.00 600 1,638,425,612,836.00 800 513,920,800.00 800
DIVIDE AND CONQUER SPACE - TIME recursiveHelperDAC - recursiveHelperDAC - (4 bytes) Integer Values (n) for filling of route (2 * 4 bytes * n) 1D Integer Arrays (n) for filling of tempRoute (4 bytes * n^2) 2D Integer Array
recursiveDAC - recursiveDAC - (6 * 4 bytes * nlogn) Integer Values (nlogn) for recursiveDAC calls (2 * 4 bytes * n * nlogn) 1D Integer Arrays (n) for copying to route (4 bytes * n^2 * nlogn) 2D Integer Arrays
Cost (Bytes) n Value Time (Seconds) n Value 24.00 1 3.00 1 164.00 2 8.00 2 2,087.98 5 26.61 5 17,306.52 10 63.22 10 319,150.61 25 191.10 25 2,952,381.85 50 432.19 50 27,164,482.51 100 964.39 100 247,249,326.56 200 2,128.77 200 2,224,620,705.52 400 4,657.54 400 8,001,860,845.41 600 7,337.29 600 19,802,751,986.39 800 10,115.08 800
200,000,000,000.00
400,000,000,000.00
600,000,000,000.00
800,000,000,000.00
1,000,000,000,000.00
1,200,000,000,000.00
1,400,000,000,000.00
1,600,000,000,000.00
1,800,000,000,000.00
0 100 200 300 400 500 600 700 800 900
Cost vs. n
100,000,000.00
200,000,000.00
300,000,000.00
400,000,000.00
500,000,000.00
600,000,000.00
0 100 200 300 400 500 600 700 800 900
Time vs. n
5,000,000,000.00
10,000,000,000.00
15,000,000,000.00
20,000,000,000.00
25,000,000,000.00
0 100 200 300 400 500 600 700 800 900
Cost vs. n
2,000.00
4,000.00
6,000.00
8,000.00
10,000.00
12,000.00
0 100 200 300 400 500 600 700 800 900
Time vs. n
DYNAMIC PROGRAMMING SPACE - TIME dynamic - dynamic (12 * 4 bytes) Integer Values (n) for the loop to copy the first row (2 * 4 bytes * n) 1D Integer Arrays (n^3) for the loops to traverse the table (2 * 4 bytes * n^2) 2D Integer Arrays (n^2*logn) for adding to the heap in the loop (4 bytes * n) Priority Queue (n^2 )for the loops to construct the route array (n) for the loop to make a new route array with no zeroes
Cost (Bytes) n Value Time (Seconds) n Value 68.00 1 4.00 1 104.00 2 20.00 2 308.00 5 218.05 5 968.00 10 1,452.19 10 5,348.00 25 19,202.41 25 20,648.00 50 141,709.64 50 81,248.00 100 1,076,638.56 100 322,448.00 200 8,346,154.25 200 1,284,848.00 400 65,543,816.99 400 2,887,248.00 600 219,683,574.73 600 5,129,648.00 800 518,813,667.96 800
1,000,000.00
2,000,000.00
3,000,000.00
4,000,000.00
5,000,000.00
6,000,000.00
0 100 200 300 400 500 600 700 800 900
Cost vs. n
100,000,000.00
200,000,000.00
300,000,000.00
400,000,000.00
500,000,000.00
600,000,000.00
0 100 200 300 400 500 600 700 800 900
Time vs. n