Randomized Quick sort

 #include<iostream>

#include<cstdlib>

using namespace std;

void swap(int *a, int *b) {

   int temp;

   temp = *a;

   *a = *b;

   *b = temp;

}

int Partition(int a[], int l, int h) {

   int pivot, index, i;

   index = l;

   pivot = h;

   for(i = l; i < h; i++) {

      if(a[i] < a[pivot]) {

         swap(&a[i], &a[index]);

         index++;

      }

   }

   swap(&a[pivot], &a[index]);

   return index;

}

int RandomPivotPartition(int a[], int l, int h) {

   int pvt, n, temp;

   n = rand();

   pvt = l + n%(h-l+1);

   swap(&a[h], &a[pvt]);

   return Partition(a, l, h);

}

int QuickSort(int a[], int l, int h) {

   int pindex;

   if(l < h) {

      pindex = RandomPivotPartition(a, l, h);

      QuickSort(a, l, pindex-1);

      QuickSort(a, pindex+1, h);

   }

   return 0;

}

int main() {

   int n, i;

   cout<<"\nEnter the number of data element to be sorted: ";

   cin>>n;

   int arr[n];

   for(i = 0; i < n; i++) {

      cout<<"Enter element "<<i+1<<": ";

      cin>>arr[i];

   }

   QuickSort(arr, 0, n-1);

   cout<<"\nSorted Data ";

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

      cout<<"->"<<arr[i];

   return 0;

}

RADIX SORT

#include<stdio.h>

int get_max (int a[], int n){

   int max = a[0];

   for (int i = 1; i < n; i++)

      if (a[i] > max)

         max = a[i];

   return max;

}

void radix_sort (int a[], int n){

   int bucket[10][10], bucket_cnt[10];

   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;

   lar = get_max (a, n);

   while (lar > 0){

      NOP++;

      lar /= 10;

   }

   for (pass = 0; pass < NOP; pass++){

      for (i = 0; i < 10; i++){

         bucket_cnt[i] = 0;

      }

      for (i = 0; i < n; i++){

         r = (a[i] / divisor) % 10;

         bucket[r][bucket_cnt[r]] = a[i];

         bucket_cnt[r] += 1;

      }

      i = 0;

      for (k = 0; k < 10; k++){

         for (j = 0; j < bucket_cnt[k]; j++){

            a[i] = bucket[k][j];

            i++;

         }

      }

      divisor *= 10;

      printf ("After pass %d : ", pass + 1);

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

         printf ("%d ", a[i]);

     // printf ("");

   }

}

int main (){

   int i, n, a[10];

   printf ("Enter the number of items to be sorted: ");

   scanf ("%d", &n);

   printf ("Enter items: ");

   for (i = 0; i < n; i++){

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

   }

   radix_sort (a, n);

   printf ("Sorted items : ");

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

      printf ("%d ", a[i]);

  // printf ("");

   return 0;

}

DYNAMIC LCS

 #include<iostream>

using namespace std;

