Write a program that takes strings as inputs and stores them in a hash table.
Then it should then ask the user for strings to be searched in the hash table.
Then it should then ask the user for strings to be searched in the hash table.
Saturday, 31 March 2012
Answer to nth fibonacci number
We have the recursion formula for fibonacci series as
f(n)=f(n-1)+f(n-2)
We can derive a formula for the function as
f(n) - f(n-1) - f(n-2) = 0
which is transformed into a recurrence relation problem as..
x^2 - x - 1=0
The solution is x= (1 +
5)/2 and x=(1- 5)/2.
therefore the homogenius solution is
.
Since the initial condition is
f(0)=0
f(1)=1
Therefore A1 + A2 =0
A1*((1 +5)/2) + A2*((1 - 5)/2) = 1
solving the above two equations ,
A1=(1/5) and A2=(-1/5).
ie. the formula for f(n)=
This formula is called
I present a simple python program to implement this..
import math
a=math.sqrt(5)
p=(1+a)/2
q=(1-a)/2
n=raw_input("enter the number n : ")
n=int(n)
print int((p**n-q**n)/a)
f(n)=f(n-1)+f(n-2)
We can derive a formula for the function as
f(n) - f(n-1) - f(n-2) = 0
which is transformed into a recurrence relation problem as..
x^2 - x - 1=0
The solution is x= (1 +
5)/2 and x=(1- 5)/2.therefore the homogenius solution is
.
 | 1 + √5 |  | n | +A2 | | 1 – √5 | | n | |||||||
