daa lab programs

import java.util.Scanner;

public class Student {
    long USN;
    String Name;
    String Branch;
    long Phone;

public Student(long usn, String name, String br, long ph){
        this.USN = usn;
        this.Name = name;
        this.Branch = br;
        this.Phone = ph;
    }

void display(){
        System.out.println(USN + "\t" + Name + "\t" + Branch + "\t" + Phone );
    }

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

System.out.println("Enter the number of students");
        int n = scan.nextInt();

Student[] students = new Student[n];

for (int i = 0; i< n; i++){
            System.out.println("Enter the details of student" + (i+1));

System.out.println("Enter the USN");
            long usn = scan.nextLong();

System.out.println("Enter the name of the student");
            String name = scan.next();

System.out.println("Enter the name of the branch");
            String branch = scan.next();

System.out.println("Enter the phone number");
            long phone = scan.nextLong();

students[i] = new Student(usn, name , branch, phone);
        }

System.out.println("USN" + "\t" + "Name" + "\t" + "Branch"  +"\t" +"Phone");
        for(int i = 0; i<n; i++){
            students[i].display();
        }
    }
}
  >

package com.example.oneb;

import java.util.Scanner;

public class Stack {
    private static final int max_size = 5;

int[] arr = new int[max_size];
    int top = -1;

public void push(int ele){
        if(top< max_size-1){
            System.out.println("the element added is "+ele);
            top ++;
            arr[top] = ele;
        }else{
            System.out.println("Error: StackOverflow");
        }
    }

public void pop(){
        if(top>= 0){
            System.out.println("the element poped is "+arr[top]);
            top --;
        }else{
            System.out.println("Error: Stack underflow");
        }
    }

public void display_stack_contents(){
        if(top>=0){
            for(int i =0; i<=top; i++){
                System.out.println(arr[i]+ " ");
            }
        }else{
            System.out.println("stack is empty");
        }
    }

public static void main(String[] args) {
        Stack stack = new Stack();
        Scanner scan = new Scanner(System.in);

int elem;
        boolean whileLoop = true;

do {
            System.out.println("Enter your choice: \n 1.push \n 2.pop \n 3.dispaly \n 4.exit \n");
            int choice = scan.nextInt();

switch (choice){
                case 1:
                    System.out.println("Enter the element to be inserted \n");
                    elem = scan.nextInt();
                    stack.push(elem);
                    break;
                case 2:
                    stack.pop();
                    break;
                case 3:
                    stack.display_stack_contents();
                    break;
                case 4:
                    whileLoop = false;
                    break;
                default:
                    System.out.println("invalid input");
            }
        }while(whileLoop);
    }
}

package staff; 
    
    class Stf{

private int StafId;
private String Name;
private String Phone; private long Salary;
public Stf(int stafid,String name,String phone,long salary)
{

StafId=stafid; Name=name; Phone=phone; Salary=salary;
}

public void Display()
{

System.out.print(StafId+"\t"+Name+"\t"+Phone+"\t"+Salary);
}
}

class Teaching extends Stf	//inheritance
{

private String Domain; private int Publication;
public Teaching(int stafid,String name,String phone,long salary,String domain,int publication)
 
{
super(stafid,name,phone,salary); Domain=domain; Publication=publication;
}

public void Display()
{

super.Display();
System.out.print("\t"+Domain+"\t\t"+Publication+"\t\t"+"---"+"\t\t"+"---");
}
}

class Technical extends Stf
{

private String Skills;
public Technical(int stafid,String name,String phone,long salary,String skills){ super(stafid,name,phone,salary);
Skills=skills;
}

public void Display()
{

super.Display();
System.out.print("\t"+"---"+"\t\t---"+"\t\t"+Skills+"\t"+"---");
}
}

class Contract extends Stf
{

private int Period;
 
public Contract(int stafid,String name,String phone,long salary,int period){ super(stafid,name,phone,salary);
this.Period=period;
}

public void Display()
{

super.Display();
System.out.print("\t---"+"\t\t---"+"\t\t---"+"\t\t"+Period);
}
}

public class STAFF{
public static void main(String[] args)
{

Stf stf[]=new Stf[3];
stf[0]= new Teaching(1,"RAHIL","944955001",25000,"CSE",10);
stf[1]= new Technical(2,"REEHA","944955002",10000,"system admin"); stf[2]= new Contract(3 ,"RIFA","944955003",20000,3);
System.out.println("STAFFID\tNAME\tPHONE\t\tSALARY\tDOMAIN\t\tPUBLICATION\tSK ILLS\t\tPERIOD");
for(int i=0;i<3;i++)
{

stf[i].Display(); System.out.println();
}
}
}

