# CS代考程序代写 algorithm Java Fall 2020 prepared by Mark Yendt

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