MU | IT | ENGINEERS

MUMBAI UNIVERSITY ENGINEERING NOTES - MU | ENGINEERING | SYLLABUS | NOTES

2011-12-13T21:25:00.000-08:00

MUMBAI UNIVERSITY ENGINEERING NOTES - MU | ENGINEERING | SYLLABUS | NOTES

Kolmogorov-Smirnov Test

2011-11-27T04:33:00.000-08:00

RANDOM NUMBER GENERATION
Test for Random Numbers

Testing for Uniformity

Refer : Kolmogorov-Smirnov Goodness-of-Fit Test for more detail explanation.

Q) Write a program for implementation of Testing for Uniformity in Kolmogorov-Smirnov Test using C++ .

ANS.

/* Program for  Kolmogorov-Smirnov Test */

#include<iostream.h>
#include<conio.h>
void main()
{
    clrscr();
    int n,i;
    float r[100];
    float cvalue,d,dplus,dminus,tplus,tminus;
    dplus=0;
    dminus=0;
    cout<<"enter critical value";
    cin>>cvalue;
    cout<<"please enter number of values";
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>r[i];
        tplus=float((i+1)/n)-r[i]);
        tminus=r[i]-float(i/n);
        if(tplus>dplus)
        {
        dplus=tplus;
        }
        if(tminus>dminus)
        {
        dminus=tminus;
        }
    }
    if(dplus>dminus)
    d=dplus;
    else
    d=dminus;
    cout<<d;
    if(d<cvalue)
    cout<<"uniform distribution is not rejected"<<endl;
    else
    cout<<"uniform distribution is rejected"<<endl;
    getch();
}

//output:
Enter critical value 15
Please enter number of values
2
5
6
uniform distribution is not rejected

Runs Up and Runs Down

2011-11-27T04:18:00.000-08:00

RANDOM NUMBER GENERATION
Test for Random Numbers

Testing for Independence

Runs Up and Runs Down

Q) Write a program for implementation of Testing for Independence in Runs Up and Runs Down using C++ .

ANS.

/* Program for Runs Up and Runs Down */

#include<iostream.h>
#include<math.h>
int main()
{
float N[10];
int n, count=0,1;
int c[10];
float mean , variance, variancesq, z0, za, z;
cout<<"\n Enter Critical Value: ";
cin>>a;
cout<<"\n Enter value of za/2: ";
cin>>za;
cout<<"\n Enter number of nos. : ";
cin>>n;
cout<<"\n Enter the nos.: ";
for(i=0;i<n;i++)
{
cin>>N[i];
}
for(i=0;i<n-1;i++)
{
if(N[i]<N[i+1])
{
cout<<"+";
c[i]=1;
}
else
{
cout<<"-";
c[i]=0;
}
}
for(i=0;i<n-1;i++)
{
if(c[i]!=c[i+1])
count++;
}
cout<<"\n No of Runs="<<count<<"\n";
mean=(2*n-1)/3;
variancesq=(16*n-29)/90;
variance=sqrt(variancesq);
z0=(a-mean)/variance;
if((za<z0)&&(z0<(0-za)))
cout<<"\n The numbers are independent";
else
cout<<"\n The numbers are auto-correlated and not independent";
return 0;
}


//OUTPUT:
Enter Critical Value: 0.05

Enter value of za/2: 1.96

Enter number of nos.10

Enter the nos.
0.15
0.27
0.37
0.10
0.50
0.60
0.80
0.70
0.59
-++-+++--
No of Runs=5

The numbers are auto-correlated and not independent

Stack Using Array Implementation In Java

2011-02-28T10:41:00.000-08:00

Stack Using Array Implementation In Java

import java.io.*;
class stk
{
int st[];
int max;
int top;
stk(int n)
{
max=n;
st=new int[n];
top=-1;
}
void push(int a)
{
int b;
b=a;
if(top==max-1)
{
System.out.println("\t\t*****stack is overflow!!!!!******\n");
}
else
{
top=top+1;
st[top]=b;
}
}
void pop()
{
if(top==-1)
{
System.out.println("\t\tstack is underflow!!!!!\n");
}
else
{
int temp;
temp=st[top];
top=top-1;
System.out.println(""+temp+"is deleted\n");
}
}
void display()
{
System.out.println("\n\t\tElements are:");
for(int i=0;i<=top;i++)
{
System.out.println(""+"\t\t"+st[i]);

}System.out.println("\n");
}
}
class m
{
static int ch;

public static void main(String args[])
{

stk obj=new stk(5);

do
{
try
{
BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

System.out.println("1:push");

System.out.println("2:pop");

System.out.println("3:display");
System.out.println("4:exit\n");
System.out.println("\t\tenter ur choice\t\t");
ch=Integer.parseInt(b.readLine());
switch(ch)

{
case 1:System.out.println("enterthe element to be inserted=");

int c=Integer.parseInt(b.readLine());
obj.push(c);
break;
case 2:
obj.pop();
break;
case 3:
obj.display();
break;
case 4:
System.out.println("exit");
break;
default:
System.out.println("invalid choice\n");
}}
catch(Exception e)
{
System.out.println(e);
}
}
while(ch!=4);
}
}

Selection Sort Implementation In JAVA

2011-02-28T10:39:00.000-08:00

Selection Sort Implementation In JAVA

Sorting Techniques

import java.io.DataInputStream; 

class SelectionSortImpl 

{ 

    private static void swap(int data[], int left, int right) 

    { 

    int temp = data[left]; 

    data[left] = data[right]; 

    data[right] = temp; 

    } 

    public static void Sort(int data[], int n) 

    { 

        int num = n; 

        int i; 

        int max; 

        while(num >0) 

        { 

            max=0; 

            for(i=1;i<num;i++) 

            { 

                if(data[max]<data[i]) 

                    max=i; 

            } 

            swap(data,max,num-1); 

            num--; 

        } 

    } 

} 

public class SelectionSort { 

    public static void main(String args[]) 

