July 28, 2012

Minimum vertex cover of tree

An unweighted, undirected tree is given. We have to find a vertex set of minimum size in this tree such that each edge has as least one of its end-points in that set, i.e. minimum vertex cover of tree.
      The problem of finding a minimum vertex cover of a graph is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem. Taken as decision problem, it is NP complete. Tree is a special type of graph which has no cycles and so it's possible to find out the minimum vertex cover by using Dynamic Programming.
  Basic idea is if any vertex is included in the set, we are free to choose or not choose it's children but if any vertex isn't included in set then we have to choose all the children of it.
  In notation:
  S+(u) = 1 + sum(min{S-(v), S+(v)})
  S-(u) = sum(S+(v))

 
  'u' is any node and 'v' refers to it's child[ren]
  S is set which stores the vertexes of minimum cover. S+(u) means 'u' is present in set, S-(u) means 'u' is not present.
  sum(X) means sum of all children

  In my code I've taken root that vertex which is of highest degree. 'root' is the vertex from which query is started. After the whole tree is covered we take min{S+(root),S-(root)} as our answer. For pedant vertexes, S+(u)=1 and S-(u)=0 as it's trivial. 


Original problem :
http://www.spoj.pl/problems/PT07X/

This is my solution

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

typedef struct node
{
    // included, not included, neighbor
    int inc, notinc;
    int neigh;
}Node;

typedef struct vertex
{
    int vertex_id;
    struct vertex *next;
}Vertex;

#define MAX 100007

int n;
Node array[MAX];
Vertex *G[MAX]; // adjacency list representation of graph
short color[MAX]; // for visiting vetexes

inline int min (int P, int Q)
{
    return (P<Q) ? P : Q;
}

void addNode (int u, int v)
{
    Vertex *newvertex = (Vertex*)malloc(sizeof (Vertex));
    newvertex->vertex_id = v;
    newvertex->next = G[u];
    array[u].neigh++;
    G[u]=newvertex;
}
void dfs (int index)
{
    if (array[index].neigh==1){
        array[index].inc=1;
        array[index].notinc=0;
        color[index]=2; // visiting done
        return;
    }

    int pos=0, neg=0;
    color[index]=1;  // visiting in progress
    Vertex *itr = G[index];
    while (itr != NULL){
        int curr = itr->vertex_id;
        if (color[curr]==0){  // not visited yet
            dfs(curr);
        }
        itr = itr->next;
    }

    itr = G[index];
    while (itr != NULL){
        int curr = itr->vertex_id;
        if (color[curr] == 2){
            pos += (min(array[curr].inc,array[curr].notinc));
            neg += array[curr].inc;
        }
        itr = itr->next;
    }
    array[index].inc = pos+1;
    array[index].notinc = neg;
    color[index] = 2;
}

int main()
{
    int I, a, b;
    scanf("%d",&n);
    memset (color, 0, sizeof color);

    for(I=0;I<n+1;I++){
        G[I]=NULL;
        array[I].neigh=0;
    }

    for(I=1;I<=n-1;I++){
        scanf("%d %d",&a, &b);
        addNode(a, b);
        addNode(b, a);
    }
    int root=1;
    for (I=1;I<=n;I++){
        if (array[I].neigh>array[root].neigh)
            root = I;
    }
    if (n== 1 || n==2 || n==3)  //trivial cases. Handle on your own.
        printf("%d",1);
    else{
        dfs (root);
        printf("%d",min(array[root].inc, array[root].notinc));
    }
    return 0;
}

July 22, 2012

2's complement - The way computer counts.

Let's start first post with counting. Computers understand binary language which consists of only two symbols, basically represented as '0' and '1'. I assume you know how to represent decimal numbers into binary domain. I'm giving here a fictional story to make you understand how computer counts.
In binary world there are two persons, Jedi and Vader. Jedi stands for good and Vader is of evil. Jedi rules over '+'(positive) domain and Vader rules over '-'(negative) domain. Now both have to count but they are opposite to each other so they start with exact opposite ends(as they don't like each other). Jedi start with all 'zero' bits while counting in his positive domain and Vader start with all 'one' bits his domain. They have something in common(both are powerful) and that's why the pattern in which they counts is same but they use just opposite symbols. What is '0' to Jedi is '1' to Vader and vice versa. Below two lists are given. The numbers in list are of 4-bits(1 bit for sign, 3 bits for value) for demo. Entries in list are written as "s vvv". Here 's' is sign bit and 'v' is the data bit. Space between sign bit and data bits is just for sake of clarity. It has no other meaning. Left list is for Jedi and right list is for Vader. While counting, sign bit is always '0' for Jedi and '1' for Vader. As you can see the bit pattern is exactly same for these lists, except that they are opposite to each other in bit.  Number in parentheses is the corresponding value of that bit pattern. 


Suppose we've to find out how '5' is stored in computer. From Jedi list you'll find that it is "0101" but what about negative integers, say -4? Advantage of using 2's complement is we don't have to consider the Vader list. For -4 we'll look up the Jedi list which says "0100". As -4 in negative domain, so we've to flip all the bits which makes it "1011". Flipping the bits gives the corresponding number in negative(vader) domain but values in Vader list are alway '1' less than the Jedi list values. To compensate, we'll add '1' to the obtained bit pattern which is "1011" in this case. After adding it will become "1100". This is the 2's complement representation of -4.

This is fiction story but the computer uses the similar patterns as for values as given in list. Computer uses 'byte' which consists of 8 bits. With a byte(8-bit) you can count from 0 to +127 and -1 to -128 in the same pattern as of the above lists, total 256(1+127+128) different values. This whole setup is called 2's complement method which makes computer enable to store negative integers as well as positive integers.

Advantage of this notation is that computer don't have to use subtraction. Subtraction could be done using addition only. e.g. 3 - 7 = 3 + (-7) = -4. In binary (from the above lists), it would be 0011(3) + 1001(-7) = 1100(-4)

Happy learning :)