DAA 3

MargeSort pgm
package demo;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[];
Scanner scan=new Scanner(System.in);
System.out.println("Enter the size for merge sort...:");
int n=scan.nextInt();
a=new int[n];
System.out.println("enter array elements:");
for(int i=0;i<n;i++)
a[i]=scan.nextInt();
msortdiv(a,0,n-1);
System.out.println("sorted array are:");
for(int i=0;i<n;i++)
System.out.println(a[i]+" ");
}
static void msortdiv(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
msortdiv(a,low,mid);
msortdiv(a,mid+1,high);
mergesort(a,low,mid,high);
}
}
static void mergesort(int a[],int low,int mid,int high)
{
int i,j,k,b[]=new int[20];
i=low;
j=mid+1;
k=low;
while(i<=mid && j<=high)
{
if(a[i]>=a[j])
{
b[k]=a[j];
j++;
k++;
}
else
{
b[k]=a[i];
k++;
i++;
}
}
while(i<=mid)
{
b[k++]=a[i++];
}
while(j<=high)
{
b[k++]=a[j++];
}
for( i=low;i<=high;i++)
{
a[i]=b[i];
}
}
}



Program 7: Write a program that implement prim’s algorithm to generate
minimum cost spanning tree.
package prims;
import java.util.*;
public class PrimProgram {
//static Scanner scan;
final static int MAX=20;
static int n;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int[][] matrix=new int[MAX][MAX];
int[] visited=new int[10];
int min;
int u=0;
int v=0;
int total=0;
System.out.println("Enter number of nodes");
int n=scan.nextInt();
System.out.println("Enter cost matrix");
for(int i=0;i<n;i++)
{
visited[i]=0;
for(int j=0;j<n;j++)
{
matrix[i][j]=scan.nextInt();
if(matrix[i][j]==0)
{
matrix[i][j]=999;
}
}
}
visited[0]=1;
//start algorithm
for(int counter =0; counter<n-1;counter++)
{
min=999;
for(int i=0;i<n;i++)
{
if(visited[i]==1)
{
for(int j=0;j<n;j++)
{
if(visited[j]!=1)
{
if(min>matrix[i][j])
{
min=matrix[i][j];
u=i;
v=j;
}
}}}}
visited[v]=1;
total+=min;
System.out.println("Edge found:"+u+"->"+v+": Weight:"+min);
}
System.out.println("The weight of the minimum spanning tree is"+total);
}


Program 8: Write a program that implement kruskal’s algorithm to
generate minimum cost spanning tree.
package kruskal;
import java.util.*;
public class KruskalProgram {
final static int MAX=20;
static int n; // no of vertices
static int cost[][];//cost matrix
static int parent[]=new int[9];
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
// TODO Auto-generated method stub
ReadMatrix();//read input
Kruskals();//construct minimum spanning tree
}
static void ReadMatrix()
{
int i,j;
cost=new int[MAX][MAX];
System.out.println("\nEnter the number of nodes");
n=scan.nextInt();
System.out.println("\nEnter cost matrix");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cost[i][j]=scan.nextInt();
if(cost[i][j]==0)
{
cost[i][j]=999;
}
}
}
}
static void Kruskals()
{
int a=0,b=0,u=0,v=0;
int i,j,ne=1,min,mincost=0;
System.out.println("The Edges of minimum cost spanning Tree are");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[a]>0)
{
a=parent[a];
}
while(parent[b]>0)
{
b=parent[b];
}
if(v!=u)
{
uni(u,v);
mincost+=min;
System.out.println(ne++ +"edge("+u+","+v+")=" +min);
}
cost[a][b]=cost[b][a]=999;
}
System.out.println("minimum cost is:"+mincost);
}
static void uni(int i,int j)
{
parent[j]=i;
}
}

Popular posts from this blog

devil

Python Programming Lab PART-A Program No.1: Program to check if a number belongs to the Fibonacci Sequence. N = int(input("Enter a number : ")) f3 = 0 f1 = 1 f2 = 1 if ( N == 0 ) or ( N == 1 ) :     print("The given number belongs to fibonacci series") else :     while f3 < N :         f3 = f1 + f2         f2 = f1         f1 = f3     if f3 == N :         print("The given number belongs to fibonacci series")     else :         print("The given number does not belong to fibonacci series") OUTPUT: Enter a number : 5 The given number  belongs to fibonacci series Enter a number : 17 The given number does not belongs to fibonacci series Program No.2: Program to solve Quadratic Equations. import math def findRoots ( a, b, c ) :          D = b * b - 4 * a * c     if D > 0:         print(" re...
Read more

A2 python

Program1: check whether the number is belongs to Fibonacci series or not PART A n=int(input("Enter the number: ")) c=0 a=1 b=1 if n==0 or n==1: print("Yes the number belongs to Fibonacci series") else:  while c<n:  c=a+b  b=a  a=c  if c==n:  print("Yes,the number belongs to Fibonacci series")  else: print("No, the number not belongs to Fibonacci series") ==========OUTPUT========= Enter the number: 5 Yes the number belongs to fibonacci series Enter the number: 4 No the number not belongs to fibonacci series SNJPSNMS Trust’s Degree College,Nidasoshi Python Programming Lab Program 2: Solve Quadratic Equations #import complex math module import cmath print("Enter the value of a") a=float(input()) print("Enter the value of b") b=float(input()) print("Enter the value of c") c=float(input()) #calculate the discriminant d=(b**2)-(4*a*c) #find the solution soln1=(-b-cmath.sqrt(d))/(2*a) soln2=(-b+cmath.sqrt(d))/(2*a) #prin...
Read more

html

HTML                                                     PART-A       Program No.1: Program to Design LOG IN Form in Html. <!DOCTYPE html> <html> <head> <meta name="view point" content="width"=device width, initial-scale="1"> <title> Login Page </title> </head> <body> <center><h1> Student Login Form </h1> </center> <form> <center> <div class ="container"> <lable>username:</lable> <input type ="text" place holder ="enter the username" name="username" requried> </div><div> <lable> password:</lable> <input type= "password" place holder ="enter password" name="password" requried></div><BR/> <button type="submit"> login</button> <input type="checkbox" checked ="checked"> Remember...
Read more