Maximum and Minimum using Divide and Conquer
in c
code in C:
#include<stdio.h>
#include<stdio.h>
int max, min;
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)
{
if(a[i] <a[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);
return 0;
}
output:-
Enter the total number of numbers : 5
Enter the numbers :
29
21
64
27
20
Minimum element in an array : 20
Maximum element in an array : 64
--------------------------------
Lab program 9: Implement any scheme to find the optimal
solution for the Traveling Salesperson problem and then solve
the same problem instance using any approximation algorithm
and determine the error in the approximation.
Description:
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to
the travelling salesman problem. In it, the salesman starts at a random city and repeatedly visits the
nearest city until all have been visited. It quickly yields a short tour, but usually not the optimal one.
Algorithm
1. Start on an arbitrary vertex as current vertex.
2. Find out the shortest edge connecting current vertex and an unvisited vertex V.
3. Set current vertex to V.
4. Mark V as visited.
5. If all the vertices in domain are visited, then terminate.
6. Go to step 2.
7. The sequence of the visited vertices is the output of the algorithm.
Solution:
#include<stdio.h>
int a[10][10],n,visit[10];
int cost_opt=0,cost_apr=0;
int least_apr(int c);
int least_opt(int c);
void mincost_opt(int city)
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_opt(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);
cost_opt+=a[city][ncity];
return;
}
mincost_opt(ncity);
void mincost_apr(int city)
{
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_apr(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);
cost_apr+=a[city][ncity];
return;
}
mincost_apr(ncity);
int least_opt(int c)
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<min)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_opt+=kmin;
return nc;
int least_apr(int c)
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<kmin)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_apr+=kmin;
return nc;
void main()
int i,j;
printf("Enter No. of cities:\n");
scanf("%d",&n);
printf("Enter the cost matrix\n");
for(i=1;i<=n;i++)
{
printf("Enter elements of row:%d\n",i );
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
visit[i]=0;
}
printf("The cost list is \n");
for(i=1;i<=n;i++)
{
printf("\n\n");
for(j=1;j<=n;j++)
printf("\t%d",a[i][j]);
}
printf("\n\n Optimal Solution :\n");
printf("\n The path is :\n");
mincost_opt(1);
printf("\n Minimum cost:");
printf("%d",cost_opt);
printf("\n\n Approximated Solution :\n");
for(i=1;i<=n;i++)
visit[i]=0;
printf("\n The path is :\n");
mincost_apr(1);
printf("\nMinimum cost:");
printf("%d",cost_apr);
printf("\n\nError in approximation is approximated solution/optimal solution=%f",
(float)cost_apr/cost_opt);
OUTPUT 1 :
Enter No. of cities:
Enter the cost matrix
Enter elements of row:1
0136
Enter elements of row:2
1023
Enter elements of row:3
3201
Enter elements of row:4
6310
The cost list is
0 1 3 6
1 0 2 3
3 2 0 1
6 3 1 0
Optimal Solution :
The path is :
1-->2-->4-->3-->1
Minimum cost:8
Approximated Solution :
The path is :
1-->2-->3-->4-->1
Minimum cost:10
Error in approximation is approximated solution/optimal solution=1.250000
// C# program to find k'th smallest
// element in expected linear time
using System;
class GFG
// This function returns k'th smallest
// element in arr[l..r] using QuickSort
// based method. ASSUMPTION: ALL ELEMENTS
// IN ARR[] ARE DISTINCT
int kthSmallest(int []arr, int l, int r, int k)
// If k is smaller than number
// of elements in array
if (k > 0 && k <= r - l + 1)
// Partition the array around a
// random element and get position
// of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k - 1)
return arr[pos];
// If position is more, recur
// for left subarray
if (pos - l > k - 1)
return kthSmallest(arr, l, pos - 1, k);
// Else recur for right subarray
return kthSmallest(arr, pos + 1, r,
k - pos + l - 1);
// If k is more than number of
// elements in array
return int.MaxValue;
// Utility method to swap arr[i] and arr[j]
void swap(int []arr, int i, int j)
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Standard partition process of QuickSort().
// It considers the last element as pivot and
// moves all smaller element to left of it
// and greater elements to right. This function
// is used by randomPartition()
int partition(int []arr, int l, int r)
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
if (arr[j] <= x)
swap(arr, i, j);
i++;
swap(arr, i, r);
return i;
// Picks a random pivot element between
// l and r and partitions arr[l..r]
// around the randomly picked element
// using partition()
int randomPartition(int []arr, int l, int r)
int n = r - l + 1;
Random rnd = new Random();
int rand = rnd.Next(0, 1);
int pivot = (int)(rand * (n - 1));
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
// Driver Code
public static void Main()
GFG ob = new GFG();
int []arr = {12, 3, 5, 7, 4, 19, 26};
int n = arr.Length,k = 3;
Console.Write("K'th smallest element is "+
ob.kthSmallest(arr, 0, n - 1, k));
// This code is contributed by 29AjayKumar
Output
K'th smallest element is 5
Time Complexity:
The worst-case time complexity of the above solution is still O(n 2). In the worst
case, the randomized function may always pick a corner element. The expected
time complexity of above randomized QuickSelect is O(n), see CLRS
book or MIT video lecture for proof. The assumption in the analysis is, random
number generator is equally likely to generate any number in the input range.
Auxiliary Space: O(1) since using constant variables
// C program for Naive Pattern Searching algorithm
#include <stdio.h>
#include <string.h>
void search(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++) {
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j
== M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
printf("Pattern found at index %d \n", i);
// Driver's code
int main()
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
// Function call
search(pat, txt);
return 0;
}
Output
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Time Complexity: O(N2)
Auxiliary Space: O(1)