import java.util.Random;

import java.util.Scanner;
 public class Quick {

private int[] numbers; 
private int size;

public void sort(int[] values) {

this.numbers = values; size = values.length;
long startTime =System.currentTimeMillis(); 
quicksort(0, size - 1);
long stopTime =System.currentTimeMillis(); 
long elapsedTime= stopTime-startTime; 
System.out.println("Time taken"); 
System.out.println(elapsedTime);
}

private void quicksort(int low, int high) { int j;
if(low<=high)
{
 
j=part(low,high); quicksort(low,j-1); 
quicksort(j+1,high);
}
}

private int part(int low,int high)
{

int i,j,pivot; pivot=numbers[low];
 i=low+1;
 j=high; 
while(true)
{

while(i<high && pivot >numbers[i]) i++;
while(numbers[j]>pivot) j--;
if (i<j)
{

int temp=numbers[i];
numbers[i]=numbers[j]; 
numbers[j]=temp;
}

else
{

int temp = numbers[low]; 
numbers[low]=numbers[j]; 
numbers[j]=temp;
 
return j;
}
}
}

public static void main(String[] args) {
 Quick sorter = new Quick();
int[] numbers; int size;
Scanner scan =new Scanner(System.in); 
System.out.println("enter size of the array"); 
size =scan.nextInt();
numbers=new int[size];
System.out.println("the elements of the array"); 
Random random = new Random();
for(int i=0;i<size;i++)
{

numbers[i]=Math.abs(random.nextInt(100));

}
for(int i=0;i<size;i++)
{

System.out.print("\t" + numbers[i]);

}
long startTime =System.currentTimeMillis();
 sorter.sort(numbers);
long stopTime =System.currentTimeMillis();
 
long elapsedTime= stopTime-startTime;
 System.out.println();
for(int i:numbers){
System.out.print(i); System.out.print(" ");
}
System.out.println(); 
System.out.println("Time taken"); 
System.out.println(elapsedTime);
}
}

5. Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the for varied values of n > 5000, and record the time taken to sort. Plot a graph of the time taken versus n on graph sheet. The elements can be read from a file or can be generated using the random number generator Demonstrate using Java how the divide and-conquer method works along with its time complexity analysis. worst case, average case and best case.

package merge;

import java.util.Scanner; import java.util.Random;
public class Merge {
private int[] numbers; private int[] c;
private int number;

public void sort(int[] values) {	// check for empty or null array if (values ==null || values.length==0){
return;

}

this.numbers = values; number = values.length; this.c = new int[number]; mergesort(0, number - 1);
}

private void mergesort(int low, int high) {

// int i = low, j = high;

// Get the pivot element from the middle of the list if (low<high)
{

int mid = (low + (high))/2;

// Recursion
 
mergesort(low, mid); mergesort(mid+1, high); mergearray( low, mid, high);
}

}

private void mergearray(int low,int mid,int high)	{ int i=low; int j=mid+1; int k =low;
while(i<=mid && j<=high)

{

if( numbers[i] < numbers[j]) c[k++]= numbers[i++];
else

c[k++]=numbers[j++];

}

while(i<=mid) c[k++]=numbers[i++];
while (j<=high) c[k++]=numbers[j++];
for(i=low;i<=high;i++) numbers[i]= c[i];

}

public static void main(String[] args) { Merge sorter = new Merge();
int[] numbers; int number;	int[] c; Scanner scan =new Scanner(System.in); System.out.println("enter size of the array"); number =scan.nextInt();
 
numbers=new int[number]; System.out.println("The elements of the array"); Random random = new Random();
for(int i=0;i<number;i++)

numbers[i]=Math.abs(random.nextInt(5000)); for(int i=0;i<number;i++)
System.out.print( "\t" + numbers[i]);	System.out.println(); long startTime =System.currentTimeMillis();
sorter.sort(numbers);

long stopTime =System.currentTimeMillis(); long elapsedTime= stopTime-startTime;
for(int i:numbers){

System.out.print(i);	System.out.print(" ");

}

System.out.println(); System.out.println("Time taken"); System.out.println(elapsedTime);
}

}

