Design and Analysis of Algorithms

ALGORITHM

  BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

  Step 1: [INITIALIZE] SET BEG = lower_bound END = upper_bound, POS = - 1

  Step 2: Repeat Steps 3 and 4 while BEG <=END

  Step 3: SET MID = (BEG + END)/2

  Step 4: IF A[MID] = VAL
  SET POS = MID
  PRINT POS

  Go to Step 6

  ELSE IF A[MID] > VAL
  SET END = MID - 1
  ELSE
  SET BEG = MID + 1
    [END OF IF]
    [END OF LOOP]

  Step 5: IF POS = -1
  PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
  [END OF IF]

  Step 6: EXIT
          

CODE

#include<stdio.h>
int binarysearch(int arr[],int n,int key)
{
    int low=0,high=n-1,mid,flag=0,c=0;
    while(low<=high)
    {
        mid=(high+low)/2;
        c++;
        if(key==arr[mid])
        {
        flag=1;
        break;
        }
        else if(key< arr[mid])
        high=mid-1;
        else
        low=mid+1;
    }
    if(flag==1)
    printf("Key is found at %d\n",mid);
    else
    printf("Key is not found");

    printf("No.of iterations %d",c);
}
void main()
{
    int arr[10],i,n,key;
    printf("Enter no of elements: ");
    scanf("%d",&n);
    printf("Enter the array elements: ");
    for(i=0;i< n;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("Enter the key: ");
    scanf("%d",&key);
    binarysearch(arr,n,key);
}
                    
                            
  

TIME COMPLEXITY

Best case time complexity = O(1)
Average case time complexity = O(logn)
Worst case time complexity = O(logn)

EXPLANATION

OUTPUT

ALGORITHM

  MergeSort(arr[], l,  r)
    If r > l
       Find the middle point to divide the array into two halves:  
              middle m = l+ (r-l)/2

       Call mergeSort for first half:   
              Call mergeSort(arr, l, m)

       Call mergeSort for second half:
              Call mergeSort(arr, m+1, r)

       Merge the two halves sorted in step 2 and 3:
              Call merge(arr, l, m, r)
          

CODE

#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

int main()
{
    int a[30],n,i;
    printf("Enter no of elements:");
    scanf("%d",&n);
    printf("Enter array elements:");

    for(i=0;i< n;i++)
        scanf("%d",&a[i]);

    mergesort(a,0,n-1);

    printf("\nSorted array is :");
    for(i=0;i< n;i++)
        printf("%d ",a[i]);

    return 0;
}

void mergesort(int a[],int i,int j)
{
    int mid;

    if(i< j)
    {
        mid=(i+j)/2;
        mergesort(a,i,mid);		//left recursion
        mergesort(a,mid+1,j);	//right recursion
        merge(a,i,mid,mid+1,j);	//merging of two sorted sub-arrays
    }
}

void merge(int a[],int i1,int j1,int i2,int j2)
{
    int temp[50];	//array used for merging
    int i,j,k;
    i=i1;	//beginning of the first list
    j=i2;	//beginning of the second list
    k=0;

    while(i<=j1 && j<=j2)	//while elements in both lists
    {
        if(a[i]< a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }

    while(i<=j1)	//copy remaining elements of the first list
        temp[k++]=a[i++];

    while(j<=j2)	//copy remaining elements of the second list
        temp[k++]=a[j++];

    //Transfer elements from temp[] back to a[]
    for(i=i1,j=0;i<=j2;i++,j++)
        a[i]=temp[j];
}                      
  

TIME COMPLEXITY

  Worst Case Complexity = O(n logn)
  Best Case Complexity = O(n logn)
  Average Case Complexity = O(n logn)

EXPLANATION

OUTPUT

ALGORITHM

  /* low  --> Starting index,  high  --> Ending index */
  quickSort(arr[], low, high)
  {
      if (low < high)
      {
          /* pi is partitioning index, arr[pi] is now
            at right place */
          pi = partition(arr, low, high);

          quickSort(arr, low, pi - 1);  // Before pi
          quickSort(arr, pi + 1, high); // After pi
      }
  }
          

CODE

#include<stdio.h>
void quicksort(int number[25],int first,int last){
    int i, j, pivot, temp;

    if(first< last){
      pivot=first;
      i=first;
      j=last;

      while(i< j){
          while(number[i]<=number[pivot]&&i< last)
            i++;
          while(number[j]>number[pivot])
            j--;
          if(i< j){
            temp=number[i];
            number[i]=number[j];
            number[j]=temp;
          }
      }

      temp=number[pivot];
      number[pivot]=number[j];
      number[j]=temp;
      quicksort(number,first,j-1);
      quicksort(number,j+1,last);

    }
}

int main(){
    int i, count, number[25];

    printf("How many elements are u going to enter?: ");
    scanf("%d",&count);

    printf("Enter %d elements: ", count);
    for(i=0;i< count;i++)
      scanf("%d",&number[i]);

    quicksort(number,0,count-1);

    printf("Order of Sorted elements: ");
    for(i=0;i< count;i++)
      printf(" %d",number[i]);

    return 0;
}
  

TIME COMPLEXITY

  Worst Case Complexity = O(n^2)
  Best Case Complexity = O(n logn)
  Average Case Complexity = O(n logn)

EXPLANATION

OUTPUT

ALGORITHM

            
Naive Method Algorithm
            

    Algorithm: Max-Min-Element (numbers[]) 
    max := numbers[1] 
    min := numbers[1] 

    for i = 2 to n do 
      if numbers[i] > max then  
          max := numbers[i] 
      if numbers[i] < min then  
          min := numbers[i] 
    return (max, min) 
            

            
Divide & Conquer Method Algorithm
            

    Algorithm: Max - Min(x, y) 
    if y – x ≤ 1 then  
      return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
    else 
      (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
      (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
    return (max(max1, max2), min(min1, min2))
          

CODE

          
Naive Method

  #include<stdio.h&ht;
    int maxmin(int a[],int n)
    {
      int min,max,i;
      min=max=a[0];
        for(i=1; i< n; i++)
        {
    
            if(min>a[i])
          min=a[i];
          if(max< a[i])
            max=a[i];
        }
    
        printf("MINIMUM OF THE ARRAY  = %d",min);
        printf("\n MAXIMUM OF THE ARRAY = %d",max);
    
    }
    int main()
    {
        int a[100],i,n,sum;
    
        printf("ENTER THE SIZE OF THE ARRAY : ");
        scanf("%d", &n);
    
        printf("ENTER THE ELEMENTS  : ");
        for(i=0; i< n; i++)
        {
            scanf("%d",&a[i]);
        }
        maxmin(a,n);
    
    }
           
  

  
Divide and Conquer Method

  #include<stdio.h>
    int max, min,c=0;
    int a[100];
    void maxmin(int i, int j)
    {
     int max1, min1, mid;
     if(i==j)
     {
    
      max = min = a[i];
     }
     else
     {
      if(i == j-1)
      {
          c++;
       if(a[i] < [j])
       {
        max = a[j];
        min = a[i];
       }
       else
       {
        max = a[i];
        min = a[j];
       }
      }
      else
      {
       mid = (i+j)/2;
       maxmin(i, mid);
       max1 = max; min1 = min;
       maxmin(mid+1, j);
       if(max < max1)
        max = max1;
       if(min > min1)
        min = min1;
      }
     }
    }
    int main ()
    {
     int i, num;
     printf ("\nEnter the total number of numbers : ");
     scanf ("%d",&num);
     printf ("Enter the numbers : \n");
     for (i=1;i<=num;i++)
        scanf ("%d",&a[i]);
    max = a[0];
    min = a[0];
     maxmin(1, num);
     printf ("Minimum element in an array : %d\n", min);
     printf ("Maximum element in an array : %d\n", max);
     printf("No. of comparison = %d",c);
     return 0;
    }
    
   

TIME COMPLEXITY

 Time Complexity = O(n)

EXPLANATION

OUTPUT

ALGORITHM

  Take the sequence of matrices and separate it into two subsequences.

  Find the minimum cost of multiplying out each subsequence.

  Add these costs together, and add in the cost of multiplying the two result matrices.

  Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.
          

CODE

#include<limits.h>
#include<stdio.h>
int MatrixChainOrder(int p[], int n)
{
    int m[n][n];
    int i, j, k, L, q;
    // cost is zero when multiplying one matrix. the diagonal elements should be zero.
    for (i = 1; i < n; i++)
        m[i][i] = 0;
    // L is chain length. how many matrices is going to be multiplied
    for (L = 2; L < n; L++) {
        for (i = 1; i < n - L + 1; i++)
        {
            j = i + L - 1;
            m[i][j] = INT_MAX;
            for (k = i; k <= j - 1; k++)
            {
                // q = cost/scalar multiplications
                q = m[i][k] + m[k + 1][j]
                    + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])

                    m[i][j] = q;
            }
        }
    }
    return m[1][n - 1];
}
int main()
{
    int x,size;
    printf("enter how many elements in the array = ");
    scanf("%d",&size);
    int arr[size];
    printf("enter the elements = \n");
    for(x=0;x< size;x++)
        scanf("%d",&arr[x]);

    printf("Minimum number of multiplications is %d ",
        MatrixChainOrder(arr, size));
    return 0;
}                        
  

TIME COMPLEXITY

 Time Complexity = O(n^3)

EXPLANATION

OUTPUT

ALGORITHM

  let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
  for each edge (u, v) do
      dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
  for each vertex v do
      dist[v][v] ← 0
  for k from 1 to |V|
      for i from 1 to |V|
          for j from 1 to |V|
              if dist[i][j] > dist[i][k] + dist[k][j] 
                  dist[i][j] ← dist[i][k] + dist[k][j]
              end if
          

CODE

#include<stdio.h>

int min(int,int);

void floyds(int p[10][10],int n)
{
  int i,j,k;
  for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i==j)
      p[i][j]=0;
    else
      p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}

int min(int a,int b)
{
  if(a< b)
  return(a);
  else
  return(b);
}

void main()
{
  int p[10][10],w,n,e,u,v,i,j;;
  printf("Enter the number of vertices: ");
  scanf("%d",&n);
  printf("\nEnter the number of edges: ");
  scanf("%d",&e);
  
  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++)
    p[i][j]=999;
  }
  for(i=1;i<=e;i++)
  {
  printf("\nEnter the end vertices of edge%d with its weight \n",i);
  scanf("%d%d%d",&u,&v,&w);
  p[u][v]=w;
  }
  printf("\n Matrix of input data:\n");
  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++)
    printf("%d \t",p[i][j]);
  printf("\n");
  }
  floyds(p,n);
  printf("\n Transitive closure:\n");
  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++)
    printf("%d \t",p[i][j]);
  printf("\n");
  }
  printf("\n The shortest paths are:\n");
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
    if(i!=j)
    printf("\n <%d,%d>=%d",i,j,p[i][j]);
  }
}          
  

