Sieve of Eratosthenes

Sieve of Eratosthenes is one of the efficient method of finding the prime numbers in a given range.It is popularly known as Prime Sieve.The steps  involved are
1.create a range from 2 to any given range n.
2.let p be a variable initially equals to 2 (the first prime number)
3.Remove all the multiples of p
4.Now,p equals to the next number greater than p that is unmarked,If there was no such number, then you can stop.
5.Otherwise, p now equal this number (which is the next prime),
Example
 Lets find the prime numbers from 2 to 30

1.Create a list from 2 to 30

  2  3  4  5  6 7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 27  28  29  30 31 
  32  33 34 35 36 37 38 39 40

 Initially p is 2 so,mark all the multiples of 2
 
  2  3  4  5  6 7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 27  28  29  30 31    
  32 33 34 35 36 37 38 39 40

   Now p is equal to the next unmarked number i.e., 3


Now mark all the multiples of 3

   2  3  4  5  6 7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 27  28  29  30 31 
  32  33  34  35  36  37  38  39  40

Now p is equal to the next unmarked number , i.e., 5

Now  mark all the multiples of 5

   2  3  4  5  6 7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 27  28  29 30 31 
  32  33  34  35  36  37  38  39  40

  The algorithm continues to find the next unmarked number and continues to mark all its multiples but it doesn’t  produce any change in the current list.

So  finally we obtained the prime numbers from 2 to 30 as

     2  3  5  7  11  13  17  19  23  29 31 37

Thus, it is as simple as that !!!!

Now lets look into the Implementation in C …..

#include "stdio.h"
#include "math.h"
int main(void) {
 // your code goes here
 int a[40],n=40,i,j;
 for(i=0;i< n;i++)
 a[i]=1;
 for(i=2;i< sqrt(n);i++)
 {
  if(a[i])
  for(j=i;i*j< n;j++)
  {
   a[i*j]=0;
  }
 }
 printf("primes from 2 to 40");
 for (i = 2;i< n; i++)
        if (a[i])
            printf("%d\n", i);
 
 return 0;
 

Output

primes from 2 to 40
2
3
5
7
11
13
17
19
23
29
31
37

Time Complexity Of Algorithms

The time complexity of an algorithm is the time required for an algorithm for its complete execution.The time complexity of an algorithm usually depends on the size of the input.

Some common time complexities

The time complexity of various algorithms would be constant O(1),Linear O(n),quadratic O(n2),Exponential O(2n),factorial O(n!) etc

Now let us see some of the time complexities.

O(1)

The time complexity of an algorithm is said to be O(1),If it requires same amount of time for execution regardless of the size of the input.

Example:

It takes constant time to access an element in an array of any size.

O(n)

The time complexity of an algorithm is said to be O(n),If the time of execution of the algorithm increases linearly with increase in size of the input.

Example

int main(void) {
int arr[5],i;
printf("enter 5 integers\n");
for(i=0;i<5;i++)
scanf("%d",&arr[i]);
printf("It takes linear time access the elements of an array\n");
for(i=0;i<5;i++)
printf("%d",arr[i]);
 return 0;
}

Output

enter 5 integers
1
2
3
4
5
It takes linear time access the elements 
of array
12345

O(logn)

The time complexity of an algorithm is said to be O(logn),If the time of execution of the algorithm increases logarithmically with increase in size of the input.

O(loglogn)

The time complexity of an algorithm is said to be O(loglogn),If the loop variables are increased or decreased by a constant amount.

int main() 
{
 
int i,n=2,c=3;
for(i=2;i<=n;i=pow(i,c))
printf("Code Titans\n");
return 0;
}

Output

Code Titans

O(n^c)

The time complexity of an algorithm is said to be O(nc) which is nothing but the time required to execute the innermost loop.

Example for n²

int main() {
int i,j;
for( i=0;i<3;i++)
{
    for(j=0;j<2;j++)
    {
        printf("Code Titans\n");
    }
}
 return 0;
}

Output

Code Titans
Code Titans
Code Titans
Code Titans
Code Titans
Code Titans

O(cⁿ)

The time complexity of an algorithm is said to be O(cⁿ),If the time of execution of the algorithm increases exponentially with increase in size of the input.

Example

Brute force method of n-queen problem take O(nⁿ)

O(n!)

Some algorithms take factorial time for their execution which are considered as the slowest algorithms.

Example

Travel Sales person

Dynamic Programming-2

In continuation to Dynamic Programming,let us discuss a simple problem.

Fibonacci Series:

A series of numbers in which each number is the sum of the two preceding numbers.
Fibonacci sequence is widely used for better understanding of DP.
Let us consider a general method to find the nth member of the fibonacci series.

General Recursive method of Fibonacci:

fib(int n)
{
 if(n==0)
 return 0;
 else if(n==1)
 return 1;
 else
 return (fib(n-1)+fib(n-2));
}

             

Consider the following recursive calls for n=5.

 
Time complexity is T(n)=T(n-1)+T(n-2) i.e, Exponential

What is Dynamic Programming...

Dynamic programming(DP) is the general and powerful method of solving some class of problems.It is often used for optimization.We break a complex problem into smaller sub problems and solve each of the individual sub problems at once and store the solution. When we suppose to solve a sub problem,we check whether it is already computed or not.if it is so,we just look its solution.

so,essentially  DP=sub problems+"reuse of computed results"

Memoization:

The technique of reusing the stored solutions of sub problems without recomputing them is known as 'Memoization'.

How to implement DP?

There are two approaches to implement DP.

1)Top down approach

2)Bottom up approach

Top-down approach:

Here, we divide the complex problem into number of sub problems.whenever we attempt to solve a new sub problem, we first check the table to see if it is already solved.if a solution has been recorded,we use it directly,otherwise we solve the sub problem and add its solution to the table.

Bottom-up approach:

In this case we try solving the sub problems first and use their solutions to build-on and arrive at solutions to bigger sub problems.

When to use Dp ?

DP has two properties.

1)Optimal substructures.

2) Overlapping sub problems

Optimal substructures:

A problem is said to have optimal substructure when there exists an optimal solution derived from optimal solutions of its sub problems.

Overlapping sub problems:

Overlapping sub problems is nothing but repetition of sub problems. 

So,whenever you feel the given problem has these properties,you can choose DP to solve it.

Time and Space complexities:

The time complexity of DP problems vary from problem to problem.However,we generally calculate time complexity for DP problems as 

T.C = no.of sub problems * time taken to solve each sub problem 

The space complexity for DP problems depends on the data structure that we use  to store the computed results of the sub problems.

Points to be noted:   

DP vs Recursion:

It seems to be that DP is quite similar to recursion.But,there is a significant difference between them.

Recursion helps just to breakdown the problems into sub problems.The sub problem may be computed more than once.

Whereas,in DP we store the result of the previous computation to avoid computing the same sub problem once again.

DP vs D&C:

If we say dividing the complex problems into sub problems most of us may think about divide and conquer So,I want to make it clear that D&C method is used to solve the non-overlapping sub problems,but in DP we deal with overlapping sub problems.