Kruskal's algorithm's implementation in java

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Example run

Image	Description
	AD and CE are the shortest edges, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
	CE is now the shortest edge that does not form a cycle, with length 5, so it is highlighted as the second edge.
	The next edge, DF with length 6, is highlighted using much the same method.
	The next-shortest edges are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The edge BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen.
	The process continues to highlight the next-smallest edge, BE with length 7. Many more edges are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD.
	Finally, the process finishes with the edge EG of length 9, and the minimum spanning tree is found.

import java.io.*; 
class Tnode
{
char label;
//boolean vis;
int prev;
public Tnode(char lab) 
 { 
   label = lab; 
   //vis=false;
   prev=-1;
 } 
}

Prim's algorithm's implementation in java

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted, undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Example run

Image	U	possible edges	V \ U	Description
	{}		{A,B,C,D,E,F,G}	This is our original weighted graph. The numbers near the edges indicate their weight.
	{D}	{D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6	{A,B,C,E,F,G}	Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
	{A,D}	{D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7	{B,C,E,F,G}	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
	{A,D,F}	{D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11	{B,C,E,G}	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
	{A,B,D,F}	{B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11	{C,E,G}	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away fromB, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE.
	{A,B,D,E,F}	{B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11	{C,G}	Here, the only vertices available are C and G.C is 5 away from E, and G is 9 away from E.C is chosen, so it is highlighted along with the edge EC.
	{A,B,C,D,E,F}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11	{G}	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG.
	{A,B,C,D,E,F,G}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle	{}	Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Implementation:

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}

GATE 2013 Preparation tips

Important tips for Preparation:

Foremost thing is to prepare right from the day you want to plan for it. As it is a saying beginning is half success. If you wait for some good day to start, that good day will never come and eventually you will loose/waste your time gratuitously. 

Candidate must collect GATE 2013 syllabus copy and find the subjects asked during examination and segregate the subjects based on past questions and mark weightage of each subjects.

Dijkstra algorithm's implementation in java (From one source to one destination in Graph)

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts,i,min;
  public Tnode vlist[];
  public int adj[][];
  public graph()
  {
   nverts = 0;
   adj = new int[MAX][MAX];
   vlist = new Tnode[MAX];
   for(int i=0;i<MAX;i++)
 {
for(int j=0;j<MAX;j++)
adj[i][j] = 0;
 }
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new Tnode(lab);
  }
  public void addedge(int start,int end,int cost)
  {
    adj[start][end] = cost;
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs(int src, int dest)
  {
 int k;
 int path[]=new int[20];
 vlist[src].len=0;
 vlist[src].vis=true;
k=src;
do{
for(i=0;i<nverts;i++)
{
if((adj[k][i]!=0)&&(vlist[i].vis==false))
{
if(vlist[k].len+adj[k][i]<vlist[i].len)
{
vlist[i].prev=k;
vlist[i].len=vlist[k].len+adj[k][i];
}
}
}
k=0;
min=100000;
for(i=0;i<nverts;i++)
{
if((vlist[i].vis==false)&&(vlist[i].len<min))
{
min=vlist[i].len;
k=i;
}
}
vlist[k].vis=true;
 }while(k!=dest);
i=0;
k=dest;
int c=0;
do{
path[i++]=k;
c++;
k=vlist[k].prev;
}while(k>=0);
System.out.println("shortest path from source to destination is \n");
for(i=c-1;i>=0;i--)
System.out.print("-->"+vlist[path[i]].label);
System.out.println("\n shortest distance from source to destination is \n"+vlist[dest].len);
}
}

GATE 2013 useful preparation tips

GATE 2013 useful preparation tips

Get your fundamentals right:

It is important that you get your fundamentals right. GATE is one such exam which tests you on your fundamentals.

Take exercise:

After you gain full confidence in your fundamentals then go for the exercise for the each topic you studied, that will boast your confidence.

Solve previous year's papers:

To understand the pattern of the exam and get familiar with it, aspirants should solve the previous year's papers of GATE exam. It will also brushes up your basic concepts and exposes you to real exam pattern.

PGECET-2012 Admissions Vacancy Position in SVU region as on 17-12-2012

Left over seat in M.Tech Colleges in  SVU region.
Student who are not qualified in PGECET or who are not allotted in PGECET Counselling can get seat in left over seats in spot admission.

PGECET-2012 Admissions Vacancy Position in AU region as on 17-12-2012

Left over seat in M.Tech Colleges in  AU region.
Student who are not qualified in PGECET or who are not allotted in PGECET Counselling can get seat in left over seats in spot admission.

PGECET-2012 Admissions Vacancy Position in OU region as on 17-12-2012

Left over seat in M.Tech Colleges in  OU region.
Student who are not qualified in PGECET or who are not allotted in PGECET Counselling can get seat in left over seats in spot admission.

To know the left over seat in the respective colleges Click here

List of Not reported for PHASE-2 as on 17-12-2012 2:30 PM

Many Students who are allotted in M.Tech College did not reported the respective colleges.

BFS implementation using Java

import java.io.*;
class quelist
{
  public int front;
  public int rear;
  public int maxsize;
  public int que[];
  public quelist(int size)
  {
    maxsize = size;
    que = new int[size];
    front = rear = -1;
  }
  public void enque(int x)
  {
     if(front==-1)
     front = 0;
     que[(++rear)%maxsize]=x;
  }
  public int deque()
  {
    int temp = que[front];
    front = (front +1)%maxsize;
    return temp;
  }
   public boolean isempty()
  {
    return((front>rear)||(front==-1));
  }
}  
class vertex
{
 public char label;
 public boolean wasvisited;
 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  quelist qu;
  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   qu = new quelist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }
  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    qu.enque(0);
    int v2;
    while(!(qu.isempty()))
    {
     int v1 = qu.deque();
     while((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        qu.enque(v2);
      }  
    }
    System.out.print("\n");
  }
}

DFS implementation using Java

import java.io.*;
class stcklist
{
  public int top;
  public int maxsize;
  public int[] stck;

  public stcklist(int size)
  {
    maxsize = size;
    stck = new int[size];
    top= -1;
  }

  public void push(int x)
  {
     stck[++top]=x;
  }

  public int pop()
  {
    int temp = stck[top];
    top--;
    return temp;
  }
  public int top()
  {
    int temp = stck[top];
    return temp;
  }
  public boolean isempty()
  {
    return(top==-1);
  }
}  

class vertex
{
 public char label;
 public boolean wasvisited;

 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}

class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  stcklist st;

  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   st = new stcklist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }

  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }

  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
 
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }

  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }

  public void drfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    st.push(0);
    int v2;
    while(!(st.isempty()))
    {
     int v1 = st.top();
// v2=getadjunvis(v1));
     if((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        st.push(v2);
      }
 else
 st.pop();
    }
  }
}

