HUFFMAN CODING

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding and/or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Ph.D. student at MIT



C Code:
int adj[20][20];
main()
{
                int n,i;
                printf("Enter total number of frequencies");
                scanf("%d",&n);
                 int a[100];
                 printf("Enter the frequecy");
                for(i=0;i<n;i++)
                {
                                scanf("%d",&a[i]);
                }
                int result[100][100];
                int fy[100];
                int node[8*n];
                for(i=0;i<8*n;i++)
                {
                                node[i]=i;
                }
                int l=n;int j;
                int lm=0;
                while(1)
                {
                                for(i=lm;i<l;i++)
                                {
                                                for(j=i+1;j<l;j++)
                                                {
                                                                if(a[i]>a[j])//make this from bubble to merge or quick sort to run in O(nlogn)
                                                                {
                                                                                int t=a[i];
                                                                                int res=node[i];
                                                                                a[i]=a[j];
                                                                                node[i]=node[j];
                                                                                a[j]=t;
                                                                                node[j]=res;
                                                                }
                                                }
                                }
                                int ssum=a[lm]+a[lm+1];
                                a[l]=ssum;
                                adj[node[lm]][node[l]]=1;
                                adj[node[lm+1]][node[l]]=2;
                                l++;

                                lm+=2;
                                if(lm==l-1)break;


                }
                for(i=0;i<n;i++)
                {
                           {
                                           int t=0;
                                           int k=0;
                                           int y=i;
                                           int gg=0;
                                           for(k=0;k<20;k++)
                                           {
                                                           if(adj[y][k]!=0)
                                                           {
                                                                           result[i][gg]=adj[y][k]-1;
                                                           gg++;
                                                           y=k;k=0;
                                                           }

                                           }
                                                fy[i]=gg;
                           }
                }
                int ri;
                for(ri=0;ri<n;ri++)
                {for(i=0;i<8*n;i++)
                                {
                                                if(node[i]==ri)break;
                                }
                                printf("%d\t",a[i],fy[i]-1);
                                for(j=fy[ri]-1;j>=0;j--)
                                {
                                                printf("%d",result[ri][j]);
                                }
                               printf("\n");
                }
}

Time Complexity:O(nlog(n))

Strassen Algorithm

Concept(Source Wikipedia):

Let A, B be two square matrices over a ring R. We want to calculate the matrix product C as

If the matrices A, B are not of type 2ⁿ x 2ⁿ we fill the missing rows and columns with zeros.

We partition A, B and C into equally sized block matrices

with

then

With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the C_i,j matrices, the same number of multiplications we need when using standard matrix multiplication.

Now comes the important part. We define new matrices

only using 7 multiplications (one for each M_k) instead of 8. We may now express the C_i,j in terms of M_k, like this:

C Code:

//Please enter n(order of matrix) of form 2^i

int iop=0,jop=0;

static int resc[2][2];

void rec(int n,int comb[])//FOR GETTING OF EVERY 2*2 matrix

{

    int ri;

    comb[0]=0;

for(ri=1;ri<(n/2)+1;ri++)

{

    comb[ri]=(2*ri)-1;

}

}

recadd(int n,int a[][n],int b[][n],int c[][n],int k,int comb[])//For getting matrices of order 2 by 2 which are to be multiplied