TIME COMPLEXITY

 Time Complexity = O(V^3), where V is the number of vertex.

EXPLANATION

OUTPUT

ALGORITHM

  Algorithm: Traveling-Salesman-Problem 
  C ({1}, 1) = 0 
  for s = 2 to n do 
    for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
        C (S, 1) = ∞ 
    for all j Є S and j ≠ 1 
        C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
  Return minj C ({1, 2, 3, …, n}, j) + d(j, i) 
          

CODE

#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;
  
void takeInput()
{
  int i,j;
  
  printf("Enter the number of nodes: ");
  scanf("%d",&n);
  
  printf("\nEnter the Cost Matrix\n");
  
  for(i=0;i < n;i++)
  {
    for( j=0;j < n;j++)
      scanf("%d",&ary[i][j]);
  
    completed[i]=0;
  }
  
  printf("\n\nThe cost list is:");
  
  for( i=0;i < n;i++)
  {
    printf("\n");
  
    for(j=0;j < n;j++)
      printf("\t%d",ary[i][j]);
  }
}
  
void mincost(int city)
{
  int i,ncity;
  
  completed[city]=1;
  
  printf("%d--->",city+1);
  ncity=least(city);
  
  if(ncity==999)
  {
    ncity=0;
    printf("%d",ncity+1);
    cost+=ary[city][ncity];
  
    return;
  }
  
  mincost(ncity);
}
  
