Q1 (a)Write the java code for doing a Linear Search on the array given below. Wr

Question

Q1

(a)Write the java code for doing a Linear

Search on the array given below.

Write your code in the space below,

(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.

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(n log(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

(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 .javafile)

public static

int factorialIterative(int n) {

int res = 1;

while (n > 0) {

res = res * n;

n

-­-­

;

}

return res;

}

Q4

Write aprogram where you use Selec tion 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)

Linear search in an array list

import java.util.Scanner;
class LinearSearch
{
public static void main(String args[])
{
int counter, num, item, array[];
Scanner input = new Scanner(System.in);
System.out.println("Enter number of elements:");
num = input.nextInt();
//Creating array to store the all the elements
array = new int[num];
System.out.println("Enter " + num + " integers");
//Loop to store each numbers in array list
for (counter = 0; counter < num; counter++)
array[counter] = input.nextInt();
System.out.println("Enter the search value:");
item = input.nextInt();
for (counter = 0; counter < num; counter++)
{
if (array[counter] == item)
{
System.out.println(item+" is present at location "+(counter+1));
//Item is found so to stop the searching and then come out of the loop use break statement.
break;
}
}
if (counter == num)
System.out.println(item + " doesn't exist in array.");
}
}
output:
1)
Enter number of elements:
6
Enter 6 integers
25
31
5
1
100
99
Enter the search value:
31
31 is present at location 2

2)
Enter number of elements:
4
Enter 4 integers
1
202
14
58
Enter the search value:
99
99 doesn't exist in array.

Q2) Really these should be multiplied by 2 because each iteration
must compare the loop condition i<n.

Best case:       1
Average case: n/2
Worse case: n

Suppose we used this algorithm by hand to search for a array list element in the array list.
Here n=100.If the time to check each element by hand is .001seconds
(a very optimistic estimate for a search by hand), then the average time is:
n x 0.001 sec = 100 x 0.001 sec = 0.1 sec.

Time complexity for merge sort
Best case: O(nlog(n))
Average case: O(nlog(n))
Worse case: O(nlog(n))

Q3)

a)Recursion:

int factorial (int n) {
if (n == 1) {
return 1;
} else {
return n*factorial(n-1);
}
}

Iteration:
int factorial (int n) {
int product = 1;
for(int i=2; i<n; i++) {
product *= i;
}
return product;
}

b) Advantages and Disadvantages of recursion fuction

A recursive function is a function which calls itself.
Advantages :
---->Avoidance of unnecessary calling of functions.
---->A substitute for iteration where the iterative solution is very complex. For example to reduce the code size for Tower of Honai application, a recursive function is bet suited.
---->Extremely useful when applying the same solution
Disadvantages:
---->A recursive function is often confusing.
---->The exit point must be explicitly coded.
---->It is difficult to trace the logic of the function.

Q4) Selection sort

public class MySelectionSortAscendingOrder{
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 args[]){
int[] arr1 = {24,2,45,20,56,75,2,56,99,53,12};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}

Insertion sort:

public class MyInsertionSort {

public static void main(String[] args) {

int[] input = { 24,2,45,20,56,75,2,56,99,53,12 };
insertionSort(input);
}

private static void print(int[] input) {

for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println(" ");
}

public static void 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;
print(array);
}
}
}

Output:

2,2,12,20,24,45,53,56,56,75,99

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.