{

    if(n!=2)

    {

    int i,j,ridi;

    {

        int al[2][2],bl[2][2];int l=1;

        int ri=comb[0],rj=comb[1];

        int rms=comb[0],lms=comb[1],lml=1;

        while(lml<=k)

        {

        int rmss=comb[0],lmss=comb[1],lmll=1;

        {

            al[0][0]=a[rms][rmss];al[0][1]=a[rms][lmss];al[1][0]=a[lms][rmss];al[1][1]=a[lms][lmss];

        int ris=comb[0],rij=comb[1],lm=1;

        while(lm<=k)

        {

            int l=1;

        int ri=comb[0],rj=comb[1];

                while(l<=k)

                {

                    for(i=0;i<2;i++)

                    {

                        bl[i][0]=b[ri][ris];

                        bl[i][1]=b[ri][rij];

                        ri=rj;

                    }

                    int tyu,yu;

                   mul(al,bl);

                    rmss=++lmss,lmss=comb[++lmll];

                    al[0][0]=a[rms][rmss];al[0][1]=a[rms][lmss];al[1][0]=a[lms][rmss];al[1][1]=a[lms][lmss];

                    ri=++rj;

                    rj=comb[++l];

                }

                int tyu,yu;

                c[iop][jop]=resc[0][0];c[iop][jop+1]=resc[0][1];c[iop+1][jop]=resc[1][0];c[iop+1][jop+1]=resc[1][1];

jop+=2;

if(jop>n-2){iop+=2;jop=0;}

    resc[0][0]=0;resc[0][1]=0;resc[1][0]=0;resc[1][1]=0;

                ris=++rij;

                rij=comb[++lm];

            rmss=comb[0],lmss=comb[1],lmll=1;

             al[0][0]=a[rms][rmss];al[0][1]=a[rms][lmss];al[1][0]=a[lms][rmss];al[1][1]=a[lms][lmss];

            }

        }

    rms=++lms,lms=comb[++lml];

    }

}

    }

    else{

    mul(a,b);

      int tyu,yu;

                for(tyu=0;tyu<2;tyu++)

                {

                    for(yu=0;yu<2;yu++)

                        {printf("%d ",resc[tyu][yu]);resc[tyu][yu]=0;}

                }

    }

}

mul(int al[][2],int bl[][2])//Strassen Matrix Multiplication

{

    int a1,a2,a3,a4,a5,a6,a7;

    a1=(al[0][0]+al[1][1])*(bl[0][0]+bl[1][1]);

    a2=(al[1][0]+al[1][1])*bl[0][0];

    a3=al[0][0]*(bl[0][1]-bl[1][1]);

    a4=al[1][1]*(bl[1][0]-bl[0][0]);

    a5=(al[0][0]+al[0][1])*bl[1][1];

    a6=(al[1][0]-al[0][0])*(bl[0][0]+bl[0][1]);

    a7=(al[0][1]-al[1][1])*(bl[1][0]+bl[1][1]);

resc[0][0]+=(a1+a4+a7-a5);

resc[0][1]+=(a3+a5);

resc[1][0]+=(a2+a4);

resc[1][1]+=(a1+a3+a6-a2);

}

main()

{

printf("Enter the size of Matrix\n");

int n;

scanf("%d",&n);

int a[n][n];

int b[n][n];

int c[n][n];

int mit,nit;

printf("Enter elements of a\n");

for(mit=0;mit<n;mit++)

{

    for(nit=0;nit<n;nit++)

    {

        scanf("%d",&a[mit][nit]);

    }

}

printf("Enter elements of b\n");

for(mit=0;mit<n;mit++)

{

    for(nit=0;nit<n;nit++)

    {

        scanf("%d",&b[mit][nit]);

    }

}

int k=(n/2)+1;

int comb[k];

k--;

rec(n,comb);

recadd(n,a,b,c,k,comb);

for(mit=0;mit<n;mit++)

{

    for(nit=0;nit<n;nit++)

    {

        printf("%d ",c[mit][nit]);

    }

    printf("\n");

}

}

Time Complexity:

The standard matrix multiplication takes approximately 2N³ (where N = 2ⁿ) arithmetic operations (additions and multiplications); the asymptotic complexity is Θ(N³).

The number of additions and multiplications required in the Strassen algorithm can be calculated as follows: let f(n) be the number of operations for a 2ⁿ × 2ⁿ matrix. Then by recursive application of the Strassen algorithm, we see that f(n) = 7f(n−1) + l4ⁿ, for some constant l that depends on the number of additions performed at each application of the algorithm. Hence f(n) = (7 + o(1))ⁿ, i.e., the asymptotic complexity for multiplying matrices of size N = 2ⁿ using the Strassen algorithm is

.

The reduction in the number of arithmetic operations however comes at the price of a somewhat reduced numerical stability,^[3] and the algorithm also requires significantly more memory compared to the naive algorithm. Both initial matrices must have their dimensions expanded to the next power of 2, which results in storing up to four times as many elements, and the seven auxiliary matrices each contain a quarter of the elements in the expanded ones.