int least(int c)
{
  int i,nc=999;
  int min=999,kmin;
  
  for(i=0;i < n;i++)
  {
    if((ary[c][i]!=0)&&(completed[i]==0))
      if(ary[c][i]+ary[i][c] < min)
      {
        min=ary[i][0]+ary[c][i];
        kmin=ary[c][i];
        nc=i;
      }
  }
  
  if(min!=999)
    cost+=kmin;
  
  return nc;
}
  
int main()
{
  takeInput();
  
  printf("\n\nThe Path is:\n");
  mincost(0); //passing 0 because starting vertex
  
  printf("\n\nMinimum cost is %d\n ",cost);
  
  return 0;
}
 

TIME COMPLEXITY

 Time Complexity = O(n^2*2^n)

EXPLANATION

OUTPUT

ALGORITHM

  Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
  for i = 1 to n 
    do x[i] = 0 
  weight = 0 
  for i = 1 to n 
    if weight + w[i] ≤ W then  
        x[i] = 1 
        weight = weight + w[i] 
    else 
        x[i] = (W - weight) / w[i] 
        weight = W 
        break 
  return x
          

CODE

  #include <stdio.h>

    void main()
    {
    int capacity, no_items, cur_weight, item;
    int used[10];
    float total_profit;
    int i;
    int weight[10];
    int value[10];
    
    printf("Enter the capacity of knapsack:\n");
    scanf("%d", &capacity);
    
    printf("Enter the number of items:\n");
    scanf("%d", &no_items);
    
    printf("Enter the weight and value of %d item:\n", no_items);
    for (i = 0; i < no_items; i++)
    {
    printf("Weight[%d]:\t", i);
    scanf("%d", &weight[i]);
    printf("Value[%d]:\t", i);
    scanf("%d", &value[i]);
    }
    
    for (i = 0; i < no_items; ++i)
    used[i] = 0;
    
    cur_weight = capacity;
    while (cur_weight > 0)
    {
    item = -1;
    for (i = 0; i < no_items; ++i)
    if ((used[i] == 0) &&
    ((item == -1) || ((float) value[i] / weight[i] > (float) value[item] / weight[item])))
    item = i;
    
    used[item] = 1;
    cur_weight -= weight[item];
    total_profit += value[item];
    if (cur_weight >= 0)
    printf("Added object %d (%d Rs.,%dKg) completely in the bag.Space left: %d.\n", item + 1,value[item],weight[item],cur_weight);
    else
    {
    int item_percent = (int) ((1 + (float) cur_weight / weight[item]) * 100);
    printf("Added %d%% (%d Rs., %dKg) of object %d in the bag.\n", item_percent, value[item], weight[item], item + 1);
    total_profit -= value[item];
    total_profit += (1 + (float)cur_weight / weight[item]) * value[item];
    }
    }
    printf("Filled the bag with objects worth %.2f Rs.\n", total_profit);
    }
              
            