    { 

        DataInputStream in = new DataInputStream(System.in); 

        System.out.println("Enter the array to be sorted"); 

        int data[]=new int[10]; 

        try 

        { 

        for(int i=0;i<10;i++) 

            data[i]=Integer.parseInt(in.readLine()); 

        } 

        catch(Exception e) {} 

        SelectionSortImpl.Sort(data, 10); 

        System.out.println("Sorted array:"); 

        for(int i=0;i<10;i++) 

            System.out.println(+data[i]); 

    } 

} 

-----------------------Output------------------------------------------------- 

-------------------------------------------------------------------------------- 

Enter the array to be sorted 

45 

12 

78 

1 

7 

14 

90 

27 

9 

47 

Sorted array: 

1 

7 

9 

12 

14 

27 

45 

47 

78 

90

Radix Sort Implementation In Java

2011-02-28T10:36:00.000-08:00

Radix Sort Implementation In Java

Sorting Techniques

import java.io.*;
class node1
      {
        int data;
        node1 next;
     node1(int n)
       {
    data=n;
    next=null;
       }

}
class list
   {
node1 last[]=new node1[10];
node1 bucket[]=new node1[10];
node1 current;
int i,digit,divisor,d,j,k;
list()
{}
void radix_sort(int x[],int n,int m)
{
for(digit=1;digit<=m;digit++)
{
     for( i=0;i<10;i++)
last[i]=bucket[i]=null;
divisor=1;
for(k=1;k<=digit-1;k++)
divisor=divisor*10;
for(i=0;i<n;i++)
    {
   node1 temp=new node1(x[i]);
d=(x[i]/divisor)%10;
if(bucket[d]==null)
bucket[d]=last[d]=temp;
else
{
last[d].next=temp;
last[d]=temp;
}
}
j=0;
for(i=0;i<10;i++)
    {
    current=bucket[i];
      while(current!=null)
    {
        x[j]=current.data;
    j++;
current=current.next;
    }
     }
}
}

}
class radix1
{
public static int c=0;
public static void main(String args[]) throws IOException
{
int a[],n,m;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   list l=new list();
System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
System.out.println("Enter no of digits = ");
m = Integer.parseInt(b.readLine());
a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   l.radix_sort(a,n,m);
   System.out.println(" Sorted Array is : ");
   for(int i=0;i<n;i++)
   {
    System.out.println(a[i]+" ");
   }
}
}

/*   OUTPUT

Enter size of array =
10
Enter no of digits =
3
Enter values =
321
123
345
456
567
876
897
213
113
296
Sorted Array is :
113
123
213
296
321
345
456
567
876
897
*/

Quick SOrt Recursive Implementation In Java

2011-02-28T10:34:00.000-08:00

Quick Sort Recursive Implementation In Java

Sorting Techniques

import java.io.*;

class QuickSortImple
{

static void swap(int data[], int left, int right)
{
int temp = data[left];
data[left] = data[right];
data[right] = temp;
}

private static int partition(int data[], int left, int right)
{
    while(true)
    {
        while(left < right && data[left] < data[right])
            right--;

        if(left<right)
        {
            swap(data, left, right);
            left++;
        }
        else
            return left;

        while(left < right && data[left] < data[right])
            left++;

        if(left<right)
        {
            swap(data, left, right);
            right--;
        }
        else
            return right;
    }
}

private static void quickSortRecursive(int data[], int left, int right)
{
    int pivot;
    if(left >= right) return;

    pivot = partition(data,left,right);
    quickSortRecursive(data,left,pivot-1);
    quickSortRecursive(data,pivot+1,right);
}

public static void quickSortP(int data[], int n)
{
    quickSortRecursive(data,0,n-1);
}
}

class QuickSort
{
    public static void main(String args[])
    {
        DataInputStream in = new DataInputStream(System.in);
        System.out.println("Enter the array to be sorted");
        int data[]=new int[10];
        try
        {
        for(int i=0;i<10;i++)
            data[i]=Integer.parseInt(in.readLine());
        }
        catch(Exception e) {}

        QuickSortImple.quickSortP(data, 10);

        System.out.println("Sorted array:");
        for(int i=0;i<10;i++)
            System.out.println(+data[i]);
    }
}

-------------------------------Output------------------------------------------
---------------------------------------------------------------------------------
Enter the array to be sorted
4
7
12
78
34
7
19
1
6
35
Sorted array:
1
4
6
7
7
12
19
34
35
78

Quick Sort Implementation In Java

2011-02-28T10:32:00.000-08:00

Quick Sort Implementation In Java

Sorting Techniques

import java.io.*;

class quick
{
public static int a[];
public static void main(String args[]) throws IOException
{
int a[],n;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   quick_sort(a,0,n-1);
for(int i=0;i<n;i++)
System.out.println("\n sorted array is"+a[i]);
}

public static void quick_sort(int x[],int lb, int ub)
{
int j;
if(lb>=ub)
    return;
j=partition(x,lb,ub);
quick_sort(x,lb,j-1);
quick_sort(x,j+1,ub);
}
public static int partition(int x[],int lb,int ub)
     {
    int a,temp,up,down;
    a=x[lb];
    up=ub;
    down=lb;

    while(down<up)
    {
    while(x[down]<=a && down<up)
        down++;
    while(x[up]>a)
    up--;
    if(down<up)
       {
        temp=x[up];
        x[up]=x[down];
        x[down]=temp;
       }
    }
x[lb]=x[up];
x[up]=a;
return up;
}
}

Queue Using Array Implementation In JAVA

2011-02-28T10:29:00.000-08:00

Queue Using Array Implementation In JAVA

