Server and client example with C sockets on Linux

In this example we shall build a basic ECHO client and server. The server/client shown here use TCP sockets or SOCK_STREAM. TCP sockets are connection oriented, means that they have a concept of independant connection on a certain port which one application can use at a time. The concept of connection makes TCP a "reliable" stream such that if errors occur, they can be detected and compensated for by resending the failed packets.

Server

Lets build a very simple web server. The steps to make a webserver are as follows :

1. Create socket
2. Bind to address and port
3. Put in listening mode
4. Accept connections and process there after.

UVA 326

http://uva.onlinejudge.org/external/3/326.html

using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<cmath>
#include<queue>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
int main()
{
    int N,t,k;
    while(cin>>N && N)
    {
        vector<int> inp;
        FOR(i,N)
        {
            cin>>t;
            inp.push_back(t);
        }
        cin>>k;
        vector<int> res;
        res.push_back(inp[inp.size()-1]);
        for(int i=0;i<N-1;i++)
        {
            for(int j=N-1;j>i;j–)
            {
                inp[j]=inp[j]-inp[j-1];
            }
            res.push_back(inp[N-1]);
        }
        for(int j=0;j<k;j++)
        {
            for(int i=res.size()-2;i>=0;i–)
            {
                res[i]=res[i]+res[i+1];
            }
        }
        printf(“Term %d of the sequence is %d\n”,N+k,res[0]);
    }
}

UVA 507

http://uva.onlinejudge.org/external/5/507.html

#include<iostream>
using namespace std;

void max(int a[],int n,int j)
{
 int m_s=1,m_e=2,m=a[0],s=a[0],st=0;
 
 for (int i=1;i<n;i++)
 {
  if (s>=0)
   s+=a[i];
  else
  {
   st=i;
   s=a[i];
  }
  
  if (s>m)
  {
   m=s;
   m_s=st+1;
   m_e=i+2;
  }
  else if (s==m)
  {
   if (i-st > m_e-m_s)
   {
    m=s;
    m_s=st+1;
    m_e=i+2;
   }
   else if (i-st == m_e-m_s)
   { 
    if (st < m_s)
    {
     m=s;
     m_s=st+1;
     m_e=i+2;
    }
   }
  }
 }
 
 if (m>=0)
  cout<<"The nicest part of route "<<j<<" is between stops "<<m_s<<" and "<<m_e<<endl;
 else
  cout<<"Route "<<j<<" has no nice parts\n";
}

int main()
{
 int n,s;
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>s;
  int a[s-1];
  for (int j=0;j<s-1;j++)
   cin>>a[j];
  
  max(a,s-1,i);
 }
}

UVA 481

http://uva.onlinejudge.org/external/4/481.html

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
  if (a[b.back()] < a[i]) 
                {
   p[i] = b.back();
   b.push_back(i);
   continue;
  }
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
                {
   int c = (u + v) / 2;
   if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
                // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
                {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[100000],i=0;
 
 while(scanf("%d",&a[i])!=EOF)
  i++;
 vector<int> seq(a, a+i); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
        printf("%d\n-\n",lis.size());
 for (size_t i = 0; i < lis.size(); i++)
  printf("%d\n", seq[lis[i]]);   
 
 return 0;
}

UVA 616

http://uva.onlinejudge.org/external/6/616.html

#include<iostream>
using namespace std;

int no(int c);
void print(int p,int n);

int main()
{
 int c,p;

 cin>>c;
 while(c>0)
 {
  p=no(c);
  print(p,c);
  cin>>c;
 }
}

void print(int p,int n)
{
 if(p>0)
 {
  cout<<n<<" coconuts, "<<p<<" people and 1 monkey\n";
 }
 else
  cout<<n<<" coconuts, no solution\n";
}


int no(int c)
{
 int j,a,b,d;

 for(int i=10;i>1;i--)
 {
  if(c%i==1)
  {
   b=c;
   a=1;
   for(j=1;j<=i;j++)
   {
    if (b%i==1)
    {
     b=((b-1)/i)*(i-1);
    }
    else
    {
     a=0;
     break;
    }
   }
   if ((a==1)&&(b%i==0))
   {
    return i;
   }
   else if ((a==0)&&(i==2))
    return -1;
  }
 }
 return -1;
}

CYK algorithm implementation

Implementation of CYK algorithm in C++

The CYK algorithm is a parsing algorithm for context-free grammars. It employs bottom-up parsing and dynamic programming. It is used to check whether a particular string can be generated from a set of productions or not.

#include<iostream>  
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b; i++)