TIME COMPLEXITY

 Time Complexity = O(n logn)

EXPLANATION

OUTPUT

ALGORITHM

  Begin

  Create the edge list of given graph, with their weights.

  Sort the edge list according to their weights in ascending order.

  Draw all the nodes to create skeleton for spanning tree.

  Pick up the edge at the top of the edge list (i.e. edge with minimum weight).

  Remove this edge from the edge list.

  Connect the vertices in the skeleton with given edge. If by connecting the vertices, a cycle is created in the skeleton, then discard this edge.

  Repeat steps 5 to 7, until n-1 edges are added or list of edges is over.

  Return 
          

CODE

#include<stdio.h>
#include<conio.h>
<stdlib.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()
{
  clrscr();
  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;
}

TIME COMPLEXITY

Time Complexity = O(E logE),  where E is the number of edges in the graph

EXPLANATION

OUTPUT

ALGORITHM

Step 1: Select a starting vertex

Step 2: Repeat Steps 3 and 4 until there are fringe vertices

Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight

Step 4: Add the selected edge and the vertex to the minimum spanning tree T

[END OF LOOP]

Step 5: EXIT
          

CODE

#include <stdio.h>
#include<limits.h>
int parent[9];
int unique(int i,int j)
{
  if(i!=j)
  {
    parent[j]=i;
    return 1;
  }
  return 0;
}
int find_parent(int i)
{
  while(parent[i])
  {
    i=parent[i];
  }
  return i;
}
int main()
{
  int i,j,k,a,b,u,v,ne=1,n;
  printf("\nEnter the no. of vertices:");
  scanf("%d",&n);
  int min,mincost=0,cost[n][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]);
    }
  }
  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_parent(u);
    v=find_parent(v);
    if(unique(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);
}

TIME COMPLEXITY

Time Complexity = O(E logV), where E and V is the number of edges and vertices in the graph.

EXPLANATION

OUTPUT

ALGORITHM

        function dijkstra(G, S)
  for each vertex V in G
      distance[V] <- infinite
      previous[V] <- NULL
      If V != S, add V to Priority Queue Q
  distance[S] <- 0

  while Q IS NOT EMPTY
      U <- Extract MIN from Q
      for each unvisited neighbour V of U
          tempDistance <- distance[U] + edge_weight(U, V)
          if tempDistance < distance[V]
              distance[V] <- tempDistance
              previous[V] <- U
  return distance[], previous[]

CODE

#include <stdio.h>
#define INFINITY 9999
#define MAX 10

void Dijkstra(int Graph[MAX][MAX], int n, int start);