import java.io.*;
class queue
{
int q[];
int front;
int rear;
int temp;
int max;
queue(int n)
{
max=n;
q=new int[max];
front=0;
rear=-1;
}
void push(int a)
{
int b;
b=a;
if(rear>=max-1)
{
System.out.println("\t\t*****queue is overflow!!!!!******\n");
}
else
{
rear=rear+1;
q[rear]=b;

}
}
void pop()
{
if(rear<front)
{
System.out.println("\t\tstack is underflow!!!!!\n");
}
else
{
System.out.println(""+q[front]+"is deleted\n");
front=front+1;

}
}
void display()
{
System.out.println("\n\t\tElements are:");
for(int i=front;i<=rear;i++)
{
System.out.println(""+"\t\t"+q[i]);

}System.out.println("\n");
}
}
class q1
{
static int ch;

public static void main(String args[])
{

queue obj=new queue(5);

do
{
try
{
BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

System.out.println("1:push");

System.out.println("2:pop");

System.out.println("3:display");
System.out.println("4:exit\n");
System.out.println("\t\tenter ur choice\t\t");
ch=Integer.parseInt(b.readLine());
switch(ch)

{
case 1:System.out.println("enterthe element to be inserted=");

int c=Integer.parseInt(b.readLine());
obj.push(c);
break;
case 2:
obj.pop();
break;
case 3:
obj.display();
break;
case 4:
System.out.println("exit");
break;
default:
System.out.println("invalid choice\n");
}}
catch(Exception e)
{
System.out.println(e);
}
}
while(ch!=4);
}
}

Queue Implementation In JAVA

2011-02-28T10:26:00.000-08:00

Queue Implementation In JAVA

import java.io.*;
class Queue
{
    int size = 10;
    int que[];
    int rear, front;

    Queue()
    {
        que = new int[size];
        rear = -1;
        front = 0;
    }

    void insert(int x)
    {
        if(rear==size)
            System.out.println("Queue is full");
        else if(rear == -1)
        {
            que[++rear] = x;
            front++;
        }
        else
            que[++rear] = x;
    }

    void delete()
    {
        if(front == -1)
            System.out.println("Queue is empty");
        else if(rear == front)
            rear = front = -1;
        else
            front++;
    }

