Floyd Warshall

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

There are many notable algorithms to calculate the shortest path between vertices in a graph. Most are based on single source to a set of destination vertices. Examples of such famous algorithms include Dijkstra’s, Bellman-Ford and even Breadth First Search for weightless graphs. However, sometimes we wish to calculate the shortest paths between all pairs of vertices. An easy way to calculate this is to loop through each possible pair of vertices and run a Dijkstra through it. However, there exists a more efficient way to calculate this in n^3 time complexity.

Floyd-Warshall algorithm, a formula consisting of the core is very simple. A, B, C, I suppose we have 3 points. In this case, the shortest distance between A and C (distance (A, C), distance (A, B) + distance (B, C)) is up. Floyd-Warshall’ı need to apply to a table. The size of this table, depending on the number of points to be determined. We got one point, the table size N * N N

int[,] table = new int[5,5];

On the basis of the algorithm used for the function of the input for this table are the values at the maximum. The distance of each point of self-0, the distance to other points, we will begin by accepting the infinite.

int INFINITY = 9999999;
int N = 5;
for (int i = 0; i < N; i++)
  for(int j = 0; j < N; j++)
    table[i,j] = i == j ? 0 : INFINITY;

After this operation, the value of the table will be as follows.

table 1 2 3 4 5
1 0 INF INF INF INF
2 INF 0 INF INF INF
3 INF INF 0 INF INF
4 INF INF INF 0 INF
5 INF INF INF INF 0

Second, to keep the connection between the points and to build the matrix of contiguity for questioning. If you have an edge from one point to another entry in the table that would give a value. For example, point 3 and point 4, one side has 2 points. Therefore, our statements [2,3] = [2.4] = 1 = [3.2] = [4.2]. Grafımız no way we obtain for the diagonal matrix based on contiguity should be symmetrical. 1 to 4, because to have the edge in the 4 to 1, this also means there are also edges. Our example is a way you could tell it had graphs. After this, the final version of the table will be as follows:

table 1 2 3 4 5
1 0 INF INF 1 INF
2 INF 0 1 1 INF
3 INF 1 0 1 INF
4 1 1 1 0 1
5 INF INF INF 1 0

Floyd-Warshall can now apply the formula:

for( int k = 0; k &lt; N; k++)
for( int i = 0; i &lt; N; i++)
for( int j = 0; j &lt; N; j++)
table[i,j] = Math.Min(table[i,j], table[i,k] + table[k,j]);

That’s it. After this, our table will be as final.

table 1 2 3 4 5
1 0 2 2 1 2
2 2 0 1 1 2
3 2 1 0 1 2
4 1 1 1 0 1
5 2 2 2 1 0

Now using the table between the two points (a, b) can query the shortest distance. table [a, b] = table [b, a].

Installing windows softwares on Ubuntu 10.04

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

Linux is the one of the best open source operating system but most of the linux user faces the problem of installing windows exe (executable files) in linux. There is always question in their mind how to install some windows application in linux operating system. Previously user have no alternatives as linux doesn’t support exe files. Therefore user have to find the alternative of the problem that is in linux platform. Now with Ubuntu 10.04 user can run exe files easily with the help of application called wine.
1. Download ubuntu 10.04 and install in your computer if you don’t have it.

2. After installing it go to Application then choose Ubuntu software center from drop down menu.

3. Search wine in Ubuntu support center and click on install.

4. After installing it go to any windows exe file , right click on it and choose Open with wine window program loader. Then the set up fill will execute and you can successfully install windows exe file in ubuntu 10.04

Screenshot of windows exe fileon Linux Ubuntu 10.4

or
Open the terminal, and cd into the directory where the .EXE is located.
Type wine the-name-of-the-application.extension (e.g. wine realplayer.exe).

nVidia Driver installation in Ubuntu 10.04

Standard

Add to DeliciousAdd to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

So I have been playing with 10.04 for last few days on my Intel® Core™ i7 and I must say I am enjoying it very much! One change I made however was changing over to the 64bit version of the Ubuntu and as such I installed the PAE kernel modules so I could use my four full gigs of RAM on the system still. I had everything configured and all was going well until the fateful kernel update…
Upon upgrading to 2.6.32-21 I rebooted to that wonderus “Ubuntu is running in low graphics mode” message I have seen oh so many times before. I load up the system in 800×600 resolution and and try to reinstall the nVidia drivers from the hardware drivers menu – only to see nothing was offered. Not a problem, I download the .run file from nVidia and attempt to install it. Installer fails with a kernel module error. After having a thread go nowhere on the Ubuntu boards for a couple of days I was able to work out the solution on my own. The issue seems to come from a combination of the new open source nVidia driver 10.04 is using by default and the kernel change I recently went through. The following is what worked for me:

First:
Go download the nVidia drivers for your system and install the packages build-essential and linux-headers-`uname -r`

Next:
Drop down to a terminal login and kill your X server

