Short Answer Questions Q1. (0.5 point) (a)Write the java code for doing a Linear
ID: 3672325 • Letter: S
Question
Short Answer Questions
Q1. (0.5 point) (a)Write the java code for doing a Linear Search on the array given below.
Write your code in the space below, (no need to submit .java file)
(b) What would your search method return if we asked to search for the number 2 and return it’s index position?
[24][2][45][20]56][75][2][56][99][53][12]
Q2. (0.5 points) Calculate the Big Oh performance for the following: Given that an Array of size n=10 takes 3 seconds to search, how long does it take a search Array of size n=100? (a)Linear Search of an array of size n=100 Given O(n)
(b) Merge Sort performance of an array is O(nlog(n)), given that an Array of size n=10 takes 3 seconds to sort, how long does it take to sort an Array of size n=100?
Q3. (2 points) (a) Convert the following iterative method to recursive method.
(b) What is the advantage and disadvantage of using recursion?
Write your code in the space below, (no need to submit .java file)
public
static
int
factorialIterative(int
n)
{
int
res
=
1;
while
(n
>
0)
{
res
=
res
*
n;
n--;
}
return
res;
}
Q4. (2 points) Write a program where you use Selection Sort to sort the following array in ascending order.
24,2,45,20,56,75,2,56,99,53,12
a) Declare an array of integers called unsortedarr and load it with the integers above. Notice we have 11 numbers, and the number 2 is repeated which is fine.
Display the array as it is by printing it before the sort. b) Sort the array using the insertion sort technique and display the array after you sort it.
Here is the beginning of the code, complete it, run it, test it, submit it.
import java.util.*;
public class MySelectSort { public static void main(String[] args) { int arr[] = {24,2,45,20,56,75,2,56,99,53,12}; System.out.println("-------------------------- unsorted"); System.out.println(arr);
// continue … write your code
Explanation / Answer
Q1) a)
package linearsearch;
import java.util.Scanner;
public class searchlinear {
public static void main(String args[])
{
int c, n, search, array[];
Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
n = in.nextInt();
array = new int[n];
System.out.println("Enter " + n + " integers");
for (c = 0; c < n; c++)
array[c] = in.nextInt();
System.out.println("Enter value to find");
search = in.nextInt();
int i=0;
for (c = 0; c < n; c++)
{
if (array[c] == search) /* Searching element is present */
{ i=1;
System.out.println(search + " is present at location " + (c + 1) + ".");
}
}
if (c == n && i==0) /* Searching element is absent */
System.out.println(search + " is not present in array.");
}
}
b) It will return
2 is present at location 2.
2 is present at location 8.
Q2) a) linear search n=10 takes 3 seconds , so for n=100 it will take 3*10 = 30 seconds.
b) merge sort n=10 takes 3 seconds , so for n=100 it will take 3*2*10 = 60 seconds
Q3) a)
public class MainClass {
public static void main(String args[]) {
for (int counter = 0; counter <= 10; counter++)
System.out.printf("%d! = %d ", counter, factorial(counter));
}
// recursive declaration of method factorial
public static long factorial(long n) {
if (n <= 1) // test for base case
return 1; // base cases: 0! = 1 and 1! = 1
else
// recursion step
return n * factorial(n - 1);
}
}
b)
Disadvantages
Advantages
For example, the Tower of Hanoi problem is more easily solved using recursion as opposed to iteration.
Q4) a)
public class MySelectSort {
public static int[] doSelectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
public static void main(String a[]){
int[] arr = {24,2,45,20,56,75,2,56,99,53,12};
System.out.println("-------------------------- unsorted");
for(int i:arr){
System.out.print(i);
System.out.print(", ");
}
System.out.println(" ");
System.out.println("-------------------------- sorted");
int[] arr2 = doSelectionSort(arr);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
b)
public class Insertionsort {
public static void main(String[] args) {
int[] unsortedarr = {24,2,45,20,56,75,2,56,99,53,12};
System.out.println("-------------------------- unsorted");
for(int i:unsortedarr ){
System.out.print(i);
System.out.print(", ");
}
System.out.println(" ");
System.out.println("-------------------------- sorted");
int[] arr2 = insertionSort(unsortedarr );
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
public static int[] insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
return array;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.