6. Implement in Java, the 0/1 Knapsack problem using (a) Dynamic Programming method (b)Greedy method.

<--       6a -->
        
      method package knapsack;
importjava.util.Scanner;

public class Knapsack { static int max(int a,int b)
{
return (a>b)?a:b;
}
public static void main(String[] args) { int n,i,j,cap;
int[] p =new int[20]; int[] w= new int [20];
int[][] v =new int[10][10]; System.out.println("enter no of items\n"); Scanner s=new Scanner(System.in);
n =s.nextInt(); for(i=1;i<=n;i++)
{
System.out.println("\n enter weights and profit of eachobject"); w[i]=s.nextInt();
p[i]=s.nextInt();

}
System.out.println("\ncapacity of knapsack"); cap=s.nextInt();

for(i=0;i<=n;i++) v[i][0]=0;
for(i=1;i<=n;i++) // to find the maximum values of item to be placed for(j=1;j<=cap;j++)
{
if(w[i] > j) v[i][j]=v[i-1][j];
else
v[i][j] = max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
System.out.println("\n the table is\n");

for(i=0;i<=n;i++)
{
for(j=0;j<=cap;j++)
{
System.out.print(v[i][j]+" ");
}
System.out.println("\n");

}
System.out.println("the maximum profit is\n"+v[n][cap]);
System.out.println("optimalsubset{");	// to find the items placed in the knapsack j=cap;
for(i=n; i>=1; i--)
if( v[i][j] != v[i-1][j]) // if values not of v[i][j] and v[i-1][j] are not same then pick that item i
{
System.out.println("item\t"+i);
j=j-w[i];	// reduce the capacity of the knapsack after picking itemi

}
System.out.println("\t }");

}
}

<-- 6b -->

package greedyknapsack;
    
import java.util.Scanner;

public class Greedyknapsack{
static void knapsack (int n,float weight[],float profit[],float capacity)
{
float x[]= new float [20],tp=0; int i,j,u;
c= (int) capacity; for (i=0;i<n;i++)
x[i]= (float) 0.0; for(i=0;i<n;i++)
{
if(weight[i] >c ) break;
else
{
x[i]=(float) 1.0; tp = tp +profit[i];
c=(int)(c-weight[i]);
}
}
if(i<n)
x[i]= c/weight[i]; tp=tp+(x[i] * profit[i]);
System.out.println("the result vector"); for (i=0;i<n;i++)
System.out.println( + x[i]); System.out.println("the total profit is"); System.out.println( + tp);
}
public static void main(String[] args)
{
float weight[]= new float[20]; float profit[]= new float[20]; float capacity;
int num,i,j;
float ratio[] = new float[20],temp; System.out.println("\nenter the no of objects"); Scanner s = new Scanner(System.in);
num =s.nextInt();
System.out.println("\n enter weights and profit of each object"); for(i=0;i<num;i++)
{
weight[i]=s.nextInt(); profit[i]= s.nextInt();

}
System.out.println("\ncapacity of knapsack"); capacity=s.nextInt();
for(i=0;i<num;i++)
{
ratio[i]= profit[i]/weight[i];
}
for(i=0;i<num;i++)
{
for(j=i+1;j<num;j++)

{
if (ratio[i]< ratio[j])
{
temp= ratio[j]; ratio[j]=ratio[i]; ratio[i]=temp; temp= weight[j]; weight[j]=weight[i]; weight[i]=temp; temp= profit[j]; profit[j]=profit[i]; profit[i]=temp;
}
}
}
knapsack(num,weight,profit,capacity);
}
}

import java.util.*; 
    
