Sunday 30 December 2012

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

ImageDescription
Kruskal Algorithm 1.svgAD and CE are the shortest edges, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
Kruskal Algorithm 2.svgCE is now the shortest edge that does not form a cycle, with length 5, so it is highlighted as the second edge.
Kruskal Algorithm 3.svgThe next edge, DF with length 6, is highlighted using much the same method.
Kruskal Algorithm 4.svgThe 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.
Kruskal Algorithm 5.svgThe 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 BCEDE because it would form the loop DEBA, and FE because it would form FEBAD.
Kruskal Algorithm 6.svgFinally, 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

ImageUpossible edgesV \ UDescription
Prim Algorithm 0.svg{}{A,B,C,D,E,F,G}This is our original weighted graph. The numbers near the edges indicate their weight.
Prim Algorithm 1.svg{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 ABE 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.
Prim Algorithm 2.svg{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 AB is 9 away from D and 7 away from AE is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
Prim Algorithm 3.svg{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.
Prim Algorithm 4.svg{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 CE, and GC is 8 away from BE is 7 away fromB, and G is 11 away from FE is nearest, so we highlight the vertex E and the edge BE.
Prim Algorithm 5.svg{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.
Prim Algorithm 6.svg{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 EE is nearer, so we highlight G and the edge EG.
Prim Algorithm 7.svg{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;
 }
}

Thursday 27 December 2012

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.


Friday 21 December 2012

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);
}
}

Thursday 20 December 2012

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.

Monday 17 December 2012

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.

Sunday 16 December 2012

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]);
}
}

}

Friday 7 December 2012

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.

Monday 3 December 2012

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.

Sunday 2 December 2012

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.

Friday 30 November 2012

GATE 2013 Application Status


After an applicant submits an online application the application goes through the following states

1. Online Application Submitted:
The application was received.  A copy of the application form (in PDF) must be downloaded.

2. Application Received and Under Scrutiny:
The Zonal GATE office has received the posted hard copy.  In case an application has been sent but not received for more than 10 days, please check the Speed Post website for the tracking the consignment.

3. Application Accepted:
The application has been scrutinized and found to be eligible to take the GATE 2013 examination.  The candidate has to wait till 5 Dec 2012 when the Admit Card will be available for download.

4. Rectification Required:
The application is incomplete or defective. Read the instructions given and take actions accordingly. The response must reach the Zonal office within 10 days of receipt of the mail from GATE office or November 5 which ever is earlier.

5. Provisionally Accepted:
The application has been provisionally accepted, subject to additional documents to be submitted.  Admit card for GATE 2013 will be issued, but the candidate must bring a copy of the document mentioned or a Demand Draft for Rs.600, in favour of “Chairman GATE 2013″ to the examination center; otherwise the Score Card will not be issued.

GATE 2013 Admit Card



When I will receive admit card?

Admit card can only be downloaded from the GATE Online Applicant Interface from 5th December 2012. Sending Admit cards by post has been discontinued.

Note:  For Examination bring downloaded admit card along with at least one original (not photocopied / scanned copy) and valid (not expired) photo identification.

One of the following photo identifications is permitted:

PGEC/PGECET Final Phase of Web counselling



Final Phase Web counselling from 30-11-2012 to 02-12-12

Best geography books for UPSC prelims, mains

This post is intended to clear the confusion that prevails among the aspirants over how to prepare for UPSC geography and the best books f...