Queue implementation using Linked List in Java

import java.io.*;
class Node
{
public int item;
public Node next;
public Node(int val)
{
item = val;
}
}
class LinkedList
{
private Node front,rear;
public LinkedList()
{
front = null;
rear = null;
}
public void insert(int val)
{
Node newNode = new Node(val);
if (front == null) {
            front = rear = newNode;
        }
else {
            rear.next = newNode;
rear = newNode;
}
}
public int delete()
{
if(front==null)
{
System.out.println("Queue is Empty");
return 0;
}
else
{
int temp = front.item;
            front = front.next;
            return temp;
}
}
public void display()
{
if(front==null)
{
System.out.println("Queue is Empty");
}
else
{
System.out.println("Elements in the Queue");
Node current = front;
while(current != null)
{
System.out.println("[" + current.item + "] ");
current = current.next;
}
System.out.println("");
}
}

}

Stack implementation using Linked List in Java

import java.io.*;
class Node
{
public int item;
public Node next;
public Node(int val)
{
item = val;
}
}
class LinkedList
{
private Node first;
public LinkedList()
{
first = null;
}
public void push(int val)
{
Node newNode = new Node(val);
newNode.next = first;
first = newNode;
}
public int pop()
{
if(first==null)
{
System.out.println("Stack is Empty");
return 0;
}
else
{
int temp = first.item;
first = first.next;
return temp;
}
}
public void display()
{
if(first==null)
{
System.out.println("Stack is Empty");
}
else
{
System.out.println("Elements from top to bottom");
Node current = first;
while(current != null)
{
System.out.println("[" + current.item + "] ");
current = current.next;
}
System.out.println("");
}
}

}

