How to roundoff given real number to nearest integer(Optimizing Algorithm/Program Step by Step)

Without using builtin function round,ceil,floor..

Example:
if f = 3.7 then i = 4
if f = 3.2 then i = 3

Code:

General logic:

int roundoff(float n)
{
int k = (n *10) %10;
if(k>5)
k=n+1;
else
k=n;
return k;
}

Optimized : int roundoff(float n)
{
int k = n + 0.5;
return k;
}

How to Check for given number is Prime or Not (Optimizing step by step)

General Algorithm:

for(i=2;i<n;i++)
{
if(n%2==0)
break;
}
if(i==n)
puts("Prime");
else
puts("Not Prime");

Better Solution:

for(i=2;i<n/2;i++) //perfect divisor will be less than n/2
{
if(n%2==0)
break;
}
if(i==n)
puts("Prime");
else
puts("Not Prime");


Even Better Solution:

int k = sqrt(n);
for(i=2;i<k;i++) //At least one factor will be less than square_root(n)
{
if(n%2==0)
break;
}
if(i==k)
puts("Prime");
else
puts("Not Prime");


Even more Better Solution:

if(n%2==0)
{
puts("Prime");
}
else
{
for(i=3;i<k;i+=2)
//if it is not divisible by 2, then no need to check for multiple of 2
{
if(n%2==0)
break;
}
if(i==k)
puts("Prime");
else
puts("Not Prime");
}

Optimizing Program for Fibonacci Series (Optimizing Algorithm/Program Step by Step)

Problem:
F(0)=0;
F(1)=1;
F (n)=(F(n-1)+F(n-2)) mod 10
efficient algorithm that computes this function.


Algo I :

int rec (int n){
    if (n<2)
     return (n);
   else
     return((rec(n-1)+rec(n-2))%10);

}


Exponential time

Linear Space

Algo II : 

int dp (int n){
f[0]=0;
f[1]=1;
for (i=2;i<=n; ++i)
f [n] =(f[n-1]+f[n-2])%10;
}

Linear time.
Linear space.

Algo III:

int linear (int n){
a=0; b=1; c=n;
for (i=2;i<=n; ++i){
c=(a+b)%10;
a=b;
b=c;
}
return c;
}

Linear time.
Constant space.

Algo IV:

For further optimization, we should analyse the output sequence and check whether it is periodic or not.
If it is periodic @ x then find value till x and use (n mod x ) to compute nth term of series.
e.g, Fibonacci series is periodic (not known exactly but 'x' is between 61-72).

Max Subsequence Problem (Optimizing Algorithm/Program Step by Step)

Problem:
Given a sequence of integers A1, A2, …, An, find the maximum possible value of a subsequence Ai, …, Aj.
Numbers can be negative.
You want a contiguous chunk with largest sum.

Example:   -2, 11, -4, 13, -5, -2
The answer is  20    (subseq.  A2 through A4).

    Algo I :

        int Sum = 0;

 for( int i = 0; i < a.size( ); i++ )
 for( int j = i; j < a.size( ); j++ )
 {
 int thisSum = 0;
 for( int k = i; k <= j; k++ )
 thisSum += a[ k ];
 if( thisSum > maxSum ) maxSum   = thisSum;
 }
 return maxSum;

    Complexity: O(n3)               [algo not good for large number of inputs e.g, size > 10 ^7]

    Algo II :

    into maxSum = 0;

 for( int i = 0; i < a.size( ); i++ )
 int thisSum = 0;
 for( int j = i; j < a.size( ); j++ )
 {
      thisSum += a[ j ];
      if( thisSum > maxSum )
   maxSum   = thisSum;
 }
 return maxSum;

    Complexity: O(n2)               [just good... ]
 
     
    Algo III:

        This algorithm uses divide-and-conquer paradigm. The max subsequence is entirely in the left half, entirely in the right half, or it straddles the midpoint.
