the algolabphobia…

What is computer science…..???

comp sc is the design and analysis of algorithms.

and with this course comes the algolab.I don’t no about other colleges, but in IIT kgp, this is the most annoying lab.(at least for me).It weighs little in terms of grades coz it has only 2 credits, bt then, it is our bread and butter, so we can’t leave iot unattended.

I’ve learned quiet a lot from this algolab…no I’m not talking about coding experience…Its about something more important…i.e. your attitude towards life…Now one might wonder what is the connection between algolab and attitude…But then to really understand this you’ll have to come to kgp and experience it yourself.

this algolab is in our curricullum in the 2nd year(3rd sem).And the raggigng ( better call it Orientation Programme or the more popular “OP”) period comes in 2nd year…ya ya i know its strange…coz all other colgs hv it in 1st year…its so here because we shift to senior halls in 2nd year…so we have to face the combination of ragging + algolab.and both demand time. The sole purpose of ragging is to ensure that you know all your battchmates and seniors well.and obviously for that you need to spend quiet a lot of time meeting all your batchmates…and seniors …knowing all your “hall fundas”…all this takes a lot of time…so at the end of the day we’re left with little or no time…

In the algolab, we’re given an assignment, we’re supposed to submit the assignment brfore next lab i.e. within a period of one week. So it becomes really very difficult to manage both of them at the same time. In the 1st few weeks you just won’t understand what’s happening. And by the time you realise everything …its too late. The assignments carry marks nd hence reflect in your grade sheet. so you xcan’t just drop it. It demands attention.

i used to spend 90% of my time on monday trying to code the assignment. I knew that internet is an excellent resource. But it dissapointed me. I’ll get the algo everywhere, but no one will give you the code.and even if you get one…it’ll be in java. Our submissions are in C only. So even internet proved to be of no use. So i decided that i’ll put up all my algolab assignments on the net so that if anyone needs the codes in C language he can use it.

BUT THERE’S ONE THING THAT I WOULD LIKE TO SAY.PLEASE DON’T JUST COPY AND PASTE THIS STUFF.BECAUSE THAT WOULD DEFEAT THE SOLE PURPOSE OF HAVING THIS LAB IN THE CURRICULLUM.

You can take ideas from here but do not just copy paste this stuff!!!

I had planned to put this up on net since long but couldn’t do so due to lack of time.So i decided today to atleast write something about it so that i get committed to it.Otherwise like all good ides even this one wud get lost.

ppc

well well before i put up any codes i’d like to talk about Prof. Parth Pratim Chakraborti ( or PPC as he is better known). He;s the busiest person in the institute. He’s also the Dean of SRIC, Sponsored Research and Industrial Consultancy. He’s also our allumni. Its coz of him that i developed such an interest in algorithms. He’s got a unique style of teaching. I’ll talk more about him in the days to come.

But for now i’ll put up one of my favouraite code. The mst.c

Problem :

  1. Write a C Program to implement Prim’s Algorithm for finding the minimum cost spanning tree of a weighted graph. You need to print the cost of the tree and the set of edges of the original graph present in the tree.

The datastrucure used is Heap, because it helps reduce the complexity. The min-priority queue and decrease functions are pretty useful in this context. 

 

Code :

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define infy 9999

struct str1{      // datastructure for min-priority queue.
  int key;
  int node;
};

typedef struct str1 str;

int **adj;        // adjacency matrix.
int *visited;
str *Q;           // min-priority key.
int *key;         // key[v] = min wt. of any
                  // edge joining v to tree.
int *parent;      // stores the parent node.

int heap_size;

//…………..  SWAP  ……………..

void swap(str *array,int p,int q)
{
  str temp;
 
  temp.key        = (array[p]).key;
  temp.node       = (array[p]).node;
 
  (array[p]).key  = (array[q]).key;
  (array[p]).node = (array[q]).node;
 
  (array[q]).key  = temp.key;
  (array[q]).node = temp.node;
}

// ………. MIN HEAPIFY  ……………..