Queue implementation using Array in Java

import java.io.*;
class Aray
{
private int a[];
public int c=0,i,front,rear;
public Aray()
{
a=new int[5];
front=0;
rear=-1;
}
public void insert(int val)
{
if(c<=4)
{
rear=(rear+1)%5;
a[rear]=val;
c++;
}
else
System.out.println("Queue is full");
}
public int delete()
{
if(c==0)
{
System.out.println("Queue is Empty");
return 0;
}
else
{
int temp = a[front];
front=(front+1)%5;
c--;
return temp;
}
}
public void display()
{
if(c==0)
{
System.out.println("Queue is Empty");
}
else
{
System.out.println("Elements from front to rear");
int m=0;
for(i=front;m<c;i++,m++)
{
if(i>4)
i=i%5;
System.out.println(a[i]);
}
}
}

}

Stack implementation using Array in Java

import java.io.*;
class Aray
{
private int a[];
public int t=-1,i;
public Aray()
{
a=new int[5];
}
public void push(int val)
{
if(t<4)
{
t++;
a[t]=val;
}
else
System.out.println("Stack is full");
}
public int pop()
{
if(t==-1)
{
System.out.println("Stack is Empty");
return 0;
}
else
{
int temp = a[t];
t--;
return temp;
}
}
public void display()
{
if(t==-1)
{
System.out.println("Stack is Empty");
}
else
{
System.out.println("Elements from top to bottom");
for(i=t;i>-1;i--)
System.out.println(a[i]);
}
}

}

Download GATE 2013 Admit Card now

Eligible candidates can now download admit cards by signing into their account here.

Click here to download your Admit Card

Download Admit Card for GATE 2013 Exam

Admit cards can be downloaded 5:00 p.m. onwards from 10th December 2012 instead of the advertised date of 5th December 2012.

Check your application status.

Mathematical functions in C language

Q) Which statement will you add in the following program to work it correctly?

#include<stdio.h>
int main()
{
    printf("%f\n", log(36.0));
    return 0;
}

A. #include<conio.h> B. #include<math.h>
C. #include<stdlib.h> D. #include<dos.h>

Explanation:

Attention Not allotted / Not reported PGECET Candidates

Not allotted / Not reported and candidates who have cancelled their admission  are advised to collect their Original Certificates from the  concerned helpline centers where the certificates were deposited from  7-12-2012  to  24-12-2012.

PGEC/PGECET 2012 Final Phase Allotments released

PGEC/PGECET 2012 Final Phase Allotments released.

Variables name in C

Variable is the name given to the memory location, it is not the actual memory, it is just the name to the memory location.

Variable name can be in UPPER CASE or it can be also in lower case.

Variable can also have underscore( _ ) and numbers. Apart from this variable can't have anything else.

Variable can be started with only alphabets ( UPPER and lower case) and underscore but not with numbers , numbers and underscore can be used in the middle of the variables.

fmod(x,y) function in C

fmod(x,y) function in C, what is do?

It calculates x modulo y i.e., the remainder of x/y.
This function is the same as the modulus operator, but fmod() performs floating point divisions.

Example:

C programming for GATE 2013

Hi friends, this post is for those candidates who are going to appear GATE 2013 exam and those who want to learn C programming. In this month we will learn complete C programming.So check regularly this blog for the posts. Daily one topic will be discussed, if you have any query you can also comment, your queries will be resolved spontaneously.

Refer you friends also.

Join us on Facebook

Career Laucher

You can also add us in your Google circle, just click on the slider menu on the right hand side and click on the G+ icon and then click on add to circle.