int lcs(string pattern_1, string pattern_2) {

  int m = pattern_1.size();

  int n = pattern_2.size();

  // dp will store solutions as the iteration goes on

  int dp[n + 1][m + 1];

  for (int i = 0; i < n + 1; i++) {

    for (int j = 0; j < m + 1; j++) {

      if (i == 0 || j == 0) {

        dp[i][j] = 0;

      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {

        dp[i][j] = dp[i - 1][j - 1] + 1;

      } else {

        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

      }

    }

  }

  return dp[n][m];

}

int main() {

  string pattern_1 = "RGBGARGA";

  string pattern_2 = "BGRARG";

  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;

}

DFS IN C++

 #include<iostream>

using namespace std;

#include<conio.h>

#include<stdlib.h>

int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

int main()

{

    int m;

    cout <<"Enter no of vertices:";

    cin >> n;

    cout <<"Enter no of edges:";

    cin >> m;

    cout <<"\nEDGES \n";

    for(k=1; k<=m; k++)

    {

        cin >>i>>j;

        cost[i][j]=1;

    }

    cout <<"Enter initial vertex to traverse from:";

    cin >>v;

    cout <<"DFS ORDER OF VISITED VERTICES:";

    cout << v <<" ";

    visited[v]=1;

    k=1;

    while(k<n)

    {

        for(j=n; j>=1; j--)

            if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

            {

                visit[j]=1;

                stk[top]=j;

                top++;

            }

        v=stk[--top];

        cout<<v << " ";

        k++;

        visit[v]=0;

        visited[v]=1;

    }

    return 0;

}

BFS IN C

 #include <stdio.h>

 

int n, i, j, visited[10], queue[10], front = -1, rear = -1;

int adj[10][10];

 

void bfs(int v)

{

    for (i = 1; i <= n; i++)

        if (adj[v][i] && !visited[i])

            queue[++rear] = i;

    if (front <= rear)

    {

        visited[queue[front]] = 1;

        bfs(queue[front++]);

    }

}

 

void main()

{

    int v;

    printf("Enter the number of vertices: ");

    scanf("%d", &n);

    for (i = 1; i <= n; i++)

    {

        queue[i] = 0;

        visited[i] = 0;

    }

    printf("Enter graph data in matrix form:    \n");

    for (i = 1; i <= n; i++)

        for (j = 1; j <= n; j++)

            scanf("%d", &adj[i][j]);

    printf("Enter the starting vertex: ");

    scanf("%d", &v);

    bfs(v);

    printf("The node which are reachable are:    \n");

    for (i = 1; i <= n; i++)

        if (visited[i])

            printf("%d\t", i);

        else

            printf("BFS is not possible. Not all nodes are reachable");

    

}

KRUSKAL

 #include <conio.h>

#include <stdlib.h>

#include <stdio.h>

    int i, j, k, a, b, u, v, n, ne = 1;

    int min, mincost = 0, cost[9][9], parent[9];

    int find(int);

    int uni(int, int);

    void main() {

      printf("\n\tImplementation of Kruskal's Algorithm\n");

      printf("\nEnter the no. of vertices:");

      scanf("%d",&n);

      printf("\nEnter the cost adjacency matrix:\n");

      for (i = 1; i<= n; i++) {

        for (j = 1; j <= n; j++) {

          scanf("%d", &cost[i][j]);

          if (cost[i][j] == 0)

            cost[i][j] = 999;

        }

      }

      printf("The edges of Minimum Cost Spanning Tree are\n");

      while (ne < n) {

        for (i = 1, min = 999; i <= n; i++) {

          for (j = 1; j <= n; j++) {

            if (cost[i][j] <min) {

              min = cost[i][j];

              a = u = i;

              b = v = j;

            }

          }

        }

        u = find(u);

        v = find(v);

        if (uni(u, v)) {

          printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);

          mincost += min;

        }

        cost[a][b] = cost[b][a] = 999;

      }

      printf("\n\tMinimum cost = %d\n", mincost);

      getch();

    }

    int find(int i) {

      while (parent[i])

        i = parent[i];

      return i;

    }

    int uni(int i, int j) {

      if (i != j) {

        parent[j] = i;

        return 1;

      }

      return 0;

    }

prims algorithm

 #include<iostream>

using namespace std;

// Number of vertices in the graph  

const int V=6;

// Function to find the vertex with minimum key value 

int min_Key(int key[], bool visited[])  

{ 

    int min = 999, min_index;  // 999 represents an Infinite value

    for (int v = 0; v < V; v++) { 

        if (visited[v] == false && key[v] < min) { 

        // vertex should not be visited

            min = key[v];

min_index = v;  

        }

    }    

    return min_index;  

}  

// Function to print the final MST stored in parent[]  

void print_MST(int parent[], int cost[V][V])  

{  

    int minCost=0;

cout<<"Edge \tWeight\n";  

    for (int i = 1; i< V; i++) {

cout<<parent[i]<<" - "<<i<<" \t"<<cost[i][parent[i]]<<" \n";  

minCost+=cost[i][parent[i]];

    }

cout<<"Total cost is"<<minCost;

}  

// Function to find the MST using adjacency cost matrix representation  

void find_MST(int cost[V][V])  