    void display()
    {
        for(int i=front; i<=rear;i++)
            System.out.print("\t"+que[i]);

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

class QueueImpl
{
    public static void main(String args[])
    {
        DataInputStream in = new DataInputStream(System.in);
        Queue q= new Queue();
        q.insert(6);
        q.insert(13);
        q.insert(2);
        q.insert(19);
        q.insert(10);
        q.insert(7);


        q.delete();
        q.delete();
        System.out.println("Initial Queue");
        q.display();

        int ch = 4;
        do
        {
        System.out.println("What operation you wan to perform?:");
        System.out.println("1. Insert an element in queue");
        System.out.println("2. Delete an element from queue");
        System.out.println("3. Display queue");
        System.out.println("4. Quit");



        try {
            ch= Integer.parseInt(in.readLine());}
        catch(Exception e) { }
        int x = 0;
        switch(ch)
        {
            case 1:
                System.out.println("Enter the element");
                try {
                    x= Integer.parseInt(in.readLine());}
                catch(Exception e) { }

                q.insert(x);
                System.out.println("Now the Queue is:");
                q.display();
                break;

            case 2:
                q.delete();
                System.out.println("Element deleted");
                System.out.println("Now the Queue is:");
                q.display();
                break;

            case 3:
                q.display();
                break;

            default:
                System.out.println("Wrong choice");
        }
        } while (ch!=4);
    }
}

------------------------------------Output----------------------------------
-----------------------------------------------------------------------------
Initial Queue
        19      10      7
What operation you wan to perform?:
1. Insert an element in queue
2. Delete an element from queue
3. Display queue
4. Quit
1
Enter the element
23
Now the Queue is:
        19      10      7       23
What operation you wan to perform?:
1. Insert an element in queue
2. Delete an element from queue
3. Display queue
4. Quit
1
Enter the element
67
Now the Queue is:
        19      10      7       23      67
What operation you wan to perform?:
1. Insert an element in queue
2. Delete an element from queue
3. Display queue
4. Quit
2
Element deleted
Now the Queue is:
        10      7       23      67
What operation you wan to perform?:
1. Insert an element in queue
2. Delete an element from queue
3. Display queue
4. Quit
1
Enter the element
12
Now the Queue is:
        10      7       23      67      12
What operation you wan to perform?:
1. Insert an element in queue
2. Delete an element from queue
3. Display queue
4. Quit
4
Wrong choice

Prims Algorithms Implementation In Java

2011-02-28T10:23:00.000-08:00

Prims Algorithms Implementation In Java

MINIMUM COST SPANNING TREE

import java.io.*;
import java.util.*;

class Graph
{   int weight[][]=new int[20][20];
   int visited[]=new int [20];
   int d[]=new int[20];
   int p[]=new int[20];
   int v,e;
   void creategraph()throws IOException
   {
       int i,j,a,b,w;
                     BufferedReader in=new BufferedReader( new InputStreamReader(System.in));
       System.out.print("\nEnter number of vertices :");
       v=Integer.parseInt(in.readLine());
       System.out.print("\nEnter number of Edges :");
       e=Integer.parseInt(in.readLine());
       for ( i=1;i<=v;i++)
           for( j=1;j<=v;j++)
               weight[i][j]=0;

       for (i=1;i<=v;i++)
           {
           p[i]=visited[i]=0;
           d[i]=32767;
           }
       for ( i=1;i<=e;i++)
       {
       System.out.print("\nEnter edge a,b and weight w :");
       a=Integer.parseInt(in.readLine());
       b=Integer.parseInt(in.readLine());
       w=Integer.parseInt(in.readLine());
       weight[a][b]=weight[b][a]=w;
       }

   }

   void algo ()throws IOException
   {
   creategraph();
      int current,total,mincost,i;
      current=1;d[current]=0;
       total=1;
       visited[current]=1;
       while(total!=v)
       {
          for (i=1;i<=v;i++)
           {
       if(weight[current][i]!=0)
          if(visited[i]==0)
          if(d[i]>weight[current][i])
                            {
               d[i]=weight[current][i];
                p[i]=current;
               }
                    }
   mincost=32767;
      for (i=1;i<=v;i++)
        {
            if(visited[i]==0)
            if(d[i]<mincost)
       {
       mincost=d[i];
       current=i;
           }
      }
   visited[current]=1;
   total++;
       }
   mincost=0;
   for(i=1;i<=v;i++)
   mincost=mincost+d[i];
   System.out.print("\n Minimum cost="+mincost);
   System.out.print("\n Minimum Spanning tree is");

   for(i=1;i<=v;i++)
   System.out.print("\n vertex" +i+"is connected to"+p[i]);
}
}
class prims
{
public static void main(String args[])throws IOException
{
   Graph g=new Graph();
   g.algo();
}
}

/*

Enter number of vertices :5

Enter number of Edges :7

Enter edge a,b and weight w :1
2
2

Enter edge a,b and weight w :1
5
8

Enter edge a,b and weight w :2
3
6

Enter edge a,b and weight w :2
4
12

Enter edge a,b and weight w :2
5
7

Enter edge a,b and weight w :4
5
4

Enter edge a,b and weight w :3
4
10

Minimum cost=19
Minimum Spanning tree is
vertex1is connected to0
vertex2is connected to1
vertex3is connected to2
vertex4is connected to5
vertex5is connected to2
*/

Merge Recursive Sort Implementation In Java

2011-02-28T10:19:00.000-08:00

Merge Recursive Sort Implementation In Java

Sorting Techniques

import java.io.*;

class MergeSort {
    private static void merge(int data[], int temp[], int low, int middle,int high)
    {
        int i=low;
        int j= middle;
        int k=low;

        while(i<middle && j<=high)
        {
            if(temp[i] < data[j])
            {
                data[k] = temp[i];
                k++;
                i++;
            }
            else
            {
                data[k]=data[j];
                k++;
                j++;
            }
        }

        while(i<middle)
        {
            data[k]=temp[i];
            k++;
            i++;
        }
    }

    private static void mergeSortRecursive(int data[], int temp[],
            int low, int high)
    {
        int n=high-low+1;
        int middle = low + n/2;
        int i;

        if(n<2)
            return;

        for(i=low;i<middle;i++)
            temp[i] = data[i];

        mergeSortRecursive(temp,data, low,middle-1);
        mergeSortRecursive(data,temp,middle,high);
        merge(data,temp,low,middle,high);
    }

    public static void mergeSortP(int data[], int n)
    {
        mergeSortRecursive(data, new int[n], 0, n-1);
    }

}

class MergeSortImpl
{
    public static void main(String args[])
    {
        DataInputStream in = new DataInputStream(System.in);
        System.out.println("Enter the array to be sorted");
        int data[]=new int[10];
        try
        {
        for(int i=0;i<10;i++)
            data[i]=Integer.parseInt(in.readLine());
        }
        catch(Exception e) {}

        MergeSort.mergeSortP(data, 10);

        System.out.println("Sorted array:");
        for(int i=0;i<10;i++)
            System.out.println(+data[i]);
    }
}

------------------------------Output---------------------------------------------
-----------------------------------------------------------------------------------
Enter the array to be sorted
4
7
1
90
3
67
23
12
67
2
Sorted array:
1
2
3
4
7
12
23
67
67
90

Merge Sort Implementation In Java

2011-02-28T10:15:00.000-08:00

Merge Sort Implementation In Java

Sorting Techniques

import java.io.*;

class merge
{
public static int a[];
public static void main(String args[]) throws IOException
{
int n;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   merge(0,n-1);
   System.out.println(" Sorted Array is = ");
   for( int i=0;i<n;i++)
    System.out.println(a[i]+" ");
}

public static void simplemerge(int f,int s,int t)
{
int i,j,k,w;
int temp[] = new int[10] ;
i=f; j=s; k=-1;
while(i<=(s-1) && j<=t)
{
if(a[i]<a[j])
   temp[++k] =a[i++];
else
   temp[++k]=a[j++];
}
if(i>(s-1))
{
for(w=j;w<=t;w++)
   temp[++k]=a[w];
}
else
{
for(w=i;w<=s-1;w++)
   temp[++k]=a[w];
}
for(w=0;w<=k;w++)
a[f+w]=temp[w];
}

public static void merge(int l, int r)
{
int mid;
if(l<r)
{
mid=(l+r)/2;
merge(l, mid);
merge(mid+1,r);
simplemerge(l, mid+1,r);
}
}
}

Matrix Operations Implementation In Java

2011-02-28T10:12:00.000-08:00

Matrix Operations Implementation In Java

import java.io.*;
class Matrix
{
    public static void main(String args[])
    {
        DataInputStream in=new DataInputStream(System.in);
        int a[][]=new int[3][3];
        int b[][]=new int[3][3];
        int c[][]=new int[3][3];
        int i,j,k;
        try
        {
        System.out.println("Enter 1st matrix:\n");
        for(i=0;i<3;i++)
            for(j=0;j<3;j++)
                a[i][j] = Integer.parseInt(in.readLine());

        System.out.println("Enter 2nd matrix:\n");
        for(i=0;i<3;i++)
            for(j=0;j<3;j++)
                b[i][j] = Integer.parseInt(in.readLine());

        System.out.println("Enter the option:");
        System.out.println("A. Matrix Addition");
        System.out.println("B. Matrix subtraction");
        System.out.println("C. Matrix Multiplication");
        char s = (char)System.in.read();
        System.out.println("You entered " + s);
        switch(s)
        {
            case 'A':
            case 'a':
                for(i=0;i<3;i++)
                    for(j=0;j<3;j++)
                        c[i][j] = a[i][j]+b[i][j];
                break;

            case 'B':
            case 'b':
                for(i=0;i<3;i++)
                    for(j=0;j<3;j++)
                        c[i][j] = a[i][j]-b[i][j];
                break;

            case 'C':
            case 'c':
                for(i=0;i<3;i++)
                    for(j=0;j<3;j++)
                        for(k=0;k<3;k++)
                            c[i][j] = c[i][j] + a[i][k]*b[k][j];
                break;

            default:
                System.out.println("\nPlease enter a valid option");
        }

        System.out.println("Result matrix:\n");
        for(i=0;i<3;i++)
        {
            for(j=0;j<3;j++)
                System.out.println("\t" + c[i][j]);
        System.out.println("\n");
        }
        }
        catch(Exception e) {}
    }
}

-----------------------------Output--------------------------------------------
--------------------------------------------------------------------------------
Enter 1st matrix:

1    2    3
1    2    3
1    2    3
Enter 2nd matrix:

5    6    7
4    5    6
3    4    5
Enter the option:
A. Matrix Addition
B. Matrix subtraction
C. Matrix Multiplication
A
You entered A
Result matrix:

        6        8        10
        5        7        9
        4        6        8

Enter 1st matrix:

1    2    3
1    2    3
1    2    3
Enter 2nd matrix:

1    2    1
3    4    5
7    9    5
Enter the option:
A. Matrix Addition
B. Matrix subtraction
C. Matrix Multiplication
B
You entered B
Result matrix:

        0        0        2
        -2       -2       -2
        -6       -7       -2

Enter 1st matrix:

1    2    3
1    2    3
1    2    3
Enter 2nd matrix:

4    5    6
4    5    6
4    5    6
Enter the option:
A. Matrix Addition
B. Matrix subtraction
C. Matrix Multiplication
C
You entered C
Result matrix:

        24        30        36
        24        30        36
        24        30        36

Linked List Implementation In Java

2011-02-28T10:10:00.000-08:00

Linked List Implementation In Java

import java.io.*; 

class Node 

{ 

    private int element; 

    private Node next; 

    static Node head; 

    static Node tail; 

    public Node() 

    { 

    } 

    public Node(int e, Node n) 

    {     

        element = e; 

        next = n; 

    } 

    public int getElement() 

    {     

        return element; 

    } 

    public Node getNext() 

    {     

        return next; 

    } 

    public void setElement(int e) 

    {     

        element = e; 

    } 

    public void setNext(Node n) 

    {     

        next = n; 

    } 

    public void insert(int e) 

    {     

        Node n=new Node(); 

        n.setElement(e); 

        n.setNext(this.getNext()); 

        this.setNext(n);     

    } 

    public void delete(int e) 

    {     

        Node n=new Node(); 

        Node prev = new Node(); 

        n.setNext(head.getNext()); 

        n = n.getNext(); 

        if (head.getNext() != null) 

        {     

            do 

            { 

                if(n.getElement() == e)                     

                    prev.setNext(n.getNext()); 

                prev= n; 

                n = n.getNext(); 

            }     

            while(n.getNext()!=null); 

        } 

    } 

    public void display() 

    {     

        Node n=new Node();         

        n.setNext(head.getNext()); 

        n = n.getNext(); 

        if (head.getNext() != null) 

        {     

            do 

            {                 

                System.out.println(n.getElement()); 

                n = n.getNext(); 

            }     

            while(n.getNext()!=null); 

        System.out.println(n.getElement()); 

        } 

    } 

} 

class LinkedList 

{ 

    public static void main(String args[]) 

    { 

        Node n1=new Node(); 

        Node n2=new Node(); 

        Node n3=new Node(); 

        Node n4=new Node(); 

        Node n5=new Node(); 

        Node.head = new Node(); 

        Node.tail = new Node(); 

        n1.setElement(5); 

        n1.setNext(n2); 

        n2.setElement(10);         

        n2.setNext(n3); 

        n3.setElement(20);         

        n3.setNext(n4); 

        n4.setElement(5); 

        n4.setNext(n5); 

        n5.setElement(17); 

        Node.head.setNext(n1); 

        Node.tail.setNext(n5); 

        n1.display(); 

        System.out.println(); 

        n1.insert(76); 

        n1.display(); 

        System.out.println(); 

        n1.delete(10); 

        n1.display(); 

    } 

} 

----------------------------------Output------------------------------ 

---------------------------------------------------------------------- 

5 

10 

20 

5 

17 

5 

76 

10 

20 

5 

17 

5 

76 

20 

5 

17

Heap Sort Implementation In Java

2011-02-28T10:08:00.000-08:00

Heap Sort Implementation In Java

Sorting Techniques

import java.io.*;

class heap
{
public static int c=0;
public static void main(String args[]) throws IOException
{
int a[],n;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   heap(a,n);
   System.out.println(" Sorted Array is : ");
   for(int i=0;i<n;i++)
   {
    System.out.println(a[i]+" ");
   }
}

public static void heap(int a[],int n)
{
int i,s,f,elt,v;
for(i=1; i<n; i++)
{
    elt=a[i];
    s=i;
    f=(s-1)/2;
    while(s>0 && a[f]<elt)
    {
      a[s]=a[f];
      s=f;
      f=(s-1)/2;
    }
    a[s]=elt;
   c++;
}
for(i=n-1; i>0; i--)
{
    v=a[i];
    a[i]=a[0];
    f=0;
    if(i==1)
    s=-1;
    else
    s=1;
    if(i>2 && a[2]>a[1])
    s=2;
    while(s>=0 && v<a[s])
    {
      a[f]=a[s];
      f=s;
      s=2*f+1;
      if((s+1)<=i-1 && a[s]<a[s+1])
    s=s+1;
      if(s>(i-1))
    s=-1;
     }
     a[f]=v;
    }
}
}

Hash Search Implementation In Java

2011-02-28T10:05:00.000-08:00

Hash Search Implementation In Java

Search Tree

import java.io.*;
class hash
{
public static int a[],ht[];
public static void main(String args[]) throws IOException
{
int a[],n,ch,size;

   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   System.out.println("Enter the size of hash table = ");
   size=Integer.parseInt(b.readLine());
    for(int i=0;i<size;i++)
     ht= new int[size];
    store(a,n,ht,size);
do
        {
                  hashsearch(b,size);
System.out.println("\n Do you want to continue press 1");
ch=Integer.parseInt(b.readLine());
}while(ch==1);
}

public static void store(int x[],int n,int ht[],int size)
{
int i,key,address;

for(i=0;i<10;i++)
ht[i]=-1;
for(i=0;i<n;i++)
{
key=x[i];
address=modulodivison(key,size);
if(ht[address]!=-1)
address=linearprobe(address,size);
ht[address]=key;
}
}
public static int modulodivison(int key,int size)
{
   int address;
   address=(key%size)+1;
   if(address<size)
           return address;
   else
     return 0;
}

public static int linearprobe(int address,int size)
    {
        while(ht[address]!=-1)
    {
        address++;
       if(address==size)
        address=0;
    }
return address;
}

public static void hashsearch(BufferedReader br,int size)throws IOException
    {
int key,address;
System.out.println("enter the element to be searched");
key=Integer.parseInt(br.readLine());
address=modulodivison(key,size);
while(ht[address]!=-1 && ht[address]!=key)
   {
    address++;
           if(address==size)
    address=0;
}
if(ht[address]==-1)
System.out.println(key +"key is not found");
else
System.out.println(key+"key is found at address"+address);
}}

/*              output

Enter size of array =
8
Enter values =
35
66
44
22
84
29
78
57
Enter the size of hash table =
10
enter the element to be searched
78
78key is found at address9

Do you want to continue press 1
1
enter the element to be searched
57
57key is found at address1

Do you want to continue press 1
1
enter the element to be searched
84
84key is found at address8

Do you want to continue press 1
2

*/

Bucket Sort Implementation In Java

2011-02-28T09:59:00.000-08:00

Bucket Sort Implementation In Java

Sorting Techniques

import java.io.*;
class node1
      {
        int data;
        node1 next;
     node1(int n)
       {
    data=n;
    next=null;
       }

}
class list
   {
node1 last[]=new node1[10];
node1 bucket[]=new node1[10];
node1 current;
int i;
list()
{}
void bucket_sort(int x[],int n)
{
for( i=0;i<10;i++)
last[i]=bucket[i]=null;
for(i=0;i<n;i++)
    {
   node1 temp=new node1(x[i]);
if(bucket[x[i]]==null)
bucket[x[i]]=last[x[i]]=temp;
else
    {
     last[x[i]].next=temp;
    last[x[i]]=temp;
   }
}
int j=0;
for(i=0;i<10;i++)
    {
current=bucket[i];
while(current!=null)
    {
x[j]=current.data;
    j++;
current=current.next;
}
}
}
}

class bucket1
{
public static int c=0;
public static void main(String args[]) throws IOException
{
int a[],n;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
   list l=new list();
System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   l.bucket_sort(a,n);
   System.out.println(" Sorted Array is : ");
   for(int i=0;i<n;i++)
   {
    System.out.println(a[i]+" ");
   }
}
}

Depth First Search Implementation in Java

2011-02-28T09:52:00.000-08:00

Depth First Search Implementation in Java

Graph Traversals

import java.io.*;

import java.util.*; 

class Stack 

{

    int stk[]=new int[10]; 

    int top; 

    Stack() 

{

        top=-1; 

}

    void push (int item) 

{

        if (top==9) 

            System.out.println("Stack overflow"); 

        else 

            stk[++top]=item; 

    }/*end push*/ 

    boolean isempty() 

{

        if (top<0) 

            return true; 

        else 

            return false; 

    }/*end isempty*/ 

    int pop() 

{

        if (isempty()) 

{

            System.out.println("Stack underflow"); 

            return 0; 

}

        else 

            return (stk[top--]); 

    }/*end pop*/ 

    void stacktop() 

{

        if(isempty()) 

            System.out.println("Stack underflow "); 

        else 

            System.out.println("Stack top is "+(stk[top])); 

    }/*end stacktop*/ 

    void display() 

{

        System.out.println("Stack-->"); 

        for(int i=0;i<=top;i++) 

            System.out.println(stk[i]); 

    }/*end display*/ 

}

class Graph 

{

    int MAXSIZE=51; 

    int adj[][]=new int[MAXSIZE][MAXSIZE]; 

    int visited[]=new int [MAXSIZE]; 

    Stack s=new Stack(); 

    /*Function  for Depth-First-Search    */ 

    void createGraph() 

{

        int n,i,j,parent,adj_parent,initial_node; 

        int  ans=0,ans1=0; 

        System.out.print("\nEnter total number elements in a Undirected Graph :"); 

        n=getNumber(); 

        for ( i=1;i<=n;i++) 

            for( j=1;j<=n;j++) 

                adj[i][j]=0; 

        /*All graph nodes are unvisited, hence assigned zero to visited field of each node */ 

        for (int c=1;c<=50;c++) 

            visited[c]=0; 

        System.out.println("\nEnter graph structure for BFS  "); 

do

{

            System.out.print("\nEnter parent node :"); 

            parent=getNumber(); 

do

{

                System.out.print("\nEnter adjacent node for node "+parent+ " : "); 

                adj_parent=getNumber(); 

                adj[parent][adj_parent]=1; 

                adj[adj_parent][parent]=1; 

                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?"); 

                ans1= getNumber(); 

            } while (ans1==1); 

            System.out.print("\nContinue to add graph node?"); 

            ans= getNumber(); 

        }while (ans ==1); 

        System.out.print("\nAdjacency matrix for your graph is :\n"); 

        for (i=1;i<=n;i++) 

{

            for (j=1;j<=n;j++) 

            System.out.print(" "+adj[i][j]); 

            System.out.print("\n"); 

}

        System.out.println("\nYour Undirected Graph is :"); 

        for (i=1;i<=n;i++) 

{

            System.out.print("\nVertex "+i+"is connected to : "); 

            for (j=1;j<=n;j++) 

{

            if (adj[i][j]==1) 

            System.out.print(" "+j); 

}

}

        System.out.println("\nEnter the initial node for BFS traversal:"); 

        initial_node=getNumber(); 

        DFS (initial_node, n); 

}

    void DFS (int initial_node,int n) 

{

        int u,i; 

        s.top = -1; 

        s.push(initial_node); 

        System.out.println("\nDFS traversal for given graph is : "); 

        while(!s.isempty()) 

{

            u=s.pop(); 

            if(visited[u]==0) 

{

                System.out.print("\n"+u); 

                visited[u]=1; 

}

            for (i=1;i<=n;i++) 

{

                if((adj[u][i]==1) && (visited[i]==0)) 

{

                    s.push(u); 

                    visited[i]=1; 

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

                    u = i; 

}

}

}

    }/*  end of DFS function  */ 

    int getNumber() 

{

          String str; 

          int ne=0; 

          InputStreamReader input=new InputStreamReader(System.in); 

          BufferedReader in=new BufferedReader(input); 

try

{

              str=in.readLine(); 

              ne=Integer.parseInt(str); 

}

          catch(Exception e) 

{

             System.out.println("I/O Error"); 

}

          return ne; 

}

}

class Graph_DFS 

{

    public static void main(String args[]) 

{

        Graph g=new Graph(); 

        g.createGraph(); 

    }         /*  end of program */ 

}

/*

Sample Input and Output : 

Enter total number elements in a Undirected Graph :9 

Enter graph structure for BFS 

Enter parent node :1 

Enter adjacent node for node 1 : 2 

Continue to add adjacent node for 1(1/0)?1 

Enter adjacent node for node 1 : 3 

Continue to add adjacent node for 1(1/0)?0 

Continue to add graph node?1 

Enter parent node :2 

Enter adjacent node for node 2 : 4 

Continue to add adjacent node for 2(1/0)?1 

Enter adjacent node for node 2 : 5 

Continue to add adjacent node for 2(1/0)?0 

Continue to add graph node?1 

Enter parent node :3 

Enter adjacent node for node 3 : 5 

Continue to add adjacent node for 3(1/0)?0 

Continue to add graph node?1 

Enter parent node :4 

Enter adjacent node for node 4 : 6 

Continue to add adjacent node for 4(1/0)?1 

Enter adjacent node for node 4 : 7 

Continue to add adjacent node for 4(1/0)?0 

Continue to add graph node?1 

Enter parent node :5 

Enter adjacent node for node 5 : 8 

Continue to add adjacent node for 5(1/0)?0 

Continue to add graph node?1 

Enter parent node :6 

Enter adjacent node for node 6 : 9 

Continue to add adjacent node for 6(1/0)?0 

Continue to add graph node?0 

Adjacency matrix for your graph is : 

 0 1 1 0 0 0 0 0 0 

 1 0 0 1 1 0 0 0 0 

 1 0 0 0 1 0 0 0 0 

 0 1 0 0 0 1 1 0 0 

 0 1 1 0 0 0 0 1 0 

 0 0 0 1 0 0 0 0 1 

 0 0 0 1 0 0 0 0 0 

 0 0 0 0 1 0 0 0 0 

 0 0 0 0 0 1 0 0 0 

Your Undirected Graph is : 

Vertex 1is connected to :  2 3 

Vertex 2is connected to :  1 4 5 

Vertex 3is connected to :  1 5 

Vertex 4is connected to :  2 6 7 

Vertex 5is connected to :  2 3 8 

Vertex 6is connected to :  4 9 

Vertex 7is connected to :  4 

Vertex 8is connected to :  5 

Vertex 9is connected to :  6 

Enter the initial node for BFS traversal: 

1

DFS traversal for given graph is : 

1 2 4 6 9 7 5 8 3 

*/

Breath First Search Implementation In Java

2011-02-28T09:46:00.000-08:00

Breath First Search Implementation In Java
Graph Traversals

import java.io.*; 

import java.util.*; 

class Queue 

{ 

                 int items[]=new int[10]; 

    int front,rear; 

    Queue() 

    { 

        front=0; 

        rear=-1; 

    } 

    void insert(int e) 

    { 

    if(rear==9) 

            System.out.println("Queue overflow"); 

        else 

        { 

            items[++rear]=e; 

        } 

    } 

    int empty() 

    { 

        return(rear<front? 1:0); 

    } 

    int remove() 

    { 

        int x=0; 

        if(empty()==1) 

        { 

            System.out.println("Queue Underflow"); 

            return 0; 

        } 

        else 

        { 

            x=items[front++]; 

            return x; 

        } 

    } 

} 

class Graph 

{ 

    int MAXSIZE=51; 

    int adj[][]=new int[MAXSIZE][MAXSIZE]; 

    int visited[]=new int [MAXSIZE]; 

    Queue q=new Queue(); 

    void createGraph()throws IOException 

    { 

        int n,i,j,parent,adj_parent,initial_node; 

        int  ans=0,ans1=0; 

         BufferedReader in=new BufferedReader( new InputStreamReader(System.in)); 

        System.out.print("\nEnter total number elements in a Undirected Graph :"); 

        n=Integer.parseInt(in.readLine()); 

        for ( i=1;i<=n;i++) 

            for( j=1;j<=n;j++) 

                adj[i][j]=0; 

        for (int c=1;c<=50;c++) 

            visited[c]=0; 

        System.out.println("\nEnter graph structure for BFS  "); 

        do 

        { 

            System.out.print("\nEnter parent node :"); 

            parent=Integer.parseInt(in.readLine()); 

            do 

            { 

                System.out.print("\nEnter adjacent node for node "+parent+ " : "); 

                adj_parent=Integer.parseInt(in.readLine()); 

                adj[parent][adj_parent]=1; 

                adj[adj_parent][parent]=1; 

                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?"); 

                ans1= Integer.parseInt(in.readLine()); 

            } while (ans1==1); 

            System.out.print("\nContinue to add graph node press 1?"); 

            ans= Integer.parseInt(in.readLine()); 

        }while (ans ==1); 

        System.out.print("\nAdjacency matrix for your graph is :\n"); 

        for (i=1;i<=n;i++) 

        { 

            for (j=1;j<=n;j++) 

                System.out.print(" "+adj[i][j]); 

            System.out.print("\n"); 

        } 

        System.out.println("\nYour Undirected Graph is :"); 

        for (i=1;i<=n;i++) 

        { 

            System.out.print("\nVertex "+i+"is connected to : "); 

            for (j=1;j<=n;j++) 

            { 

                if (adj[i][j]==1) 

                System.out.print(" "+j); 

            } 

        } 

        System.out.println("\nEnter the initial node for BFS traversal:"); 

        initial_node=Integer.parseInt(in.readLine()); 

        BFS (initial_node, n); 

    } 

     void BFS (int initial_node,int n) 

    { 

      int u,i; 

      u = initial_node; 

      visited[initial_node]=1; 

      System.out.println("\nBFS traversal for given graph is : "); 

      System.out.print(initial_node); 

      q.insert(initial_node); 

      while(q.empty()==0) 

      { 

                u = q.remove(); 

                  for (i=1;i<=n;i++) 

                 { 

                    if((adj[u][i]==1) && (visited[i]==0)) 

                    { 

                      q.insert(i); 

                      visited[i]=1; 

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

                     } 

                  } 

        } 

    } 

} 

class bgraph 

{ 

public static void main(String args[])throws IOException 

{ 

    Graph g=new Graph(); 

    g.createGraph(); 

} 

} 

/* 

Enter total number elements in a Undirected Graph :7 

Enter graph structure for BFS 

Enter parent node :1 

Enter adjacent node for node 1 : 2 

Continue to add adjacent node for 1(1/0)?1 

Enter adjacent node for node 1 : 3 

Continue to add adjacent node for 1(1/0)?0 

Continue to add graph node press 1?1 

Enter parent node :2 

Enter adjacent node for node 2 : 4 

Continue to add adjacent node for 2(1/0)?1 

Enter adjacent node for node 2 : 5 

Continue to add adjacent node for 2(1/0)?0 

Continue to add graph node press 1?1 

Enter parent node :3 

Enter adjacent node for node 3 : 6 

Continue to add adjacent node for 3(1/0)?1 

Enter adjacent node for node 3 : 7 

Continue to add adjacent node for 3(1/0)?0 

Continue to add graph node press 1?0 

Adjacency matrix for your graph is : 

 0 1 1 0 0 0 0 

 1 0 0 1 1 0 0 

 1 0 0 0 0 1 1 

 0 1 0 0 0 0 0 

 0 1 0 0 0 0 0 

 0 0 1 0 0 0 0 

 0 0 1 0 0 0 0 

Your Undirected Graph is : 

Vertex 1is connected to :  2 3 

Vertex 2is connected to :  1 4 5 

Vertex 3is connected to :  1 6 7 

Vertex 4is connected to :  2 

Vertex 5is connected to :  2 

Vertex 6is connected to :  3 

Vertex 7is connected to :  3 

Enter the initial node for BFS traversal: 

1 

BFS traversal for given graph is : 

1 2 3 4 5 6 7 

Enter total number elements in a Undirected Graph :9 

Enter graph structure for BFS 

Enter parent node :1 

Enter adjacent node for node 1 : 2 

Continue to add adjacent node for 1(1/0)?1 

Enter adjacent node for node 1 : 3 

Continue to add adjacent node for 1(1/0)?0 

Continue to add graph node?1 

Enter parent node :2 

Enter adjacent node for node 2 : 4 

Continue to add adjacent node for 2(1/0)?1 

Enter adjacent node for node 2 : 5 

Continue to add adjacent node for 2(1/0)?0 

Continue to add graph node?1 

Enter parent node :3 

Enter adjacent node for node 3 : 5 

Continue to add adjacent node for 3(1/0)?0 

Continue to add graph node?1 

Enter parent node :4 

Enter adjacent node for node 4 : 6 

Continue to add adjacent node for 4(1/0)?1 

Enter adjacent node for node 4 : 7 

Continue to add adjacent node for 4(1/0)?0 

Continue to add graph node?1 

Enter parent node :5 

Enter adjacent node for node 5 : 8 

Continue to add adjacent node for 5(1/0)?0 

Continue to add graph node?1 

Enter parent node :6 

Enter adjacent node for node 6 : 9 

Continue to add adjacent node for 6(1/0)?0 

Continue to add graph node?0 

Adjacency matrix for your graph is : 

 0 1 1 0 0 0 0 0 0 

 1 0 0 1 1 0 0 0 0 

 1 0 0 0 1 0 0 0 0 

 0 1 0 0 0 1 1 0 0 

 0 1 1 0 0 0 0 1 0 

 0 0 0 1 0 0 0 0 1 

 0 0 0 1 0 0 0 0 0 

 0 0 0 0 1 0 0 0 0 

 0 0 0 0 0 1 0 0 0 

Your Undirected Graph is : 

Vertex 1is connected to :  2  3 

Vertex 2is connected to :  1  4  5 

Vertex 3is connected to :  1  5 

Vertex 4is connected to :  2  6  7 

Vertex 5is connected to :  2  3  8 

Vertex 6is connected to :  4  9 

Vertex 7is connected to :  4 

Vertex 8is connected to :  5 

Vertex 9is connected to :  6 

Enter the initial node for BFS traversal: 

1 

BFS traversal for given graph is : 

1 2 3 4 5 6 7 8 9 

*/

Binary Search Implementation In Java

2011-02-28T09:38:00.000-08:00

Binary Search Implementation In Java

import java.io.*;

class BinarySearchImpl
{
    public static int Search(int S[], int key, int low,int high)
    {
        if(low>high)
            return -1;
        else
        {
            int mid = (low+high)/2;
            if(key==S[mid])
                return mid+1; //as array starts from 0 and not 1
            else if (key<S[mid])
                return Search(S,key,low,mid-1);
            else
                return Search(S,key,mid+1,high);
        }
    }
}

public class BinarySearch {
    public static void main(String args[])
    {
        DataInputStream in = new DataInputStream(System.in);
        System.out.println("Enter the sorted array");
        int n=10,key=0;
        int data[]=new int[n];
        try
        {
        for(int i=0;i<10;i++)
            data[i]=Integer.parseInt(in.readLine());
        }
        catch(Exception e) {}

        System.out.println("Enter the element to be searched");
        try
        {
            key=Integer.parseInt(in.readLine());
        }
        catch(Exception e) {}

        int loc = BinarySearchImpl.Search(data, key, 0, n-1);

        if(loc==-1)
            System.out.println("the element could not be found");
        else
            System.out.println("the element is at position"+loc);

    }
}

--------------------------Output-----------------------------------------------------------
-------------------------------------------------------------------------------------------
Enter the sorted array
4
8
9
12
14
17
21
22
56
100
Enter the element to be searched
17
the element is at position6