void Dijkstra(int Graph[MAX][MAX], int n, int start) {
  int cost[MAX][MAX], distance[MAX], pred[MAX];
  int visited[MAX], count, mindistance, nextnode, i, j;

  
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (Graph[i][j] == 0)
        cost[i][j] = INFINITY;
      else
        cost[i][j] = Graph[i][j];

  for (i = 0; i < n; i++) {
    distance[i] = cost[start][i];
    pred[i] = start;
    visited[i] = 0;
  }

  distance[start] = 0;
  visited[start] = 1;
  count = 1;

  while (count < n - 1) {
    mindistance = INFINITY;

    for (i = 0; i < n; i++)
      if (distance[i] < mindistance && !visited[i]) {
        mindistance = distance[i];
        nextnode = i;
      }

    visited[nextnode] = 1;
    for (i = 0; i < n; i++)
      if (!visited[i])
        if (mindistance + cost[nextnode][i] < distance[i]) {
          distance[i] = mindistance + cost[nextnode][i];
          pred[i] = nextnode;
        }
    count++;
  }

  
  for (i = 0; i < n; i++)
    if (i != start) {
      printf("\nDistance from source to %d: %d", i, distance[i]);
    }
}
int main() {
  int Graph[MAX][MAX], i, j, n, u;
  printf("The number of elements\n");
  scanf("%d",&n);
  printf("Enter the weights of matrix elements");
  for (i=0;i< n;i++){
    for(j=0;j< n;j++){
      scanf("%d",&Graph[i][j]);
    }
  }
  u = 0;
  Dijkstra(Graph, n, u);

  return 0;
}

Time Complexity

The Time Complexity = O(E logV), where E,V are the number of edges, and vertices.

EXPLANATION

OUTPUT

ALGORITHM

  Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
  D(0) := J(0) := 0 
  k := 1 
  J(1) := 1   // means first job is selected 
  for i = 2 … n do 
    r := k 
    while D(J(r)) > D(i) and D(J(r)) ≠ r do 
        r := r – 1 
    if D(J(r)) ≤ D(i) and D(i) > r then 
        for l = k … r + 1 by -1 do 
          J(l + 1) := J(l) 
          J(r + 1) := i 
          k := k + 1 
        

CODE

#include <stdio.h>

#define MAX 100

typedef struct Job {
  char id[5];
  int deadline;
  int profit;
} Job;

void jobSequencingWithDeadline(Job jobs[], int n);

int minValue(int x, int y) {
  if(x < y) return x;
  return y;
}

int main(void) {
  //variables
  int i, j;

  //jobs with deadline and profit
  Job jobs[5] = {
    {"j1", 2,  60},
    {"j2", 1, 100},
    {"j3", 3,  20},
    {"j4", 2,  40},
    {"j5", 1,  20},
  };

  //temp
  Job temp;

  //number of jobs
  int n = 5;

  //sort the jobs profit wise in descending order
  for(i = 1; i < n; i++) {
    for(j = 0; j < n - i; j++) {
      if(jobs[j+1].profit > jobs[j].profit) {
        temp = jobs[j+1];
        jobs[j+1] = jobs[j];
        jobs[j] = temp;
      }
    }
  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");
  for(i = 0; i < n; i++) {
    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);
  }

  jobSequencingWithDeadline(jobs, n);

  return 0;
}

void jobSequencingWithDeadline(Job jobs[], int n) {
  //variables
  int i, j, k, maxprofit;

  //free time slots
  int timeslot[MAX];

  //filled time slots
  int filledTimeSlot = 0;

  //find max deadline value
  int dmax = 0;
  for(i = 0; i < n; i++) {
    if(jobs[i].deadline > dmax) {
      dmax = jobs[i].deadline;
    }
  }

  //free time slots initially set to -1 [-1 denotes EMPTY]
  for(i = 1; i <= dmax; i++) {
    timeslot[i] = -1;
  }

  printf("dmax: %d\n", dmax);

  for(i = 1; i <= n; i++) {
    k = minValue(dmax, jobs[i - 1].deadline);
    while(k >= 1) {
      if(timeslot[k] == -1) {
        timeslot[k] = i-1;
        filledTimeSlot++;
        break;
      }
      k--;
    }

    //if all time slots are filled then stop
    if(filledTimeSlot == dmax) {
      break;
    }
  }

  //required jobs
  printf("\nRequired Jobs: ");
  for(i = 1; i <= dmax; i++) {
    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax) {
      printf(" --> ");
    }
  }

  //required profit
  maxprofit = 0;
  for(i = 1; i <= dmax; i++) {
    maxprofit += jobs[timeslot[i]].profit;
  }
  printf("\nMax Profit: %d\n", maxprofit);
} 

