Subject: Java Lab 4 Algorithms Lab Objective: This lab is designed to understand
ID: 3589829 • Letter: S
Question
Subject: Java
Lab 4
Algorithms
Lab Objective:
This lab is designed to understand how analysis of algorithms is done. In this lab you will practice how to write and implement efficient algorithms. Also you will be doing experimental analysis on different algorithms to tell which one is more efficient.
Problem 1: Perform an experimental analysis of the two algorithms given below.
public static double[] prefixAverage1(double[] x)
{ int n = x.length;
double [] a = new double[n]; for (int j =0; j < n; j++)
{ double total =0; for (int i =0; i <=j ; i++) total += x[i]; a[j] = total / (j + 1);
}
return a;
}
public static double[] prefixAverage2(double[] x)
{ int n = x.length;
double [] a = new double[n]; double total = 0; for (int j =0; j < n; j++)
{ total += x[i];
a[j] = total / (j + 1);
}
return a;
}
Problem 2: Describe and Implement an efficient algorithm for finding the ten largest elements in an array of size n. What is the running time of your algorithm?
Problem 3: An array A contains n-1 unique integers in the range [0, n-1]. There is one number from this range that is not in A. Describe and implement an O(n) algorithm for finding that number.
Hint : Consider computing a function of the integers in A that will immediately identify which one is missing.
public static double[] prefixAverage1(double[] x)
{ int n = x.length;
double [] a = new double[n]; for (int j =0; j < n; j++)
{ double total =0; for (int i =0; i <=j ; i++) total += x[i]; a[j] = total / (j + 1);
}
return a;
}
Explanation / Answer
// problem1:-
package lab2b;
import java.util.Arrays;
import java.util.Scanner;
public class Lab4 {
static int count1=0;
// for example double[] x taking 5 elements i.e, array size is 5.,
// outer for loop iterates 5 times and inner loop iterates 15 times(1st iteration 1 time, 2nd iteration 2 times, 3rd iteration 3 times,...)
// i.e., 1+2+3+4+5=15 times inner for loop iterates.
public static double[] prefixAverage1(double[] x)
{ int n = x.length;
double [] a = new double[n];
for (int j =0; j < n; j++)
{ count1++;
double total =0;
for (int i =0; i <=j ; i++) {
count1++;
total += x[i]; a[j] = total / (j + 1);
}
}
System.out.println("count1 "+count1); // print 20 for array size 5.
return a;
}
static int count2=0;
// for example double[] x taking 5 elements i.e, array size is 5.,
// for loop iterates 5 times only. so, iterations compare to prefixAverage1 is 3 times less in prefixAverage2.
// So, prefixAverage2 is more efficient than prefixAverage1.
public static double[] prefixAverage2(double[] x)
{ int n = x.length;
double [] a = new double[n];
double total = 0;
for (int j =0; j < n; j++)
{ count2++;
total += x[j];
a[j] = total / (j + 1);
}
System.out.println("count2 "+count2);
return a;
}
public static void main(String[] args) {
Lab4 l4=new Lab4();
Scanner sc=new Scanner(System.in);
System.out.println("enter user double array size:");
int n=sc.nextInt();
System.out.println("enter array values: ");
double[] d=new double[n];
for(int i=0;i<n;i++){
d[i]=sc.nextDouble();
}
double[] arr=l4.prefixAverage1(d);
System.out.println(Arrays.toString(arr));
double[] arr1=l4.prefixAverage2(d);
System.out.println(Arrays.toString(arr1));
}
}
/*
enter user double array size:
5
enter array values:
2.1 3.4 5.6 7.8 9.0
count1 20
[2.1, 2.75, 3.6999999999999997, 4.725, 5.58]
count2 5
[2.1, 2.75, 3.6999999999999997, 4.725, 5.58]
*/
//problm2:-
package lab2b;
import java.util.Arrays;
import java.util.Scanner;
class TenLargeElements
{
public static void kLargestElements(int[] arr, int k)
{
// Sorting the given array arr in ascending order
// Sort the elements in descending order in O(nLogn)
Arrays.sort(arr);
// Print the first k th largest elements.
// we are printing in reverse order of an array.
// Print the first k numbers of the sorted array O(k).
for (int i = arr.length-1; i >1; i--)
System.out.print(arr[i] + " ");
}
// So, totally taking Time complexity: O(nlogn).
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("enter array size:");
int n=sc.nextInt();
System.out.println("enter array values: ");
int arr[] = new int[n];
for(int i=0;i<arr.length;i++){
arr[i]=sc.nextInt();
}
int k = 10;
kLargestElements(arr,k);
}
}
/* output:-
enter array size:
12
enter array values:
2 3 5 6 12 45 67 93 12 15 63 76
93 76 67 63 45 15 12 12 6 5 */
// problem3:-
package lab2b;
import java.util.Scanner;
//Java program to find missing Number
class FindMissingNumber
{
// method to find missing number
static int findMissingNumber (int a[], int n)
{
int total;
total = (n+1)*(n+2)/2;
for ( int i = 0; i< n; i++)
total -= a[i];
return total;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("enter array size:");
int n=sc.nextInt();
System.out.println("enter array values: ");
int arr[] = new int[n];
for(int i=0;i<arr.length;i++){
arr[i]=sc.nextInt();
}
int miss = findMissingNumber(arr,arr.length);
System.out.println(miss);
}
}
/*output;-
enter array size:
5
enter array values:
1 3 4 5 6
2
*/