Fall 2020 prepared by Mark Yendt
Review Questions
The Questions below are to be used as preparation for the long answer questions on the test
Recursive Tracing
1. Show the output of the following program. It is suggested that you trace the code and predict the output and then type in the enter the code and check the results.
public class ThreeWays {
public static void main(String[] args) {
threeWays(1,4);
}
public static void threeWays(int id,int n) {
if (n >= 0) {
System.out.println(id + “=” + n);
threeWays(id+1,n-1);
threeWays(id+1,n-2);
threeWays(id+1,n-3);
} }
}
1=4
2=3
3=2
4=1
5=0
4=0
3=1
4=0
3=0
2=2
3=1
4=0
3=0
2=1
3=0
2. Show the output of the following program.
public class FindingZero {
public static void main(String[] args) {
findingZero(100);
}
public static void findingZero(int n)
{
if (n != 0) { System.out.println(n); findingZero(n-3*n/2);
} }
}
100
-50
25
-12
6
-3
1
Writing Code
3. A Box-Edge Sum is the sum of all of the values around the edges of a 2D Box or Square. The box data is typically stored in a 2D Array as shown below:
int data[][] = {{1,2,3,4},
{5,6,7,8},
{9,0,1,2},
{3,4,5,6}};
The size of the 2D array will always be square and can be any value from 1 to 10000.
Write your code to computer the box sum. You can use the above as an example data set. The box sum in the above case is 52 (1+2+3+4+5+8+9+2+3+4+5+6). Your algorithm must work in all cases and be efficient.
public static int boxSum(int[][] data) {
int N = data.length;
int sum = 0;
for (int i=0; i
}
int colRange = colMax – colMin;
if (colRange > maxRange) {
maxRange = colRange;
maxRangeCol = col;
}
}
System.out.println(“The maximum range is ” + maxRange
+ ” in Column ” + maxRangeCol);;
Algorithms
5. You have been given two algorithms that have been implemented in Java. The first algorithm is O(NlogN) which has an average basic instruction execution time of 21 ms. The second algorithm is O(N2) and has a basic instruction execution time of 1.6 ms. When N = 30 which algorithm would you select based on overall execution time? How about if N = 300?
Show how you did the calculations to prove this.
CASE 1
AL 1 = 21 * 30 * LOG2(30) = 3091
AL 2 = 1.6 * 30^2 = 1440
In the first case pick AL 1
CASE 2
AL 1 = 21 * 300 * LOG2(300) = 51841 AL 2 = 1.6 * 300^2 = 144000 In the first case pick AL 2
BONUS: At what value of N do the two algorithms require approximately the same amount of execution time? In order to solve this in a general way you will need to write a little code.
Here is the (Brute Force) code to figure it out
double bi1 = 21;
double bi2 = 1.6;
for (N=10; N<1000; N++) {
double et1 = bi1 * N * Math.log10(N)/Math.log10(2); double et2 = bi2 * N * N;
System.out.println(N + " " + et1 + "ms " + et2 + "ms"); if (et1 < et2) {
System.out.println("The break even point is about " + N);
break; }
}
6. The following code removes duplicates from an ArrayList.
ArrayList
System.out.println(“Numbers = ” + numbers);
ArrayList
for (int i=0; i