Digit fifth powers Problem 30 Project Euler

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

C CODE:

#include<stdio.h>
#include<limits.h>
main()
{
    int counter=0;
    int i;
    int sum=0;
    int result=0;
    for(i=10;i<=355000;i++)
    {
        int t=i;
        sum=0;
        while(t!=0)
        {
            sum=sum+pow(t%10,5);
            t=t/10;
        }
        if(sum==i){result=result+i;}
    }
printf("%d",result);

}

TIME TAKEN:

220ms

RESULT:

443839

Distinct powers Problem 29 Project Euler

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

SOLUTION

#include<stdio.h>
main()
{
    int res=9801;
    int a,b,x;
    for(a=2;a<=100;a++)
    {
        float p=2;
        int i=2;
        while(p>=2)
        {

             p=pow(a,1.0/i);
            int k=p;
            if(k==p){res=res-(98/i);}

            i++;
        }



    }
    res=res+2;//As there will be two numbers which wont be there
printf("%d",res);

}

TIME TAKEN:

9ms

ANSWER:

9183

Number spiral diagonals Problem 28 Project Euler

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

SOLUTION

Starting from the middle element if we add 2 

1+2=3

3+2=5

5+2=7

7+2=9

Now if we start adding 4 and proceed same way 4 times we will get next 4 elements than take six and go on you will get the result.

This is because each cycle increases two elements in a row and column and there will be 4 diagonal elements  so we add an elements 4 times.

C CODE:

#include<stdio.h>
static int a[5][5];
main()
{
int i=1,j;
int res=1;
int k=1,m=2;
while(k<=500)
{
for(j=0;j<4;j++)
{
    i=i+m;
    res=res+i;
}
m=m+2;
k++;
}
printf("%d",res);

}

TIME TAKEN

9ms

RESULT

669171001

Quadratic primes Problem 27 Project Euler

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

BRUTE FORCE:

#include<stdio.h>
#include<math.h>
#include<limits.h>
int pcheck(int n)
{
    int i;
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0){return 0;}
    }
    if(n<=1){return 0;}
    return 1;
}
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
main()
{
int a,b,i;
int max=INT_MIN;
int amax,bmax;
for(a=-999;a<1000;a++)
{
    i=0;
    for(b=-999;b<1000;b++)
    {
         if(((a+b)%2)){continue;}
    int j=0;
    while(1)
    {
        int res=(j*j)+(a*j)+b;
        if(pcheck(res)){j++;}
        else break;
    }
    if(j>max){max=j;amax=a;bmax=b;}
    }
}
int t=amax*bmax;
printf("%d",t);

}

TIME TAKEN:

.591s

ANSWER

-59231

Lexicographic permutations Problem 24 Project euler

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

ALGORITHM::

There will be 9! combination possible when first digit is fixed to zero.Similarly for 1 and 2.But when we further add 9! the sum will exceed 1 million so now first digit is fixed i.e 2.Similarly proceed the same way and fix rest of all the digit.

C CODE::

#include<stdio.h>
static int a[10];
int fact(int n)
{
    if(n>=1)return n*fact(n-1);
    if(n==0){return 1; }
    if(n<0){return 0;}
}
main()
{
    int counter=0;
    int i=0;
    int l=1000000;
    while(l>0)
    {
        while(l>0)
        {
            l=l-fact(9-i);
            counter++;
            a[i]++;
            int j,y=1;
            while(y!=0)
            {
             y=0;

            for(j=0;j<i;j++)
            {
                if(a[j]==a[i]){a[i]++;y++;}
            }
            }
        }
        int j,y=1;;
        a[i]--;


            while(y!=0)
            {
                y=0;
            for(j=0;j<i;j++)
            {

                if(a[j]==a[i]){a[i]--;y++;}
            }
            }
            l=l+fact(9-i);
            if(l==1)break;;
            i++;
}
for(i=0;i<10;i++)
printf("%d",a[i]);
}

TIME TAKEN:

10ms

RESULT:

2783915460