TIME COMPLEXITY

Time Complexity = O(n^2)

EXPLANATION

OUTPUT

ALGORITHM

          
Cost Function

          c(x) = f(x) + h(x) where, 

          f(x) is the length of the path from root to x 
                (the number of moves so far) and

          h(x) is the number of non-blank tiles not in 
                their goal position (the number of mis-
                -placed tiles). There are at least h(x) 
                moves to transform state x to a goal state  
                
        
Algorithm

/* Algorithm LCSearch uses c(x) to find an answer node
  * LCSearch uses Least() and Add() to maintain the list 
  of live nodes
  * Least() finds a live node with least c(x), deletes
  it from the list and returns it
  * Add(x) adds x to the list of live nodes
  * Implement list of live nodes as a min-heap */

  struct list_node
  {
  list_node *next;

  // Helps in tracing path when answer is found
  list_node *parent; 
  float cost;
  } 

  algorithm LCSearch(list_node *t)
  {
  // Search t for an answer node
  // Input: Root node of tree t
  // Output: Path from answer node to root
  if (*t is an answer node)
  {
      print(*t);
      return;
  }

  E = t; // E-node

  Initialize the list of live nodes to be empty;
  while (true)
  {
    for each child x of E
    {
        if x is an answer node
        {
            print the path from x to t;
            return;
        }
        Add (x); // Add x to list of live nodes;
        x->parent = E; // Pointer for path to root
    }

    if there are no more live nodes
    {
        print ("No answer node");
        return;
    }
      
    // Find a live node with least estimated cost
    E = Least(); 

    // The found node is deleted from the list of 
    // live nodes
  }
  }
        

CODE

#include<stdio.h>
int m=0,n=4;
int cal(int temp[10][10],int t[10][10])
{
  int i,j,m=0;
  for(i=0;i < n;i++)
    for(j=0;j < n;j++)
    {
      if(temp[i][j]!=t[i][j])
      m++;
    }
  return m;
}
int check(int a[10][10],int t[10][10])
{
  int i,j,f=1;
  for(i=0;i < n;i++)
    for(j=0;j < n;j++)
      if(a[i][j]!=t[i][j])
        f=0;
  return f;
}
void main()
{
  int p,i,j,n=4,a[10][10],t[10][10],temp[10][10],r[10][10];
  int m=0,x=0,y=0,d=9999,dmin=0,l=0;

  printf("\nEnter the matrix to be solved,space with zero :\n");
  for(i=0;i < n;i++)
    for(j=0;j < n;j++)
      scanf("%d",&a[i][j]);

  printf("\nEnter the target matrix,space with zero :\n");
  for(i=0;i < n;i++)
    for(j=0;j < n;j++)
      scanf("%d",&t[i][j]);

  printf("\nEntered Matrix is :\n");
  for(i=0;i < n;i++)
  {
    for(j=0;j < n;j++)
      printf("%d\t",a[i][j]);
    printf("\n");
  }

  printf("\nTarget Matrix is :\n");
  for(i=0;i < n;i++)
  {
    for(j=0;j < n;j++)
      printf("%d\t",t[i][j]);
    printf("\n");
  }

  while(!(check(a,t)))
  {
    l++;
    d=9999;
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
      {
        if(a[i][j]==0)
        {
          x=i;
          y=j;
        }
      }

    //To move upwards
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
        temp[i][j]=a[i][j];

    if(x!=0)
    {
      p=temp[x][y];
      temp[x][y]=temp[x-1][y];
      temp[x-1][y]=p;
    }
    m=cal(temp,t);
    dmin=l+m;  // c(x) = f(x) + g(x)
    if(dmin < d)
    {
      d=dmin;
      for(i=0;i < n;i++)
        for(j=0;j < n;j++)
          r[i][j]=temp[i][j];
    }

    //To move downwards
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
        temp[i][j]=a[i][j];
    if(x!=n-1)
    {
      p=temp[x][y];
      temp[x][y]=temp[x+1][y];
      temp[x+1][y]=p;
    }
    m=cal(temp,t);
    dmin=l+m;
    if(dmin < d)
    {
      d=dmin;
      for(i=0;i < n;i++)
        for(j=0;j < n;j++)
          r[i][j]=temp[i][j];
    }

    //To move right side
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
        temp[i][j]=a[i][j];
    if(y!=n-1)
    {
      p=temp[x][y];
      temp[x][y]=temp[x][y+1];
      temp[x][y+1]=p;
    }
    m=cal(temp,t);
    dmin=l+m;
    if(dmin < d)
    {
      d=dmin;
      for(i=0;i < n;i++)
        for(j=0;j < n;j++)
          r[i][j]=temp[i][j];
    }

    //To move left
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
        temp[i][j]=a[i][j];
    if(y!=0)
    {
      p=temp[x][y];
      temp[x][y]=temp[x][y-1];
      temp[x][y-1]=p;
    }
    m=cal(temp,t);
    dmin=l+m;
    if(dmin < d)
    {
      d=dmin;
      for(i=0;i < n;i++)
        for(j=0;j < n;j++)
          r[i][j]=temp[i][j];
    }

    printf("\nCalculated Intermediate Matrix Value :\n");
    for(i=0;i < n;i++)
    {
      for(j=0;j < n;j++)
        printf("%d\t",r[i][j]);
      printf("\n");
    }
    for(i=0;i < n;i++)
      for(j=0;j < n;j++)
      {
        a[i][j]=r[i][j];
        temp[i][j]=0;
      }
    printf("Minimum cost : %d\n",d);
  }

}