string gram[MAX][MAX];	//to store entered grammar
string dpr[MAX];
int p,np;		//np-> number of productions

inline string concat( string a, string b)	//concatenates unique non-terminals
{
	int i;
	string r=a;
	for(i,0,b.length())
		if(r.find(b[i]) > r.length())
			r+=b[i];
	return (r);
}

inline void break_gram(string a)	//seperates right hand side of entered grammar
{
	int i;
	p=0;
	while(a.length())
	{
		i=a.find("|");
		if(i>a.length())
		{
			dpr[p++] = a;
			a="";
		}
		else
		{
			dpr[p++] = a.substr(0,i);
			a=a.substr(i+1,a.length());
		}
	}
}

inline int lchomsky(string a)	//checks if LHS of entered grammar is in CNF
{
	if(a.length()==1 && a[0]>='A' && a[0]<='Z')
		return 1;
	return 0;
}

inline int rchomsky(string a)	//checks if RHS of grammar is in CNF
{
	if (a.length() == 1 && a[0]>='a' && a[0] <='z')
		return 1;
	if (a.length()==2 && a[0]>='A' && a[0]<='Z' && a[1]>='A' && a[1]<='Z' )
		return 1;
	return 0;
}

inline string search_prod(string p)	//returns a concatenated string of variables which can produce string p
{
	int j,k;
	string r="";
	for(j,0,np)
	{
		k=1;
		while(gram[j][k] != "")
		{
			if(gram[j][k] == p)
			{
				r=concat(r,gram[j][0]);
			}
			k++;
		}
	}	
	return r;
}

inline string gen_comb(string a, string b)	//creates every combination of variables from a and b . For eg: BA * AB = {BA, BB, AA, BB}
{
	int i,j;
	string pri=a,re="";
	for(i,0,a.length())
		for(j,0,b.length())
		{
			pri="";
			pri=pri+a[i]+b[j];
			re=re+search_prod(pri);		//searches if the generated productions can be created or not
		}		
	return re;
}

int main()
{
	int i,pt,j,l,k;
	string a,str,r,pr,start;
	cout<<"\nEnter the start Variable ";
	cin >> start;
	cout<<"\nNumber of productions ";
	cin >> np;
	for(i,0,np)
	{
		cin >> a;
		pt=a.find("->");
		gram[i][0] = a.substr(0,pt);
		if (lchomsky(gram[i][0]) == 0)
		{
			cout<<"\nGrammar not in Chomsky Form";
			abort();
		}
		a = a.substr(pt+2, a.length());
		break_gram(a);
		for(j,0,p)
		{
			gram[i][j+1]=dpr[j];
			if (rchomsky(dpr[j]) == 0)
			{
				cout<<"\nGrammar not in Chomsky Form";
				abort();
			}
		}
	}
	string matrix[MAX][MAX],st;
	cout<<"\nEnter string to be checked : ";
	cin >> str;
	for(i,0,str.length())		//Assigns values to principal diagonal of matrix
	{
		r="";
		st = "";
		st+=str[i];
		for(j,0,np)
		{
			k=1;
			while(gram[j][k] != "")
			{
				if(gram[j][k] == st)
				{
					r=concat(r,gram[j][0]);
				}
				k++;
			}
		}
		matrix[i][i]=r;
	}
	int ii,kk;
	for(k,1,str.length())		//Assigns values to upper half of the matrix
	{
		for(j,k,str.length())
		{
			r="";
			for(l,j-k,j)
			{
				pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
				r = concat(r,pr);
			}
			matrix[j-k][j] = r;
		}
	}

	for(i,0,str.length())	//Prints the matrix
	{
		k=0;
		l=str.length()-i-1;
		for(j,l,str.length())
		{
			cout<<setw(5)<<matrix[k++][j]<<" ";
		}
		cout<<endl;
	}
			
	int f=0;
	for(i,0,start.length())
		if(matrix[0][str.length()-1].find(start[i]) <= matrix[0][str.length()-1].length())	//Checks if last element of first row contains a Start variable
		{
			cout<<"String can be generated\n";
			return 0;
		}
	cout<<"String cannot be generated\n";
	return 0;
}

Sample Input ::

Enter the start Variable S

Number of productions 4

S->AB|BC
A->BA|a
B->CC|b
C->AB|a

Enter string to be checked :baaba

Output ::