Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

"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)." - Wikipedia

1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say Sx & Sy into a new set that is the union of these two sets 
Sx & Sy are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Birthday Paradox Simulation in C

/* Given a group of n people how to calculate the probability that m people among them have the same birthday without using a formula*/

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

int main()
{
  int i, n, m, rand_birthday, j, a;
  int *array = NULL, c, k, t;
  float count = 0.0, trial = 1.0, prob, percent;
  
  printf("\nEnter the number of people in a room:");
  scanf("%d", &n);
  printf("\nEnter the number of people whose birthday ");
  printf("needs to be on the same day:");
  scanf("%d", &m);
  printf("\nEnter the no. of trials:");
  scanf("%d", &t);

  // Dynamically allocate memory for n elements
  array = (int *)calloc(n, sizeof(int));

  while(trial <= t)
  {
    for(i = 0; i < n; i++)
    {
      rand_birthday = gen_rand();
      array[i] = rand_birthday;
    }
    printf("\nRandom birthdays are : \n");
    for(i = 0; i < n; i++)
      printf(" %d ", array[i]);
    printf("\n");
  
    // Sorting the birthdays
    for(i = 0; i < n; i++)
    {
      for(j= i + 1; j < n; j++)
      {
        if(array[i] > array[j])
        {
          a = array[i];
          array[i] = array[j];
          array[j] = a;
        }
      }
    }

    printf("\nRandom birthdays(sorted) are : \n");
    for(i = 0; i < n; i++) 
      printf(" %d ", array[i]);
    printf("\n");

    // Check for the same birthdays
    i = 0; j = 1; 
    while(j < n)
    {
      c = 1;
      if(array[i] != array[j])
      {
        i++;
        j++;
      }
      else
      {
        for(k = j; ((k < n) && (array[i] == array[k])); k++)
          c++;
        i = k;
        j = k + 1;
        if(c >= m)
        {
          count++;
          break;
        }
      }
    }
    trial++;
  }

  // Calculate the probability
  printf("\ncount = %f, \ntrials = %f\n", count, trial);
  prob = (count/trial);
  printf("Probability of getting %d same birthdays", m);
  printf(" among %d people is %f", n, prob);
  percent = prob * 100;
  printf(" = %f percentage\n", percent);

  return 0;
}

int gen_rand(void)
/* returns random number in range of 0 to 364 */
{
   int n;
   n=rand() % 365;
   return(n);
}

Written by Munia Balayil