    public class Dijkstra{

public int distance[] = new int[10]; public int cost[][] = new int[10][10];

public void calc(int n,int s)
{
int flag[] = new int[n+1];
int i,minpos=1,k,c,minimum;

for(i=1; i<=n; i++)
{
flag[i]=0;
this.distance[i] = this.cost[s][i];
}
c = 2;
while(c<=n)
{
minimum=99; for(k=1; k<=n; k++)
{
if(this.distance[k] < minimum && flag[k]!=1)
{
minimum = this.distance[i]; minpos = k;
}
}
flag[minpos] = 1; c++;
for(k=1;k<=n;k++)
{
if(this.distance[minpos]+this.cost[minpos][k] < this.distance[k] && flag[k]!=1 ) this.distance[k]=this.distance[minpos]+this.cost[minpos][k];
}
}
}
public static void main(String args[])
{
int nodes,source,i,j;
Scanner in = new Scanner(System.in); System.out.println("Enter the Number of Nodes \n"); nodes = in.nextInt();
 
Dijkstra d = new Dijkstra();
System.out.println("Enter the Cost Matrix Weights: \n"); for(i=1;i<=nodes;i++)
for(j=1;j<=nodes;j++)
{
d.cost[i][j]=in.nextInt();
if(d.cost[i][j]==0)
d.cost[i][j]=999;
}
System.out.println("Enter the Source Vertex :\n"); source=in.nextInt()
d.calc(nodes,source);
System.out.println("The Shortest Path from Source \t"+source+"\t to all other vertices are : \n"); for(i=1;i<=nodes;i++)
if(i!=source)
System.out.println("source :"+source+"\t destination :"+i+"\t MinCost is :"+d.distance[i]+"\t");
}
}

package kruskals;

import java.util.*; 
public class Kruskals {

public int parent[] = new int[15]; public int cost[][] = new int[10][10]; public int mincost;

public void calc(int n)
{
int flag[] = new int[n+1];
int i,j,min=999,num_edges=1,a=1,b=1,minpos_i=1,minpos_j=1; parent[minpos_i]= 0;parent[minpos_j]= 0;

while(num_edges < n)
{

for(i=1 , min=999; i<=n; i++) for(j=1 ; j<=n; j++) if(this.cost[i][j] < min)

{
min = this. cost[i][j]; a = minpos_i = i;
b = minpos_j = j;
}

while(parent[minpos_i]!=0) minpos_i=parent[minpos_i];

while(parent[minpos_j]!=0) minpos_j=parent[minpos_j];

if(minpos_i!= minpos_j)
{
System.out.println("\t from Vertex \t"+a+"\t to Vertex \t"+b+"-mincost:"+min+" \n"); this.mincost=this.mincost+min;
num_edges=num_edges+1; this.parent[minpos_j]=minpos_i;
}
this.cost[a][b]=this.cost[b][a]=999;
}
 
System.out .println("MINIMUM COST SPANNING TREE (MCST)="+mincost);
}
public static void main(String[] args) { int nodes,i,j;
Scanner in = new Scanner(System.in); System.out.println("Enter the Number of Nodes \n"); nodes = in.nextInt ();
Kruskals k = new Kruskals();
System.out.println ("Enter the Cost Matrix Weights : \n"); for(i=1; i<=nodes; i++)
for(j=1; j<=nodes; j++)
{
k.cost[i][j] = in.nextInt();
if(k.cost[i][j] == 0)
k.cost[i][j] = 999;
}

k.calc(nodes);

}
}

package prim.s;

import java.util.*; /*author PROF. SAKEENA */

public class PrimS {
public int isVisited[] = new int[15]; public int cost[][] = new int[10][10]; public int mincost;

public void calc(int n)
{
int flag[] = new int[n+1];
int i,j,min=999,num_edges=1,a=1,b=1,minpos_i=1,minpos_j=1;

while(num_edges < n)
{

for(i=1 , min=999; i<=n; i++) for(j=1 ; j<=n; j++) if(this.cost[i][j] < min)
if(this.isVisited[i] != 0)
{
min = this. cost[i][j]; a = minpos_i = i;
b = minpos_j = j;
}
if(this. isVisited[minpos_i]== 0 || this.isVisited[minpos_j] == 0)
{
System.out.println"\t from Vertex \t"+a+"\t to Vertex \t"+b+"-mincost:"+min+" \n"); this.mincost=this.mincost+min;
num_edges=num_edges+1; this.isVisited[b]=1;
}
this.cost[a][b]=this.cost[b][a]=999;
}
System.out .println("MINIMUM COST SPANNING TREE (MCST) = "+mincost);
}

public static void main(String args[])
{
int nodes,i,j;
Scanner in = new Scanner(System.in); System.out.println("Enter the Number of Nodes \n"); nodes = in.nextInt ();
PrimS p = new PrimS();
 
System.out.println ("Enter the Cost Matrix Weights : \n"); for(i=1; i<=nodes; i++)
for(j=1; j<=nodes; j++)
{
p.cost[i][j] = in.nextInt();
if(p.cost[i][j] == 0)
p.cost[i][j] = 999;
}
p.isVisited[1] = 1; // Initialization p.calc(nodes);

}
}

DAA LAB