Then:
Install your nVidia driver, but when you run the install add the launch argument –k $(uname -r) Example: sudo sh NVIDIA*.run -k $(uname -r)

Now:
We need to blacklist the FOSS nouveau driver, run sudo nano /etc/modprobe.d/blacklist.conf and add blacklist nouveau to any point in the file.

Finally:
Reboot the system and you should be good to go! Enjoy.

atod function

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter
atod function’s work is identical to atoi‘s. But this one is for doubles

// for texting/ example purposes
#include <iostream> // for cout and endl
#include <cmath> // for pow
using namespace std; // so we don't have to do std::coud or std::endl
//end testing/ example purposes 

char* substr(char* str, int start, int end){
	char* a = new char[1+(end-start)]; // we need a new char array for the return
	for(int i=start; i<end; i++){ // loop through the string
		a[i-start] = str[i]; // set the characters in the new char array to those from the old one compensating for the substring
	}
	a[end-start] = '\0'; // add the null character, so we can output
	return a; // return
}

double atod(char* a){
	double retVal = atoi(a); // start off getting the number, assuming it is a valid string to use atoi on.
	int start = 0;
	int end = 0;
	for(int i=0; a[i] != '\0'; i++){ // loop through the string to find the positions of the decimal portion, if there is one
		if(a[i] == '.' && start == 0){
			start = i+1; // set the start position to 1 more than the current (avoids a char as the first character - we want a digit)
		}
		else if(start != 0 &&  (a[i] < '0' || a[i] > '9')){ // make sure that start is set and that we aren't looking at digits
			end = i; // if so, set the end location for the substring
			break; // we don't need to continue anymore - break out of the loop
		}
	}
	if(end > start){ // avoids substring problems.
		char* decimal = substr(a, start, end); // get the string that is after the decimal point
		int dec = atoi(decimal); // make it an integer
		int power = end-start; // find the power of 10 we need to divide by
		retVal += ((double)dec)/(pow(10.0, (double)power)); // divide and add to the return value (thus making it a true double)
	}
	return retVal; // return - simple enough
}

// for testing/ example purposes
int main(){
	cout << atod("127.02501 test") << endl; // test it out on a valid character stream
	return 0;
}
// end testing/ example purposes

Quick Sort : Sorting array of Strings, Integers and Structs

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter
qsort() takes four arguments:

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
■base — is a pointer to the beginning of data array
■nel — is a number of elements
■width — is a size of each element (in bytes)
■compar — is a callback function (pointer to function), which does comparison and returns positive or negative integer depending on result.

This example contains three separate functions sort_integers_example(), sort_cstrings_example() and sort_structs_example().

■sort_integers_example() uses int_cmp() as compar callback. Additional function print_int_array is used for printing integer array contents.
■sort_cstrings_example() uses cstring_cmp() as compar callback. Additional function print_cstring_array is used for printing string array contents.
■sort_structs_example() uses struct_cmp_by_price() and struct_cmp_by_product() as compar callbacks. Additional function print_struct_array is used for printing array of struct.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* qsort int comparison function */
int int_cmp(const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types
    const int *ib = (const int *)b;
    return *ia  - *ib; 
	/* integer comparison: returns negative if b > a 
	and positive if a > b */
}
 
/* integer array printing function */
void print_int_array(const int *array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("%d | ", array[i]);
 
    putchar('\n');
}
 
/* sorting integers using qsort() example */
void sort_integers_example()
{
    int numbers[] = { 7, 3, 4, 1, -1, 23, 12, 43, 2, -4, 5 }; 
    size_t numbers_len = sizeof(numbers)/sizeof(int);
 
    puts("*** Integer sorting...");
 
    /* print original integer array */
    print_int_array(numbers, numbers_len);
 
    /* sort array using qsort functions */
    qsort(numbers, numbers_len, sizeof(int), int_cmp);
 
    /* print sorted integer array */
    print_int_array(numbers, numbers_len);
}
 
/* qsort C-string comparison function */
int cstring_cmp(const void *a, const void *b)
{
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    return strcmp(*ia, *ib);
	/* strcmp functions works exactly as expected from
	comparison function */
}
 
/* C-string array printing function */
void print_cstring_array(char **array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("%s | ", array[i]);
 
    putchar('\n');
}
 
/* sorting C-strings array using qsort() example */
void sort_cstrings_example()
{
    char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };
    size_t strings_len = sizeof(strings) / sizeof(char *);
 
    /** STRING */
    puts("*** String sorting...");
 
    /* print original string array */
    print_cstring_array(strings, strings_len);
 
    /* sort array using qsort functions */
    qsort(strings, strings_len, sizeof(char *), cstring_cmp);
 
    /* print sorted string array */
    print_cstring_array(strings, strings_len);
}
 
 
 
/* an example of struct */
struct st_ex { 
    char product[16];
    float price;
};
 
/* qsort struct comparision function (price float field) */
int struct_cmp_by_price(const void *a, const void *b)
{
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return (int)(100.f*ia->price - 100.f*ib->price);
	/* float comparison: returns negative if b > a 
	and positive if a > b. We multiplied result by 100.0
	to preserve decimal fraction */
 
} 
 
