Category: Algorithms


Vinay Deolalikar at HP Labs claim to have proved that P != NP . According to his paper…polynomial time algorithms succeed by successively “breaking up” the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes where blocks whose order is the same as the underlying problem instance require simultaneous resolution. As anyone could predict, the alleged proof of one of the thorniest problems in CS has already been Slashdotted. As i’m not a hardcore mathematician, i’ll not go into details of this…but what is this P vs NP thing all about…lets explore !!

First of all P stands for polynomial time. NP stands for non-deterministic polynomial time. As the name implies, Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data and k is a constant.Complexity is time measured in the number of operations(e.g. comparisons in case of sorting)  it would take, as a function of the number of data items. Now we basically narrowed our discussion to deterministic vs non deterministic (gosh…i luv abstraction) . There is an abstract computational model, an imaginary computer called a Turing machine (TM).A Turing machine is a kind of state machine. At any time the machine is in any one of a finite number of states. Instructions for a Turing machine consist in specified conditions under which the machine will transition between one state and another. At any given time, the Turing Machine is in one of its states, and it is looking at a particular cell on the tape. Depending on what it reads from that cell, it can write a new symbol into that cell, move the tape one cell forward or backward, and go into a different state. This is called a state transition.Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

We are basically concerned about 2 types of turing machines i) deterministic ii) non-deterministic

A deterministic Turing Machine only has one transition from each state for each symbol that it is reading off the tape, in contrast a non-deterministic Turing Machine may have several such transition, i.e. it is able to check several possibilities simultaneously. It has been proven that any problem that can be solved by a non-deterministic TM can be solved by a deterministic TM.When someone says P = NP , he means that one can build a deterministic TM for solving same problem in polynomial time which takes polynomial time in non-deterministic TM.So far nobody have been able to show that it can be done, but nobody has been able to prove that it cannot be done, either…lets  see Vinay Deolalikar’s claim get acceptance or not !!

Also, 2 terms most programmers come across are NP-complete and NP-hard. If someone tells you  that a problem is NP-complete, he basically means that it can be done in polynomial time on a non-deterministic TM, but it will take exponential time on a real computer. NP-hard ( non deterministic polynomial time hard), on the other hand, is a class of problems that are, informally, “at least as hard as the hardest problems in NP”.The precise definition here is that a problem X is NP-hard if there is an NP-complete problem Y such that Y is reducible to X in polynomial time. But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time. Confusing…right ??….don’t go into details…jus pick the essential things  😉

credits :: google

Karatsuba multiplication

The Karatsuba method for fast multiplication is sometimes also called 
Divide-and-Conquer method.It reduces the multiplication of two n digit 
numbers to at most 3n^log3 ~ 3n^1.585 single digit multiplication.

Here's karatsuba algo in detail(check out example 3,Integer Multiplication)
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

c implementation of karatsuba's algorithm ::

//recursively multiplying two big positive numbers 
//using karatsuba's algorithm

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//numbers 'll be stored in array of integers in reverse order
//i.e. array[1] is 10's digit and array[0] is 1's digit
#define MAX_DIGIT 1024

#define CUTOFF 4

void input(int aa[], int *x);
int find1(int a, int b);
void initialize(int xx[], int yy[], int xLen, int yLen, int tLEn);
void karatsuba(int xx[], int yy[], int rr[], int tLen);
void print(int aa[], int x);
void normalMultiplication(int *xx, int *yy, int *rr, int tLen);
void fixCarry(int rr[], int tLen);

int main(int agrc, char *argv[])
{
	int xx[MAX_DIGIT]; //first multiplicand
	int xLen = 0;
	int yy[MAX_DIGIT]; //second multiplicand
	int yLen = 0;
    //result 'll be in first 2d digits...
    //remaining space will be used for various purposes
	int zz[6*MAX_DIGIT];
	
	input(xx, &xLen);	
	assert(xLen >= 0);
	input(yy, &yLen);	
	assert(yLen >= 0);
	//smallest power of 2 greater than both xLen && yLen
	int tLen = find1(xLen, yLen); 
	
	initialize(xx, yy, xLen, yLen, tLen);

	karatsuba(xx, yy, zz, tLen);

//since we didn't checked in karatsuba that digits are b/w 0-9
	fixCarry(zz, 2 * tLen);

	print(zz, tLen);

	return EXIT_SUCCESS;
}

//take input and store it in reverse order in array of integers
void input(int aa[], int *x)
{
	char c;
	if((c=getchar()) != '\n' && *x <= MAX_DIGIT){
		input(aa, x);
		aa[*x] = c - '0';
		(*x)++;
	}else return;
}

//finds smallest power of 2 greater than both a and b
int find1(int a, int b)
{
	int tLen = 1;
	while(tLen <= a || tLen <=b){
		tLen *=2;
	}
	return tLen;
}

