FIFA World Cup 2010

FIFA World Cup South Africa 2010 Official Theme Song

Lyrics

ooooooh wooooooh

give me freedom, give me fire,
give me reason, take me higher
see the champions, take the field now,
you define us, make us feel proud...
in the streets are, exaliftin',
as we lose our inhabition,
celebration its around us,
every nation, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game
and together at the end of the day.

[chorus]:
we all say...

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

Oooooooooooooh woooooooooohh hohoho

give you freedom, give you fire,
give you reason, take you higher
see the champions, take the field now,
you define us, make us feel proud
in the streets are, exaliftin,
every loser in ambition,
celebration, its around us,
every nations, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game.
and together at the end of the day.

[chorus]

Oooooooooooooh woooooooooohh hohoho

[chorus]
___________________________________

Song: Wavin' Flag
Artist: K'naan

Blogger Code Formatter

Blogger is a wonderful place to write blogs and there are many code bloggers out there, who want to share their coding skills with the world! But, certainly there are some problems with blogger posting methods, for example, in a <pre> tag, it will ignore tabs, and it causes great problems with some operators like '<', '>' etcetera... So, we can easily write a simple program and use it easily as a code formatter for blogger. Here's an example:

#include <cstdio>

int main(int argc, char **argv) {
    FILE *in = fopen(argv[1], "r");
    FILE *out = fopen(argv[2], "w");
    char ch;
    if(argc < 3) {
        printf("Usage: $ %s <infile> <outfile>\n", argv[0]);
        return 1;
    }
    if(in==NULL) {
        printf("file %s can't be opened.\n", argv[1]);
        return 2;
    }
    if(out==NULL) {
        printf("file %s can't be opened.\n", argv[2]);
        return 3;
    }
    while(fscanf(in, "%c", &ch)==1) {
        if(ch=='>') fprintf(out, "&gt;");
        else if(ch=='<') fprintf(out, "&lt;");
        else if(ch=='&') fprintf(out, "&amp;");
        else if(ch=='\t') fprintf(out, "    ");
        else fprintf(out, "%c", ch);
    }
    fclose(in);
    fclose(out);
    printf("file %s was written succesfully.\n", argv[2]);
    return 0;
}

Windows:

In windows, execute this with any compiler and grab the .exe file, paste it in your C:\WINDOWS\system32 folder. So, for example, if the file name is "blog.cpp", you will get "blog.exe", just paste it to your system32 folder. So now you can use it as a command in command prompt. If you like to format a file, say, "test.cpp", cd to the directory where "test.cpp" is, and to transform, the command is "blog test.cpp blog_test.cpp". Now just open the "blog_test.cpp" file and paste it in the <pre> tags.

Linux

Run it with g++, command: "g++ -o blog blog.cpp", and give enough permissions to the executable "blog", command: "chmod 777 blog". Now, we need to paste it in the "/bin" directory, but as it is write protected, we'll need to log in as root. To do this, write on prompt: "sudo nautilus", it will ask your password, and then an explorer will be opened, and now, just go to the "/bin" directory using it and paste the file. The usage is similar as stated in the Windows part.

Makes life a bit easier...

Testing Bipartite Graph

We can use BFS to check whether an undirected graph is bipartite or not, with only a little modification...

We define bipartite graph as follows: A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) ∈ E implies either u ∈ V1 and v ∈ V2 or u ∈ V2 and v ∈ V1. That is, all edges go between the two sets V1 and V2.

In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray', i.e. visited, our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite. Note that this modification does not change the running time of BFS and remains Θ(V + E).

Here goes a simple implementation of the above idea. We'll just run a BFS, while tracking the partition in which every node falls. If, when visiting node v from node u, and they are members of same partition, then this graph is not bipartite. Well, this time, I think, we have nothing to do with the edge weights or costs, so it will also work on a weighted graph.

Formally, to check if the given graph is bipartite, the algorithm traverse the graph labelling the vertices 0 or 1 / 2 , corresponding to unvisited or visited, and partition 1 or partition 2 depending on which set the nodes are in. If an edge is detected between two vertices in the same partition, the algorithm returns false immediately.

Note: In this implementation, only one test at a time is possible, to run it for multiple cases, definitely cares must be taken about resetting the arrays and other values as necessary.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define MAX 1001

int n, e;
int partition[MAX], visited[MAX];
vector< int > G[MAX];

bool is_bipartite() {
    int i, u, v, start;
    queue< int > Q;
    start = 1; // nodes labeled from 1
    Q.push(start);
    partition[start] = 1; // 1 left, 2 right
    visited[start] = 1; // set gray
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        for(i=0; i < G[u].size(); i++) {
            v = G[u][i];
            if(partition[u] == partition[v]) return false;
            if(visited[v] == 0) {
                visited[v] = 1;
                partition[v] = 3 - partition[u]; // alter 1 and 2
                Q.push(v);
            }
        }
    }
    return true;
}

int main() {
    int i, u, v;
    scanf("%d %d", &n, &e);
    for(i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(is_bipartite()) printf("Yes\n");
    else printf("No\n");
    return 0;
}

As this algorithm traverses the graph it labels the vertices with a partition number consisted with the graph being bipartite. If at any vertex, algorithm detects an inconsistency, it shows with an invalid return value. Partition value of u will always be a valid number as it was en-queued at some point and its partition was assigned at that point. Partition of v will be unchanged if it is already set, otherwise it will be set to a value opposite to that of vertex u. So, if the algorithm returns true, it means, the graph is bipartite, i.e. bi-color-able, and partition[] holds the colors for each vertex.

Have fun, and let me know about errors, if any. [Note: The definition of bipartite graph is taken from this wonderful site]