{  

    int parent[V], key[V];

    bool visited[V];

    // Initialize all the arrays 

    for (int i = 0; i< V; i++) { 

        key[i] = 999;    // 99 represents an Infinite value

        visited[i] = false;

        parent[i]=-1;

    }    

    key[0] = 0;  // Include first vertex in MST by setting its key vaue to 0.  

    parent[0] = -1; // First node is always root of MST  

    // The MST will have maximum V-1 vertices  

    for (int x = 0; x < V - 1; x++) 

    {  

        // Finding the minimum key vertex from the 

        //set of vertices not yet included in MST  

        int u = min_Key(key, visited);  

        visited[u] = true;  // Add the minimum key vertex to the MST  

        // Update key and parent arrays

        for (int v = 0; v < V; v++)  

        {

            // cost[u][v] is non zero only for adjacent vertices of u  

            // visited[v] is false for vertices not yet included in MST  

            // key[] gets updated only if cost[u][v] is smaller than key[v]  

            if (cost[u][v]!=0 && visited[v] == false && cost[u][v] < key[v])

            {  

                parent[v] = u;

                key[v] = cost[u][v];  

            }        

        }

    }

    // print the final MST  

print_MST(parent, cost);  

}  

// main function

int main()  

{  

    int cost[V][V];

cout<<"Enter the vertices for a graph with 6 vetices";

    for (int i=0;i<V;i++)

    {

        for(int j=0;j<V;j++)

        {

cin>>cost[i][j];

        }

    }

find_MST(cost);  

    return 0;  

}  

Twin Prime Number in a range

 

import java.io.*; 

import java.util.*;

 

public class Main

{static boolean checkPrimeNumber(int number) 

    { 

        int i; 

        int m = 0; 

        int flag = 0;       

        m = number/2;       

        if(number == 0 || number == 1){   

            return false;       

        }else{   

            for(i = 2; i <= m ;i++){       

                if(number%i == 0){       

                    flag=1;       

                    return false;       

                }       

            }       

            if(flag == 0)   

            {  

                return true; 

            }   

        } 

        return false; 

    }     

    static boolean checkTwinPrimeNumber(int number1, int number2) 

    { 

        if(checkPrimeNumber(number1) && checkPrimeNumber(number2) && Math.abs(number1 - number2) == 2) 

            return true; 

        else 

            return false; 

    } 

  

    public static void main(String[] args) 

    { 

        int startRange, endRange; 

         

        Scanner sc=new Scanner(System.in);          

      

        System.out.println("Enter start value");            

        startRange = sc.nextInt();            

                System.out.println("Enter last value");            

        endRange = sc.nextInt(); 

         

        System.out.println("The pairs of twin primes between" + startRange + " and " + endRange + "are:"); 

         

        for (int i = startRange; i < endRange; i++) { 

            if (checkTwinPrimeNumber(i, (i + 2))){ 

                System.out.printf("(%d, %d)\n", i, i + 2); 

            } 

        } 

    } 

} 

Neon Number

 import java.util.Scanner;  

import java.lang.Math;  

public class Main

{

    

public static void main(String args[])     

{     

int sum = 0, n;      

Scanner sc = new Scanner(System.in);  

System.out.print("Enter the number to check: ");  

n = sc.nextInt();  

int square = n * n; 

while(square != 0)  

{  

 

int digit = square % 10; 

sum = sum + digit;

square = square / 10;  

}  

if(n == sum)  

System.out.println(n + " is a Neon Number.");  

else  

System.out.println(n + " is not a Neon Number.");  

}  

}  

DecimalToBinary

 

import java.util.Scanner; 

import java.lang.Math; 

public class Main

{

    public static int convertDecimalToBinary(int dec) {

   

      int rem,b1=0;

      int rev = 1;

      while (dec > 0) {

         rem = dec % 2;

         dec = dec / 2;

         b1 = b1 + rem * rev;

         rev = rev * 10;

      }

    return b1;

  }

public static void main(String args[])    

{    

 

 

    Scanner in = new Scanner(System.in); 

System.out.print("Enter a number : "); 

 

int num = in.nextInt(); 

 

    int decimal = convertDecimalToBinary(num);

    System.out.println("Binary to Decimal");

    System.out.println(num + " = " + decimal);

  }

 

 

}