Example:
 left half  | right half
 4   -3   5 -2 |    -1  2  6   -2
 Max in left is  6  (A1 through A3); max in right is  8  (A6 through A7). But straddling max is 11 (A1 thru A7).  


    How do we find the straddling max subsequence?
    Key Observation:
        Left half of the straddling sequence is the max subsequence ending with -2.
        Right half is the max subsequence beginning with -1.

        A linear scan lets us compute these in O(n) time.

        The divide and conquer is best analyzed through recurrence:

 T(1) = 1
 T(n) = 2T(n/2) + O(n)

        This recurrence solves to T(n) = O(n log n).
   
    Complexity: O(nlog(n))               [better ...still not best ]


    Algo IV:


 int maxSum = 0, thisSum = 0;

  for( int j = 0; j < a.size( ); j++ )
 {
 thisSum += a[ j ];

 if ( thisSum > maxSum )
 maxSum = thisSum;
 else if ( thisSum < 0 )
 thisSum = 0;
 }
     return maxSum;
        }

     Complexity: O(n)               [ best ]

Conversion of a relation (table ) from 1NF to 2NF to 3NF to BCNF

Normalization:

Definition

    Normalization can be viewed as a series of steps (i.e., levels) designed, one after another, to deal with ways in which tables can be "too complicated for their own good". The purpose of normalization is to reduce the chances for anomalies to occur in a database. The definitions of the various levels of normalization illustrate complications to be eliminated in order to reduce the chances of anomalies. At all levels and in every case of a table with a complication, the resolution of the problem turns out to be the establishment of two or more simpler tables which, as a group, contain the same information as the original table but which, because of their simpler individual structures, lack the complication. 

    Through normalization we want to design for our relational database a set of files that (1) contain all the data necessary for the purposes that the database is to serve, (2) have as little redundancy as possible, (3) accommodate multiple values for types of data that require them, (4) permit efficient updates of the data in the database, and (5) avoid the danger of losing data unknowingly. 

Advantage/Disadvantage

Adv.         -   Remove redundancy, Anomaly, Storage Efficiency 

Dis. Adv.  -  Time Consuming, Difficult, maintenance overhead (higher NF-> more tables)

Terminology

Keys – Super, Candidate, Primary.

Attributes – Prime/key , Non prime/non key.

Functional Dependency 1- Full, Partial, Transitive, overlapping, trivial, non trivial, complete non trivial.

Decomposition - Lossless Join (Algo for 2R and >2R). & Dependency preserving.

Armstrong Axioms – Reflexivity, Augmentation, Transitivity.

Closure –Attribute, F.D (If F is a set of functional dependencies for a relation R, then the set of all functional dependencies that can be derived from F, F+, is called the closure of F. ).

Redundant F.D.

Steps/Process/flowchart

1st Normal Form (1NF): 

            A table (relation) is in 1NF  

            1. If There are no duplicated rows in the table.

            2. Each cell is single-valued (i.e., there are no repeating groups or arrays).3. Entries in a column (attribute,         field) are of the same kind.

            Note: The order of the rows is immaterial; the order of the columns is immaterial. 

            Note: The requirement that there be no duplicated rows in the table means that the table has a key (although the key might be made up of more than one column—even, possibly, of all the columns). 

2nd Normal Form (2NF) : 

            A table is in 2NF 

            1. If it is in 1NF and 

            2. if all non-key attributes are dependent on all of the key.

            Note: Since a partial dependency occurs when a non-key attribute is dependent on only a part of the (composite) key, the definition of 2NF is sometimes phrased as, "A table is in 2NF if it is in 1NF and if it has no partial dependencies."

3rd Normal Form (3NF): 

            A table is in 3NF  

            1. If it is in 2NF and 

            2. If it has no transitive dependencies.

Boyce-Codd Normal Form (BCNF) : 

        A table is in BCNF 

        1. If it is in 3NF 

        2. If every determinant is a candidate key.

4th Normal Form (4NF): 

        A table is in 4NF 

        1. If it is in BCNF 

        2. If it has no multi-valued dependencies.

5th Normal Form (5NF): 

        A table is in 5NF, also called "Projection-Join Normal Form" (PJNF), 

        if it is in 4NF and if every join dependency in the table is a consequence of the candidate keys of the table.

Domain-Key Normal Form (DKNF): 

        A table is in DKNF if every constraint on the table is a logical consequence of the definition of keys and domains.