Program to Convert Decimal Numbers to Binary

#include <iostream>
#include <string>

std::string convertTobinary(long num)
{
std::string binaryVal = "";

if(num == 0) return "0";

while(num != 0)
{
if(num %2 == 0)
binaryVal = "0" + binaryVal;
else
binaryVal = "1" + binaryVal;
num /= 2;
}

return binaryVal;
}

int main(int argc, char **argv)
{
std::cout<<"\n binaryVal : "<<convertTobinary(100);
return 0;
}

Longest Common Sub-Sequence implementation in C++

Problem : Given two sequence of elements (usually characters), find the longest subsequence present in both of them. A subsequence is a sequence that appears in the same order,as appeared in original sequence's  .

Example : Strings  "abc","abd","cde" are sub-sequence of string "abcdefghi".

Solution :  With dynamic programming we can solve this problem in O(m*n) time , where m is length of first sequence and n is length of second sequence.


C++ Solution  :

char *get_lcs(char *first_str,char *sec_str,int str_len1,int str_len2)
{
 int m,n,i,j;
 char temp_lcs[100][100];
 int temp_len_lcs[100][100];
 char ret_str[100];

 memset(temp_lcs,'\0',sizeof(temp_lcs));
 memset(temp_len_lcs,0,sizeof(temp_len_lcs));

 for(m = 0;m<str_len1;m++)
 {
  temp_len_lcs[m][0] = 0;
 }

 for(n = 0;n<str_len2+1;n++)
 {
  temp_len_lcs[0][n] = 0;
 }

 for(m = 0;m<str_len1;m++)
 {
  for(n = 1;n<str_len2+1;n++)
  {
   if(first_str[m] == sec_str[n-1])
   {
    temp_len_lcs[m][n] = temp_len_lcs[m-1][n-2] + 1;
    temp_lcs[m][n-1] = '=';
   }
   else
   {
    if(temp_len_lcs[m-1][n-1] >= temp_len_lcs[m][n-2])
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m-1][n-1];
     temp_lcs[m][n-1] = '+';
    }
    else
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m][n-2];
     temp_lcs[m][n-1] = '-';
    }
   }
  }
 }


 memset(ret_str,'\0',sizeof(ret_str));

 i = m;
 j = n;

 while(1)
 {
  if(i == 0 || j == 0)
  {
   break;
  }
  else
  {
   if(temp_lcs[i-1][j-1] == '=')
   {
    i--;
    j--;
    strncat(ret_str,(first_str+i),1);
 
   }
   else if(temp_lcs[i-1][j-1] == '+')
   {
    --i;
   }
   else
   {
    --j;
   }
  }
 }

 return strrev(ret_str);

}


Usage :
Call this function from main  like this

int main(void)
{
 char first_str[100];
 char sec_str[100];
 char lcs[100];

 memset(first_str,'\0',sizeof(first_str));
 memset(sec_str,'\0',sizeof(sec_str));
 memset(lcs,'\0',sizeof(lcs));

 scanf("%s",first_str);
 scanf("%s",sec_str);

 strcpy(lcs,get_lcs(first_str,sec_str,strlen(first_str),strlen(sec_str)));
 std::cout<<lcs<<"\n";

 int a;
 std::cin>>a;
 return 0;
}

Quick sort Implementation in C++

Quick Sort : It is sorting algorithm which takes , O(n*2) time in worst case ,but usually its faster than O(NlogN) algorithms on average case.

It uses , devide and conquer algorithm.
Souce Code : C++ Implementation :

#include <iostream>
#include <cstdio>

using namespace std;

int q_partition(int arr[],int p,int r)
{
    int x,i,j,temp;
   
    x = arr[r];
    i = p-1;
   
    for(j = p;j< (r);j++)
    {
          if(arr[j] <= x)
          {
             i++;
             temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
          }
    }
    temp = arr[i+1];
    arr[i+1] = arr[r];
    arr[r] = temp;
   
    return ++i;
}

void q_sort(int arr[],int p,int r)
{
     if(p < r)
     {
          int q = q_partition(arr,p,r);
          q_sort(arr,p,q-1);
          q_sort(arr,q+1,r);
     }
}

int main(void)
{
    int arr[] = {2,5,1,9,3};
    int i;
   
   
    q_sort(arr,0,4);
    for(i = 0;i<5;i++)
      cout<<"\t"<<arr[i];
   
    int halt;
    cin>>halt;
   
    return 0;
}

Recusive NBit- GrayCode Generator in C++

While Reading tutorials on, one of the , educational institutes website , I have found this interesting property about Gray codes , so i tried implementing it  in C++.

Gray code : The Gray code , is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code.
The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
For More Information please refer wiki : http://en.wikipedia.org/wiki/Gray_code

Recursive Algorithm :
1. Write down the Gray code for N – 1 bits.
2. Copy that same list in reverse order below the original one.
3. Add a 0 bit in front of the codings in the original half of the list and a 1 bit in
front of those in the reversed copy.

C++ Code :

/*
* Author :  Nitendra Bhosle
*/
#include <iostream>
#include <vector>
#include <string>

void nBitGrayCodeGenerator(int n,std::vector<std::string>& resultVec)
{
 //Simple Case
 if(n ==1)
 {
  std::string zero = "0";
  std::string one = "1";
  resultVec.push_back(zero);
  resultVec.push_back(one);
 }
 else //Recursively solve problem by deviding it in simpler problems
 {
  std::vector<std::string> temp ;
  nBitGrayCodeGenerator(n-1,temp);

  for(int i = 0;i<temp.size();++i)
  {
   std::string res = "0"+temp[i];
   resultVec.push_back(res);
  }

  for(int i = temp.size()-1;i>=0;--i)
  {
   std::string res = "1"+temp[i];
   resultVec.push_back(res);
  }
 }
}

int main(void)
{
 std::vector<std::string> resultVec;

 nBitGrayCodeGenerator(4,resultVec);

 for(int i=0;i<resultVec.size();++i)
 {
  std::cout<<"\n"<<resultVec[i];
 }

 int halt;
 std::cin>>halt;

 return 0;
}



Result :  5-Bit GrayCode , generated from the above program

00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000