//initialize xx and yy to 0 uptil tLen
void initialize(int xx[], int yy[], int xLen, int yLen, int tLen)
{
	int i;
	for(i=xLen; i<tLen; i++) xx[i] = 0;
	for(i=yLen; i<tLen; i++) yy[i] = 0;  
}

void karatsuba(int xx[], int yy[], int rr[], int tLen)
{
	int *a = &xx[tLen/2];
	int *b = &xx[0];
	int *c = &yy[tLen/2];
	int *d = &yy[0];

	//since only 2d space is required for result
	//hence we 'll use remaining space 
	int *wx = &rr[tLen*5]; //sum of xx's halves
	int *wy = &rr[tLen*5 + tLen/2]; //sum of yy's halves

	int *V = &rr[tLen*0];  //location of b*d
	int *U = &rr[tLen*1];  //location of a*c
	int *W = &rr[tLen*2];  //location of (a+b)*(c+d)		

	//for small value of tLen ormal multiplication is faster
	if(tLen <= CUTOFF){
		normalMultiplication(xx, yy, rr, tLen);
		return;
	}
	int i;
	//compute wx and wy
	for(i=0; i<tLen/2; i++){
		wx[i] = a[i] + b[i];
		wy[i] = c[i] + d[i];
	}

	//divide
	karatsuba(b, d, V, tLen/2);
	karatsuba(a, c, U, tLen/2);
	karatsuba(wx, wy, W, tLen/2);

	//conquer and combine
	for(i=0; i<tLen; i++)  W[i]=W[i]-U[i]-V[i];
	for(i=0; i<tLen; i++)  rr[i+tLen/2] += W[i];

}

//print the result 
void print(int aa[], int x)
{
	int i;
	for( i = x-1; i>0; i--)   if(aa[i] != 0)  break;
	for( ; i>=0; i--) 	printf("%d", aa[i]);
	printf("\n");
}

//standard multiplication
void normalMultiplication(int *xx, int *yy, int *rr, int tLen)
{
	int i;
	int j;
	for(i=0; i<2*tLen; i++)  rr[i] = 0;
	for(i=0; i<tLen; i++){
		for(j=0; j<tLen; j++){
			rr[i+j] += xx[i]*yy[j];
		}
	}
}

//to make sure that all numbers are b/w 0-9
void fixCarry(int rr[], int tLen)
{
	int i;
	int carry = 0;
	for(i=0; i<tLen; i++){
		rr[i]+=carry;
		if(rr[i] < 0){
			carry = ( -(rr[i]+1)/10 +1 ); 
		}else{
			carry = rr[i]/10;
		}
		rr[i] = rr[i]- carry*10;
	}
	assert(carry == 0);  //check overflow
}

Conversion of Infix string to Prefix in c++
Have tested this on only some weak test
cases, do tell me if it goes wrong somewhere

#include<iostream>
#include<string>
#include<stack>
#include<cstdio>

using namespace std;

bool precedence(string a, string b);
void infixToPrefix(string s);