/* qsort struct comparision function (product C-string field) */
int struct_cmp_by_product(const void *a, const void *b)
{
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return strcmp(ia->product, ib->product);
	/* strcmp functions works exactly as expected from
	comparison function */ 
} 
 
/* Example struct array printing function */
void print_struct_array(struct st_ex *array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("[ product: %s \t price: $%.2f ]\n", array[i].product, array[i].price);
 
    puts("--");
}
 
/* sorting structs using qsort() example */
void sort_structs_example(void)
{
    struct st_ex structs[] = {{"mp3 player", 299.0f}, {"plasma tv", 2200.0f}, 
                              {"notebook", 1300.0f}, {"smartphone", 499.99f}, 
                              {"dvd player", 150.0f}, {"matches", 0.2f }};
 
    size_t structs_len = sizeof(structs) / sizeof(struct st_ex);
 
    puts("*** Struct sorting (price)...");
 
    /* print original struct array */
    print_struct_array(structs, structs_len);
 
    /* sort array using qsort functions */
    qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_price);
 
    /* print sorted struct array */
    print_struct_array(structs, structs_len);
 
    puts("*** Struct sorting (product)...");
 
    /* resort using other comparision function */ 
    qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_product);    
 
    /* print sorted struct array */
    print_struct_array(structs, structs_len);
}
 
 
/* MAIN program (calls all other examples) */
int main()
{
    /* run all example functions */
    sort_integers_example();
    sort_cstrings_example();
    sort_structs_example();
    return 0;
}

Execution result:

*** Integer sorting…
7 | 3 | 4 | 1 | -1 | 23 | 12 | 43 | 2 | -4 | 5 |
-4 | -1 | 1 | 2 | 3 | 4 | 5 | 7 | 12 | 23 | 43 |
*** String sorting…
Zorro | Alex | Celine | Bill | Forest | Dexter |
Alex | Bill | Celine | Dexter | Forest | Zorro |
*** Struct sorting (price)…
[ product: mp3 player price: $299.00 ]
[ product: plasma tv price: $2200.00 ]
[ product: notebook price: $1300.00 ]
[ product: smartphone price: $499.99 ]
[ product: dvd player price: $150.00 ]
[ product: matches price: $0.20 ]

[ product: matches price: $0.20 ]
[ product: dvd player price: $150.00 ]
[ product: mp3 player price: $299.00 ]
[ product: smartphone price: $499.99 ]
[ product: notebook price: $1300.00 ]
[ product: plasma tv price: $2200.00 ]

*** Struct sorting (product)…
[ product: dvd player price: $150.00 ]
[ product: matches price: $0.20 ]
[ product: mp3 player price: $299.00 ]
[ product: notebook price: $1300.00 ]
[ product: plasma tv price: $2200.00 ]
[ product: smartphone price: $499.99 ]

Euler’s Totient Theorem

Standard

Now I will present a wonderful fact about the coprimes to n — they form a group under multiplication mod n, which leads to:

If GCD(a,n) = 1 then aφ(n) = 1 (mod n).

Proof: take a to be any positive integer coprime to n.
Let A be the set of numbers coprime to n: A = {a1, a2, a3, …, aφ(n)}
Let aA be the product of the number, a, with each of the elements of A: aA = {aa1, aa2, aa3, …, aaφ(n)}
No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod n must be {a1, a2, a3, …, aφ(n)} in some order.
By equating the product of the numbers in set aA with the product of those in set A, mod n,
aφ(n)a1a2a3…aφ(n) = a1a2a3…aφ(n) (mod n)
Since a1a2a3…aφ(n) is coprime to n, we can divide both sides by a1a2a3…aφ(n), mod n, proving Euler’s Totient Theorem.

* Lemma 1: Why are no two elements of aA = {aa1, aa2, aa3, …, aaφ(n)} congruent, mod n?
Suppose a is a number coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n-1] and ab=ac, mod n.
Then ab-ac=nk, where k is an integer.
a(b-c)=nk, and since b-c is smaller than n in absolute value, a must be larger than k in absolute value.
a and n have no factors in common, so a|k, but a can’t divide k, since a is larger than k, a contradiction.


Other Totient Theorems

Let’s write m = 2n-1 for convenience.
Now 2n = m+1, so 2n = 1 (mod m), but no smaller (but still positive) power of 2 is equivalent to 1 (mod m).
So (2n)k = 1 (mod m), which means 2kn = 1 (mod m) for any integer, k.
2φ(m) = 1 (mod m), by Euler’s Totient Theorem.
We can divide φ(m) by n giving quotient q and remainder r such that φ(m) = qn+r, and so
2φ(m) = 2qn+r = 2qn 2r = 1 (mod m), and we know 2qn = 1 (mod m), so 2r = 1 (mod m), and 0 ≤ r < n, so r=0