| f(n) = |  | A1 | | | |||||||||||
| 2 | 2 |
Since the initial condition is
f(0)=0
f(1)=1
Therefore A1 + A2 =0
A1*((1 +
5)/2) + A2*((1 - 5)/2) = 1A1=(1/
5) and A2=(-1/5).ie. the formula for f(n)=
| 1 | | 1 + √5 | | n | – | | 1 – √5 | | n | | |||||
| | | |||||||||||||
| √5 | 2 | 2 |
This formula is called
I present a simple python program to implement this..
import math
a=math.sqrt(5)
p=(1+a)/2
q=(1-a)/2
n=raw_input("enter the number n : ")
n=int(n)
print int((p**n-q**n)/a)
Wednesday, 21 March 2012
Find nth fibonacci number without traversing from the start
Write a program to find the nth fibonacci number without traversing from the start index.
ie.. the program should have a time complexity of the order of 1 [O(1)].
ie.. the program should have a time complexity of the order of 1 [O(1)].
Tuesday, 6 March 2012
Answer to "Find the determinant"
Program :
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
#define EPSILON 1e-10
typedef enum {FALSE, TRUE} bool;
int N;
void print( double **a) {
/*
* print the matrix.
*/
int i, j;
for( i=0; i<N; ++i ) {
for( j=0; j<N; ++j )
printf( "%8.4g ", a[i][j] );
printf( "\n" );
}
printf( "\n" );
}
void divRow( double **a, int row, double divisor ) {
/*
* divides row of a by divisor.
*/
int j;
for( j=0; j<N; ++j )
a[row][j] /= divisor;
}
void subRow( double **a, int row1, int row2 ) {
/*
* row1 -= row2.
*/
int j;
for( j=0; j<N; ++j )
a[row1][j] -= a[row2][j];
}
bool anyZero( double **a ) {
/*
* returns TRUE if any diagonal entry of a is zero (less than EPSILON).
*/
int i;
for( i=0; i<N; ++i )
if( fabs(a[i][i]) <= EPSILON )
return TRUE;
return FALSE;
}
double makeUpper( double **a ) {
/*
* makes a an upper-triangular matrix.
* returns 0 if any of the diagonal entries are 0; 1 otherwise.
*/
int i, j;
double factor = 1.0;
double temp;
for( i=1; i<N; ++i ) // dont worry about row 0.
for( j=0; j<i; ++j ) {
temp = a[i][j];
if( fabs(temp) > EPSILON ) {
printf( "factor=%g dividing row %d by %g...\n", factor, i+1, temp );
divRow( a, i, temp );
print(a);
factor *= temp;
}
temp = a[j][j];
if( fabs(temp) > EPSILON && fabs(temp-1.0) > EPSILON ) {
printf( "factor=%g dividing row %d by %g...\n", factor, j+1, temp );
divRow( a, j, temp );
print(a);
factor *= temp;
}
if( fabs(a[i][j]) > EPSILON ) {
printf( "factor=%g row[%d] -= row[%d]...\n", factor, i+1, j+1 );
subRow( a, i, j );
print(a);
}
if( anyZero(a) == TRUE )
return 0;
}
a[N-1][N-1] *= factor; // all but(?) last element of row N-1 are zero.
return 1;
}
double multDia( double **a ) {
/*
* returns multiplication of diagonal elements.
*/
int i;
double factor = 1;
for( i=0; i<N; ++i )
factor *= a[i][i];
return factor;
}
int main() {
int i,j;
double **a;
double factor;
printf("\n enter the dimension of the matrix : ");
scanf(" %d",&N);
a=(double **)malloc (N*sizeof (double *));
for (i=0;i<N;i++)
a[i]=(double *)malloc (N *sizeof(double));
for (i=0;i<N;i++)
{
printf("\n enter row %d : ",i+1);
for (j=0;j<N;j++)
scanf(" %lf",&a[i][j]);
}
print(a);
factor = makeUpper(a);
print(a);
printf( "determinant = %g.\n", factor*multDia(a) );
}
Explanation:
1.
The usual way of finding the value of an N × N determinant is to take the first element of the first row and multiply it by the value of the determinant formed by removing that row and that column. This procedure is followed recursively at every step until only a single element remains whose value itself is the value of the 1 × 1 determinant. The sign of the element being multiplied may change depending on its row and column. In general, if the element has row i and column j, then its sign is determined by the formula (−1)^(i+j).
2.
There is another way to solve the problem. We note that if we perform row or column transformations on the determinant, its value does not change. We take advantage of this fact to transform the matrix corresponding to the determinant into an upper or lower triangular matrix and then find its determinant value. It becomes clear that the determinant value of an upper or lower triangular matrix is the product of the diagonal elements. Thus the job of finding a determinant value is basically a matter of making a matrix upper or lower triangular.
3.
To make a matrix upper triangular (makeUpper()), we perform row transformations on the matrix. Another important observation is that multiplication of a determinant D by a value v is a new determinant in which any of the rows of D are multiplied by v. Multiplication of a row by v means multiplying each element in the row by v. Thus we maintain a variable factor that keeps track of the multiplier as the rows of the determinant are multiplied or divided by various factors in the process of upper-triangulation. We assume all elements of the determinant to be floating-point numbers.
4.
In the process of upper-triangulation, if any of the diagonal elements become 0 (anyZero()), that means the value of the determinant is 0 (remember that the value of the determinant is the multiplication of diagonal elements (multDia()).
5.
Since here we assume that the elements are floating-point numbers, the calculations might not be exact. To account for this approximation, we maintain an error term EPSILON which is set to a sufficiently low value (tending to 0). Any value in the range +EPSILON…0…–EPSILON is considered to be 0.
6.
The algorithm for making a matrix upper triangular is as follows:
factor = 1.
for i=1 to N-1 do
for j=0 to i-1 do
divide row i by D[i][j] // divRow().
factor *= D[i][j].
divide row j by D[j][j] // divRow().
factor *= D[j][j].
subtract elements of row j from corresponding elements of row i
// subRow().
check for any of the diagonal elements of D to be 0.
// anyZero().
determinant = factor*product of diagonal elements.
7.
Example:
Let the determinant be
| 8 0 1 |
| 2 1 3 |
| 5 3 9 |.
factor = 1.
Snapshots of the algorithm when run on this determinant are shown here.
I J STEP FACTOR DETERMINANT
1 0 divide row 1 by 2 2 |8 0 1 |
|1 0.5 1.5 |
|5 3 9 |
1 0 divide row 0 by 8 16 | 1 0 0.125 |
| 1 0.5 1.5 |
| 5 3 9 |
1 0 row 1 −= row 0| 16 | 1 0 0.125 |
| 0 0.5 1.375 |
| 5 3 9 |
2 0 divide row 2 by 5 80 | 1 0 0.125 |
| 0 0.5 1.375 |
| 1 0.6 1.8 |
2 0 row 2 −= row 0 80 | 1 0 0.125 |
| 0 0.5 1.375 |
| 0 0.6 1.675 |
2 1 divide row 2 by 0.6 48 | 1 0 0.125 |
| 0 0.5 1.375 |
| 0 1 2.792 |
2 1 divide row 1 by 0.5 24 | 1 0 0.125 |
| 0 1 2.75 |
| 0 1 2.792 |
2 1 row 2 −= row 1 24 | 1 0 0.125 |
| 0 1 2.75 |
| 0 0 0.0417|
Thus, the determinant = 24*(1*1*0.0417) = 1.
Points to Remember:
1.
The first way to solve the problem recursively was natural but clumsy, as it requires removal of a row and a column. So, when designing an algorithm, we should try different approaches and then select the most appropriate one.
2.
Note how we reduced the problem of finding a determinant value to making a matrix upper triangular. These reductions not only simplify a problem but can also help in reusing the code and analysis.
3.
An error term such as EPSILON should be used in floating point computations.
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
#define EPSILON 1e-10
typedef enum {FALSE, TRUE} bool;
int N;
void print( double **a) {
/*
* print the matrix.
*/
int i, j;
for( i=0; i<N; ++i ) {
for( j=0; j<N; ++j )
printf( "%8.4g ", a[i][j] );
printf( "\n" );
}
printf( "\n" );
}
void divRow( double **a, int row, double divisor ) {
/*
* divides row of a by divisor.
*/
int j;
for( j=0; j<N; ++j )
a[row][j] /= divisor;
}
void subRow( double **a, int row1, int row2 ) {
/*
* row1 -= row2.
*/
int j;
for( j=0; j<N; ++j )
a[row1][j] -= a[row2][j];
}
bool anyZero( double **a ) {
/*
* returns TRUE if any diagonal entry of a is zero (less than EPSILON).
*/
int i;
for( i=0; i<N; ++i )
if( fabs(a[i][i]) <= EPSILON )
return TRUE;
return FALSE;
}
double makeUpper( double **a ) {
/*
* makes a an upper-triangular matrix.
* returns 0 if any of the diagonal entries are 0; 1 otherwise.
*/
int i, j;
double factor = 1.0;
double temp;
for( i=1; i<N; ++i ) // dont worry about row 0.
for( j=0; j<i; ++j ) {
temp = a[i][j];
if( fabs(temp) > EPSILON ) {
printf( "factor=%g dividing row %d by %g...\n", factor, i+1, temp );
divRow( a, i, temp );
print(a);
factor *= temp;
}
temp = a[j][j];
if( fabs(temp) > EPSILON && fabs(temp-1.0) > EPSILON ) {
printf( "factor=%g dividing row %d by %g...\n", factor, j+1, temp );
divRow( a, j, temp );
print(a);
factor *= temp;
}
if( fabs(a[i][j]) > EPSILON ) {
printf( "factor=%g row[%d] -= row[%d]...\n", factor, i+1, j+1 );
subRow( a, i, j );
print(a);
}
if( anyZero(a) == TRUE )
return 0;
}
a[N-1][N-1] *= factor; // all but(?) last element of row N-1 are zero.
return 1;
}
double multDia( double **a ) {
/*
* returns multiplication of diagonal elements.
*/
int i;
double factor = 1;
for( i=0; i<N; ++i )
factor *= a[i][i];
return factor;
}
int main() {
int i,j;
double **a;
double factor;
printf("\n enter the dimension of the matrix : ");
scanf(" %d",&N);
a=(double **)malloc (N*sizeof (double *));
for (i=0;i<N;i++)
a[i]=(double *)malloc (N *sizeof(double));
for (i=0;i<N;i++)
{
printf("\n enter row %d : ",i+1);
for (j=0;j<N;j++)
scanf(" %lf",&a[i][j]);
}
print(a);
factor = makeUpper(a);
print(a);
printf( "determinant = %g.\n", factor*multDia(a) );
}
Explanation:
1.
The usual way of finding the value of an N × N determinant is to take the first element of the first row and multiply it by the value of the determinant formed by removing that row and that column. This procedure is followed recursively at every step until only a single element remains whose value itself is the value of the 1 × 1 determinant. The sign of the element being multiplied may change depending on its row and column. In general, if the element has row i and column j, then its sign is determined by the formula (−1)^(i+j).
2.
There is another way to solve the problem. We note that if we perform row or column transformations on the determinant, its value does not change. We take advantage of this fact to transform the matrix corresponding to the determinant into an upper or lower triangular matrix and then find its determinant value. It becomes clear that the determinant value of an upper or lower triangular matrix is the product of the diagonal elements. Thus the job of finding a determinant value is basically a matter of making a matrix upper or lower triangular.
3.
To make a matrix upper triangular (makeUpper()), we perform row transformations on the matrix. Another important observation is that multiplication of a determinant D by a value v is a new determinant in which any of the rows of D are multiplied by v. Multiplication of a row by v means multiplying each element in the row by v. Thus we maintain a variable factor that keeps track of the multiplier as the rows of the determinant are multiplied or divided by various factors in the process of upper-triangulation. We assume all elements of the determinant to be floating-point numbers.
4.
In the process of upper-triangulation, if any of the diagonal elements become 0 (anyZero()), that means the value of the determinant is 0 (remember that the value of the determinant is the multiplication of diagonal elements (multDia()).
5.
Since here we assume that the elements are floating-point numbers, the calculations might not be exact. To account for this approximation, we maintain an error term EPSILON which is set to a sufficiently low value (tending to 0). Any value in the range +EPSILON…0…–EPSILON is considered to be 0.
6.
The algorithm for making a matrix upper triangular is as follows:
factor = 1.
for i=1 to N-1 do
for j=0 to i-1 do
divide row i by D[i][j] // divRow().
factor *= D[i][j].
divide row j by D[j][j] // divRow().
factor *= D[j][j].
subtract elements of row j from corresponding elements of row i
// subRow().
check for any of the diagonal elements of D to be 0.
// anyZero().
determinant = factor*product of diagonal elements.
7.
Example:
Let the determinant be
| 8 0 1 |
| 2 1 3 |
| 5 3 9 |.
factor = 1.
Snapshots of the algorithm when run on this determinant are shown here.
I J STEP FACTOR DETERMINANT
1 0 divide row 1 by 2 2 |8 0 1 |
|1 0.5 1.5 |
|5 3 9 |
1 0 divide row 0 by 8 16 | 1 0 0.125 |
| 1 0.5 1.5 |
| 5 3 9 |
1 0 row 1 −= row 0| 16 | 1 0 0.125 |
| 0 0.5 1.375 |
| 5 3 9 |
2 0 divide row 2 by 5 80 | 1 0 0.125 |
| 0 0.5 1.375 |
| 1 0.6 1.8 |
2 0 row 2 −= row 0 80 | 1 0 0.125 |
| 0 0.5 1.375 |
| 0 0.6 1.675 |
2 1 divide row 2 by 0.6 48 | 1 0 0.125 |
| 0 0.5 1.375 |
| 0 1 2.792 |
2 1 divide row 1 by 0.5 24 | 1 0 0.125 |
| 0 1 2.75 |
| 0 1 2.792 |
2 1 row 2 −= row 1 24 | 1 0 0.125 |
| 0 1 2.75 |
| 0 0 0.0417|
Thus, the determinant = 24*(1*1*0.0417) = 1.
Points to Remember:
1.
The first way to solve the problem recursively was natural but clumsy, as it requires removal of a row and a column. So, when designing an algorithm, we should try different approaches and then select the most appropriate one.
2.
Note how we reduced the problem of finding a determinant value to making a matrix upper triangular. These reductions not only simplify a problem but can also help in reusing the code and analysis.
3.
An error term such as EPSILON should be used in floating point computations.
Subscribe to:
Comments (Atom)