TIME COMPLEXITY

Time Complexity = O(n^2)

EXPLANATION

OUTPUT

ALGORITHM

1) Start in the leftmost column 2) If all queens are placed return true 3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in [row, column] leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows. 4) If all rows have been tried and nothing worked, return false to trigger backtracking.

CODE

#include<stdio.h>
#include<math.h>
int a[30],count=0;
int killing(int pos) {
  int i;
  for (i=1;i< pos;i++) { //from 1st row to the (current row -1) to check
    if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
        return 0;
  }
  return 1;
}
void print_sol(int n) {
  int i,j;
  count++;
  printf("\n\nSolution number = %d:\n",count);
  printf("\n");
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) {
      if(a[i]==j)// if the column number == the current column
          printf("Queen\t"); else
          printf("-\t");
    }
    printf("\n");
  }
}
void N_queen(int n) {
  int k=1; // 1st queen
  a[k]=0;  // column for queens
  while(k!=0) {
    a[k]=a[k]+1; // 1st queen at the first place
    while((a[k]<=n) && !killing(k))
        a[k]++;
    if(a[k]<=n) {
      if(k==n)
          print_sol(n); else {
        k++;
        a[k]=0;
      }
    } else
        k--;
  }
}
void main() {
  int i,n;
  printf("Enter the number of Queens\n");
  scanf("%d",&n);
  N_queen(n);
  printf("\nTotal solutions=%d",count);
}                         
  

TIME COMPLEXITY

Time Complexity = O(n^n), where n is the width of the board.

EXPLANATION

OUTPUT

ALGORITHM

  The steps required to color a graph G with n number of vertices are as follows −

  Step 1 − Arrange the vertices of the graph in some order.

  Step 2 − Choose the first vertex and color it with the first color.

  Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it.If all the adjacent vertices are colored with this color,  
assign a new color to it. Repeat this step until all the vertices are colored.
  

CODE

#include<stdio.h>
void gc()
{
int n;
  printf("Please enter the number of nodes:");
  scanf("%d",&n);
  printf("Please enter the adjacency matrix:\n");
for(int i=0;i< n;i++)
printf("%3d",i+1);
printf("\n");
int a[n][n];
for(int i=0;i< n;i++)        //The adjacency matrix stores graph information 
{
  printf("%-2d",i+1);
  for(int j=0;j< n;j++)
  {
    scanf("%d",&a[i][j]);
  }
getchar();
}
int m;
printf("Please enter the number of colors:");
scanf("%d",&m);
int result[n];                   //Store the coloring of each vertex 
for(int i=0;i< n;i++)
result[i]=0;
result[0]=1;               
int k=1;
while(k>-1)
{
  result[k]++;
  while(result[k]<=m)
  {
    int flag=0;
    for(int j=0;j< k;j++)         //Traverse the colored vertices and determine whether the constraints are met 
    {
      if(a[k][j]==1&&result[k]==result[j])
      flag=1;
  }
  if(flag==0)
  break;
  else
  result[k]++;
  }
    if(result[k]<=m)
    {
      if(k==n-1)                   //The last vertex is successfully colored and jumps out of the loop 
      break;
      else 
      k++;                         //Continue to color the vertices 
  }
  else
  {
  result[k]=0;
    k--;	                         //The vertex does not meet the constraints of coloring, backtracking 
  }
    
}
if(k==-1)
printf("No solution");
else
{ 
      printf("One solution to the problem of graph coloring is:\n");
  for(int i=0;i< n;i++)
  printf("Node %d color number: %d\n",i+1,result[i]);
  } 
} 
main()
{
  gc();
}                      
  