int main()
{
        string s;
        cin>>s;

        infixToPrefix(s);

        return 0;
}
void infixToPrefix(string s)
{
        stack<string> operator1;        //operator stack
        stack<string> op;               //operand stack

        for(int i=0; i<s.size(); i++){
                string s6="";
                s6+=s[i];

                //token is an operand
                if(s[i]!='+' && s[i]!='-' && s[i]!='*' && s[i]!='/' && s[i]!='(' && s[i]!=')' && s[i]!='$'){
                        string s5;
                        s5=s[i];
                        op.push(s5);
                }else if(s[i]==')'){  //if right parentheses 
                 //continue to pop operator nd operand stack
                 //till left parentheses is found 
                        while(operator1.top()!="("){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        //pop the left parentheses
                        operator1.pop();


                }else if(s[i]=='(' || operator1.empty() || (!operator1.empty() && precedence(s6,operator1.top())) ){
                        string s5;
                        s5=s[i];
                        operator1.push(s5);
                }else{
                /*Continue to pop operator and 
                operand stack, building prefix
                expressions until the stack is empty or 
                until an operator at the
                top of the operator stack has a lower precedence
                than that of token */
                        while((!operator1.empty()) && !(precedence(s6, operator1.top()))){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        string s5="";
                        s5+=s[i];
                        operator1.push(s5);
                }

        }
        /*If the stack is not empty,
        continue to pop operator and operand stacks building
        prefix expressions until the operator stack is empty.*/
        while(!operator1.empty()){
                string a=operator1.top();
                operator1.pop();
                string b=op.top();
                op.pop();
                string c=op.top();
                op.pop();
                string s2;
                s2=a+c+b;
                op.push(s2);
        }

        while(!op.empty()){
                cout<<op.top()<<" ";
                op.pop();
        }
        cout<<endl;

}

// returns true if precedence of a is more than b
// else return false     
bool precedence(string a, string b)
{
        int aa=0;
        int bb=0;
        if(a=="("){
                return false;
        }else if(b=="("){
                return true;
        }else if(b==")"){
                return true;
        }else if(a==")"){
                printf("undefined operation\n");
                return 0;
        }

        if(a=="+" || a=="-") aa=1;
        if(a=="*" || a=="/") aa=2;
        if(b=="+" || b=="-") bb=1;
        if(b=="*" || b=="/") bb=2;
        if(a=="$") aa=3;
        if(b=="$") bb=3;
        if(aa > bb) return true;

        return false;
}

Recursively converting expression into postfix from prefix ::

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 100

void convert(char prefix[], char postfix[]);
int find(char str[]);
char* substr(char src[], int offset, int len, char dest[]);

int main()
{
	char prefix[MAX];
	char postfix[MAX];
	printf("enter the prefix string\n");
	scanf(" %s", prefix);
	convert(prefix, postfix);
	printf("%s\n", postfix);

	return 0;
}

//algo ::
//1.If the prefix string is a single variable, it is its own postfix equivalent
//2.Let op be the first operator of the prefix string
//3.Find the first operand, opnd1 of the string.Convert it to postfix and call it post1.
//4.Find the second operand, opnd2, of the string.Convert it to postfix and cal it post2.
//5.Concatenate post1, post2, and op.
void convert(char prefix[], char postfix[])
{
	char opnd1[MAX];
	char opnd2[MAX];
	char post1[MAX];
	char post2[MAX];
	char temp[MAX];
	char op[2];
	int length;
	int i,j,m,n;

	//prefix string is single variable
	if((length=strlen(prefix))==1){
		if(isalpha(prefix[0])){
			postfix[0]=prefix[0];
			postfix[1]='\0';
			return;
		}

		printf("illegal prefix string\n");
		exit(1);
	}

	//prefix string is longer
	op[0]=prefix[0];
	op[1]='\0';
	substr(prefix,1,length-1,temp);
	m=find(temp);
	substr(prefix, m+1, length-m-1, temp);
	n=find(temp);

	if((op[0]!='+' && op[0]!='-' && op[0]!='*' && op[0]!='/') || (m==0) || (n==0) || (m+n+1!=length)){
		printf("illegal prefix string\n");
		exit(1);
	}
	substr(prefix, 1, m, opnd1);
	substr(prefix, m+1, n, opnd2);

	convert(opnd1, post1);
	convert(opnd2, post2);
	strcat(post1, post2);
	strcat(post1, op);

	substr(post1, 0, length, postfix);
}

int find(char str[])
{
	char temp[MAX];
	int length;
	int i,j,m,n;

	if((length=strlen(str))==0)	return 0;

	//first character is a letter
	if(isalpha(str[0])!=0)		return 1;

	//otherwise find the first operand
	if(strlen(str)<2)	return 0;

	substr(str, 1, length-1, temp);
	m=find(temp);

	//no valid prefi operand or no second operand
	if(m==0 || strlen(str)==m)	return 0;

	substr(str, m+1, length-m-1, temp);
	n=find(temp);

	if(n==0)	return 0;

	return (m+n+1);
}

char* substr(char src[], int offset, int len, char dest[])
{
	int i;
	for(i = 0; i < len && src[offset + i] != '\0'; i++){
		dest[i] = src[i + offset];
	}
	dest[i] = '\0';

	return dest;
}
//P.S.... COPIED FROM MY TEXTBOOK

Conversion of prefix to postfix using stack ::

#include <iostream>
#include <stack>

using namespace std;

#define MAX 100
#define OP1_FLAG '#'

bool isOperator(char ch);

int main()
{
	//prefix input expression and postfix output expression
	char prefix[MAX],postfix[MAX];
	stack<char> stk;

	cout<<"Enter the prefix expression\n";
	cin>>prefix;

	int j=0;
	for (int i=0;prefix[i];i++){
		if(isOperator(prefix[i])){
			stk.push(prefix[i]);
		}else {
			//as sequence of operand in prefix and
            //postfix expressions are same
			postfix[j]=prefix[i];
			j++;
	         /*OP1_FLAG is a flag that indicates the left operand
              for this operator is already converted to postfix.
              After popping out these OP1 operators the next
              operator is marked OP1_FLAG*/
			while(!stk.empty() && stk.top()==OP1_FLAG){
				stk.pop();
				postfix[j]=stk.top();
				j++;
				stk.pop();
			}
			stk.push(OP1_FLAG);
		}
	}

    	postfix[j]=0;

	cout<<"Postfix expression is ::  " << postfix << endl;

	return 0;

}

bool isOperator(char ch){
	if(ch=='+' || ch=='-' || ch == '*' || ch == '/' || ch == '$' || ch == '%')	return true;
	else	return false;
}

Rabin–Miller primality test

It is an algorithm which determines whether a given number is prime or not.

Rabin_miller_primality_test

#include<iostream>
#include<cstdlib>
#include<cstdio>

using namespace std;

bool Miller(long long p,int iteration);
long long mulmod(long long a,long long b,long long c);
unsigned long long modulo(unsigned long long  a,unsigned long long b,unsigned long long c);

int main()
{
        int t=0;
        cin>>t;
        while(t--){
                long long x=0;
                scanf("%lld", &x);
                if(Miller(x,15)){
                        printf("YES\n");
                }else{
                        printf("NO\n");
                }
        }

        return 0;
}

/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration){
    if(p<2){
        return false;
    }
    if(p!=2 && p%2==0){
        return false;
    }
    long long s=p-1;
    while(s%2==0){
        s/=2;
    }
    for(int i=0;i<iteration;i++){
        long long a=rand()%(p-1)+1,temp=s;
        long long mod=modulo(a,temp,p);
        while(temp!=p-1 && mod!=1 && mod!=p-1){
            mod=mulmod(mod,mod,p);
            temp *= 2;
        }
        if(mod!=p-1 && temp%2==0){
            return false;
        }
    }
    return true;
}

/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c){
    long long x = 0,y=a%c;
    while(b > 0){
        if(b%2 == 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

/* This function calculates (ab)%c */
unsigned long long modulo(unsigned long long  a,unsigned long long b,unsigned long long c){
    unsigned long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
    while(b > 0){
        if(b%2 == 1){
            x=mulmod(x, y, c);
        }
        y = mulmod(y, y, c); // squaring the base
        b /= 2;
    }
    return x%c;
}

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

one of my fav problems, learned a lot of stuff from it.

Implementation using sieve of Eratosthenes ::

#include <iostream>
#include <vector>

using namespace std;

int main()
{
        unsigned const n = 10000000;  //value of n as per requirement
        vector<bool> p(n, true);
        long long int sum = 0;

        // sieve of Eratosthenes
        for(unsigned i = 2; i*i <= n; ++i)
                for(unsigned j = 2*i; j < n; j += i)
                        p[j] = false;

        // find m-th prime
        unsigned i = 2;
        for(unsigned c = 0; i !=2000000 ; ++i){
                if(p[i]) sum+=i;
        }

        cout<<sum<<endl;

        return 0;
}

Implementation using Sieve of Atkins::

/*
 *  Adaptation of the Sieve of Atkin (faster than the Sieve of Eratosthenes), but using modulo-thirty.
 *  The idea is:
 *  - 30 is the lcm of 2, 3 and 5 (the first 3 primes);
 *  - get the list of 30 next numbers (1..30, 31..60, etc) and discard all multiples of 2, 3 and 5;
 *  - it will remain 1, 7, 11, 13, 17, 19, 23 and 29
 *  - so, you only have to test the numbers in this groups.
 *
 *   good ref. --> http://www.codeproject.com/KB/recipes/PrimeSuspect.aspx
 *      
 */


#include <iostream>
#include <stdbool.h>
#include <math.h>
#include<cstdio>
#include<vector>
#define ulli unsigned long long int

using namespace std;

bool prime(ulli n, vector<unsigned long long int> &vec) {
    int i;
    ulli max = (ulli)sqrt((ulli)n);
    for (i = 0; vec[i] <= max; i++)
        if (n % vec[i] == 0)
            return (false);
    return (true);
}

#define prime_test if (prime(num,primes)) primes[++i] = num
int main()
{
    int i = 9;
    ulli num = 31;
    vector<ulli> primes(200001);
    primes[0]=2;primes[1]=3;primes[2]=5;primes[3]=7;primes[4]=11;primes[5]=13;primes[6]=17;primes[7]=19;primes[8]=23;primes[9]=29;
    while (i < 200000) {
        prime_test; // 1
        num+=6;
        prime_test; // 7
        num+=4;
        prime_test; // 11
        num+=2;
        prime_test; // 13
        num+=4;
        prime_test; // 17

        num+=2;
        prime_test; // 19
        num+=4;
        prime_test; // 23
        num+=6;
        prime_test; // 29
        num+=2;
    }
    long long int sum=0;
    int k=0;
    while(primes[k]<2000000){
        sum+=primes[k];
        k++;
    }
    printf("%llu\n",sum);
    return 0;
}
#undef prime_test
#undef ulli