void min_heapify(str *Q,int i)
{
  int left,right,smallest;
 
  left  = 2*i;
  right = 2*i+1;
 
  if(left > heap_size)
    return;
 
  if(left <= heap_size)
    {
      if(Q[left].key < Q[i].key)
 smallest = left;
      else smallest = i;
    }
 
  if(right <= heap_size)
    if(Q[right].key < Q[smallest].key)
      smallest = right;
 
 
  if(smallest != i)
    {
      swap(Q,i,smallest);
     
      min_heapify(Q,smallest);
    }
}

// …………….  BUILD MIN HEAP  ……………..

void build_min_heap(str *Q,int n,int length)
{
  int i;
 
  for(i = length/2;i > 0;i–)
    min_heapify(Q,i);
}

//…………. EXTRACT MIN……………

str extract_min(str *Q,int n)
{
  str min;
  int i;
 
  if (heap_size < 1)
    {
      printf(“HEAP_SIZE < 1\n”);
      return;
    }
 
  min.key  = Q[1].key;
  min.node = Q[1].node;
 
  swap(Q,1,heap_size);
 
  heap_size = heap_size – 1;
 
  min_heapify(Q,1);
 
  return min;
}

//  ………….  DECREASE KEY ………………….

void decrease_key(str *Q,int i,int key)  //decrease the key of elt. i
{
 
  if(key > Q[i].key)
    return;
 
  Q[i].key = key;
 
  while((i > 1) && (Q[i/2].key > Q[i].key))
    {
      swap(Q,i,i/2);
      i = i/2;
    }
}

 

//………………  MAIN  ……………….

 

int main()
{
 
  int n,e,node1,node2,i,j;
  int root,wt,u,v,cost;
  str temp;
  int a,length;
 
 
  printf(“no of nodes :: “);
  scanf(“%d”,&n);
 
  adj = (int **)calloc(n+1,sizeof(int *));
 
  for(i = 1;i <= n;i++)
    adj[i] = (int *)calloc(n+1,sizeof(int));
 
  for(i = 1;i <= n;i++)
    for(j = 1;j <= n;j++)
      adj[i][j] = infy;
 
  a = log(n)/log(2);
  length = pow(2,a+1);
 
  heap_size = n;
 
  Q = (str *)calloc(length + 1,sizeof(str));
 
  printf(“no. of edges :: “);
  scanf(“%d”,&e);
 
  printf(“Enter the edges & weights edge1 edge2 weight.\n”);
 
  for(i = 1;i <= e;i++)
    {
      scanf(“%d%d%d”,&node1,&node2,&wt);
      adj[node1][node2] = wt;
      adj[node2][node1] = wt;
    }
 
  key     = (int *)calloc(n + 1,sizeof(int));
 
  visited = (int *)calloc(n + 1,sizeof(int));
 
   
  // initialize
 
  for(i = 0;i <= n;i++)
    {
      key[i]    = infy;
 
    }
 
  // choosing the root.
 
  root = 1;
 
  key[root] = 0;
 
 
  // min priority queue Q.
 
  for(i = 1;i <= n;i++)
    {
      Q[i].key  = key[i];
      Q[i].node = i;
    }
 
  build_min_heap(Q,n,length);
 
  cost = 0;
 
  while(heap_size != 0)
    {
      temp = extract_min(Q,n);
      u = temp.node;
      cost = cost + temp.key;
      visited[u] = 1;
     
      for(v = 1;v <= n;v++)
 {
   if(adj[u][v] != infy)
     {
       if(visited[v] == 0)
  {
    if(adj[u][v] < key[v])
      {
        key[v] = adj[u][v];
       
        for(i = 1;i <= heap_size;i++)
   {
     if((Q[i]).node == v)
       {
         // decrease the key of node v(contained in
         // elt i of min-priority queue Q) to adj[u][v]
        
         decrease_key(Q,i,adj[u][v]);
         break;
       }
   }
      }
  }
     }
 }
    }
 
 
  printf(“The Cost of shortest spanning tree = %d\n\n”,cost);
 
  printf(“\n\n”);
 
  return 0;
 
}

 

//*************************************

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s