Time Complexity

                  Time Complexity = O(m^V), m= number of different colors, V = number of Vertices
                

EXPLANATION

OUTPUT

ALGORITHM

  A standard DFS implementation puts each vertex of the graph into one of two categories:
  1. Visited
  2. Not Visited
  The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

  The DFS algorithm works as follows:

  1. Start by putting any one of the graph's vertices on top of a stack.

  2. Take the top item of the stack and add it to the visited list.

  3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.

  4. Keep repeating steps 2 and 3 until the stack is empty.

CODE

#include<stdio.h>
#define MAX 20
void push(int Q[],int *t, int num)
{
  *t=*t+1;
  Q[*t]=num;
}
int pop(int Q[], int *t)
{
  // Assume there is no underflow situation
  int d=Q[*t];
  *t=*t-1;
  return d;
    
}

void main()
{
  
  int n,i,j,t=-1,num,k,pos;
  int Q[MAX];
  int a[MAX][MAX],status[MAX];
  printf("Enter No. of Nodes : ");
  scanf("%d",&n);
  for(i=0;i< n;i++)
  {
    printf("\n Enter for Node %c : ",i+65);
    for(j=0;j< n;j++)
    {
      scanf("%d",&a[i][j]);
    }
  }
  for(i=0;i< n;i++)
    status[i]=0;// initilaize with ready state
    
  status[0]=1; // running state
  num=0;
  k=1;
  push(Q,&t,num); // first time
  while(k<=n)
  {
    
    pos=pop(Q,&t);
    printf(" %c",pos+65);
    status[pos]=2;
    for(j=0;j< n;j++)
    {
      if(a[pos][j]==1 && status[j]==0)// first check neighbour second check tready state
      {
        status[j]=1; // running state
        push(Q,&t,j);
      }
    }
  
    k++;
  }
}

TIME COMPLEXITY

Time Complexity = O(V + E), where V and E are the vertice and the edges in the graph.

EXPLANATION

OUTPUT

ALGORITHM

  A standard BFS implementation puts each vertex of the graph into one of two categories:

  1. Visited
  2. Not Visited
  The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

  The algorithm works as follows:

  1.Start by putting any one of the graph's vertices at the back of a queue.
  2. Take the front item of the queue and add it to the visited list.
  3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
  4. Keep repeating steps 2 and 3 until the queue is empty.
  The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node

          

CODE

#include<stdio.h>
#define MAX 15
void Insert(int Q[], int *f, int *r, int num)
{
  if(*r==-1)// empty list
  {
    *r=0;
    *f=0;
    Q[*r]=num;
  }
  else
  {
    *r=*r+1;
    Q[*r]=num;
  }
}
int Delete(int q[], int *f, int *r)
{
  int num=q[*f];
  if(*f==*r)// single element
  {
    *f=-1;
    *r=-1;
  }
  else
  {
    *f=*f+1;
  }
  return num;
}
void main()
{
  int a[MAX][MAX],status[MAX],Q[MAX];
  int f=-1,r=-1;// initilaize
  int n,i,j,num,k,p;
  printf("\n Enter No. of nodes : ");
  scanf("%d",&n);
  for(i=0;i< n;i++)
  {
    printf("\n Enter data for Node %c : ",i+65);
    for(j=0;j< n;j++)
    {
      scanf("%d",&a[i][j]);// 1 for neighbour 0 for nothing
    }
  }
  
  for(i=0;i< n;i++)
    status[i]=0 ;// initialize
    
  num=0;
  status[0]=1;// for insertion in Queue
  Insert(Q,&f,&r,num);
  k=1;
  while(k<=n)
  {
    p=Delete(Q,&f,&r);
    printf(" %c",p+65);
    status[p]=2;// processed
    
    for(j=0;j< n;j++)
    {
      if(a[p][j]==1 && status[j]==0)
      {
        Insert(Q,&f,&r,j);
        status[j]=1;
      }
    }
    k++;
  }
}

TIME COMPLEXITY

 Time Complexity = O(V + E), where V and E is the number of vertices and edges.

EXPLANATION

OUTPUT