Scribd
Upload
22 views23 pages

C Programs for Set Operations and Graphs

The document contains 9 problems related to data structures and algorithms. Each problem provides code to implement a specific operation like union, intersection, difference etc. on sets or find the shortest path in a graph. The code examples are written in C language.

Uploaded by

tbhhey7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views23 pages

C Programs for Set Operations and Graphs

The document contains 9 problems related to data structures and algorithms. Each problem provides code to implement a specific operation like union, intersection, difference etc. on sets or find the shortest path in a graph. The code examples are written in C language.

Uploaded by

tbhhey7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Practical Work

A
project report
submitted for fulfilment of
Practical of Bachelor of Technology,
Department of Computer Science
and
Engineering

By
Utkarsh Prajapati (2101660100061)

Department of Computer Science and Engineering

Dr. Ambedkar Institute of Technology for Handicapped


LIST OF PROBLEMS

1. Write a program in C to create two sets and


perform the Union operation on sets.
2. Write a program in C to create two sets and
perform the Intersection operation on sets.
3. Write a program in C to create two sets and
perform the Difference operation on sets.
4. Write a program in C to create two sets and
perform the Symmetric Difference operation.
5. Write a program in C to perform Power set
operation on a set.
6. Write a program in C to display the Boolean Truth
Table for AND, OR, NOT.
7. Write a C program to find Cartesian Product of two
sets.
8. Write a program in C for Minimum Cost Spanning
Tree.
9. Write a program in C for finding the shortest path
in a graph.
PROBLEM 1:
Write a program in C to create two sets and
perform the Union operation on sets.
CODE:
#include<stdio.h>
int main()
{
int a1[20],a2[20],u[40],i,j,k,n,m;
printf("Enter size of first array:");
scanf("%d",&n);
printf("Enter elements of first array in ascending order:\n");
for(i=0;i<n;++i){
scanf("%d",&a1[i]);
}
printf("\nEnter size of second array:");
scanf("%d",&m);
printf("Enter elements of second array in ascending order:\n");
for(i=0;i<m;++i){
scanf("%d",&a2[i]);
}
for(i=0,j=0,k=0;i<n&&j<m;){
if(a1[i]<a2[j]){
u[k]=a1[i];
i++;
k++;
}
else if(a1[i]>a2[j]){
u[k]=a2[j];
j++;
k++;
}
else{
u[k]=a1[i];
i++;
j++;
k++;
}}
if(i<n){
for(;i<n;++i){
u[k]=a1[i];
k++;
}}
else if(j<m){
for(;j<m;++j){
u[k]=a2[j];
k++;
}}
printf("\nUnion of two arrays is:\n");
for(i=0;i<k;++i){
printf("%d ",u[i]);
}
return 0;
}
OUTPUT:
PROBLEM 2:
Write a program in C to create two sets and
perform the intersection operation on sets.
CODE:
#include<stdio.h>
int main()
{
int a[100],b[100],c[100],n1,n2,n,k=0,i,j;

// taking input of set A

printf("Enter number of element of set A\n");


scanf("%d",&n1);
printf("Enter elements of set A\n");
for(i=0;i<n1;i++)
scanf("%d",&a[i]);
printf("Enter number of element of set B\n");
scanf("%d",&n2);
printf("Enter elements of set B\n");
for( i=0;i<n2;i++)
scanf("%d",&b[i]);

// Logic for intersection

for( i=0;i<n1;i++)
{
for(j=0;j<n2;j++)
{
if(a[i]==b[j])
{
c[k]=a[i];
k++;
}
}
}
printf("intersection of set A and set B is:-\n"); for(i=0;i<k;i++)
printf("%d ",c[i]);

return 0;
}
OUTPUT:
PROBLEM 3:
Write a program in C to create two sets and perform
the Difference operation on sets.
CODE:
#include<stdio.h>
int main()
{
int a[10],b[10],c[10],d[10],m=0,k=0,n1,n2,l,i,j;
printf("Enter size of set A");
scanf("%d",&n1);
printf("Enter element of set");
for( i=0;i<n1;i++)
scanf("%d",&a[i]);
printf("Enter size of set B");
scanf("%d",&n2);
printf("Enter element of set");
for( i=0;i<n2;i++)
scanf("%d",&b[i]);
for( i=0;i<n1;i++)
{for(j=0;j<n2;j++)
{if(b[j]==a[i])
break;}
if(j==n2)
{for(l=0;l<k;l++)
{if(c[l]==a[i])
break;}
if(l==k)
{c[k]=a[i];
k++;}}}
for( i=0;i<n2;i++)
{for(j=0;j<n1;j++)
{if(b[i]==a[j])
break;}
if(j==n1)
{for(l=0;l<m;l++)
{if(d[l]==b[i])
break;}
if(l==m)
{d[m]=b[i];
m++;}}}
printf("Difference of A-B is:-\n");
for(i=0;i<k;i++)
{printf("%d ",c[i]);}
printf("\n");
printf("Difference of B-A is:-\n");
for(i=0;i<m;i++)
{printf("%d ",d[i]);}
return 0;
}
OUTPUT:
PROBLEM 4:
Write a program in C to create two sets and perform
the Symmetric Difference operation
CODE:
#include<stdio.h>
int main()
{
int a[10],b[10],c[10],d[10],m=0,k=0,n=0,n1,n2,l,i,j,sy[100];
printf("Enter size of set A");
scanf("%d",&n1);
printf("Enter element of set");
for( i=0;i<n1;i++)
scanf("%d",&a[i]);
printf("Enter size of set B");
scanf("%d",&n2);
printf("Enter element of set");
for( i=0;i<n2;i++)
scanf("%d",&b[i]);
for( i=0;i<n1;i++)
{for(j=0;j<n2;j++)
{if(b[j]==a[i])
break;}
if(j==n2)
{for(l=0;l<k;l++)
{if(c[l]==a[i])
break;}
if(l==k)
{c[k]=a[i];
k++;}}}
for( i=0;i<n2;i++)
{for(j=0;j<n1;j++)
{if(b[i]==a[j])
break;}
if(j==n1)
{for(l=0;l<m;l++)
{if(d[l]==b[i])
break;}
if(l==m)
{d[m]=b[i];
m++;}}}
for(i=0;i<k;i++)
{sy[n]=c[i];
n++;}
for(i=0;i<m;i++)
{sy[n]=d[i];
n++;}
printf("\nsymmetric Difference of sets is:-\n");
for(i=0;i<n;i++)
printf("%d ",sy[i]);
return 0;
}
OUTPUT:
PROBLEM 5:
Write a program in C to perform Power set operation
on a set
CODE:
#include <stdio.h>
#include <math.h>
int subset(int bitn, int num, int num_of_bits) {
if (bitn >= 0) {
if ((num & (1 << bitn)) != 0) {
printf("%d ", num_of_bits - bitn);}
subset(bitn - 1, num, num_of_bits);}
else
return 0;
return 1;}
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
printSubSets(num_of_bits, num - 1);}
else
return 0;
return 1;}
int main() {
int n ;
printf("\nenter the value of n:");
scanf("%d",&n);
printSubSets(n, (int) (pow(2, n)) -1);}

OUTPUT:
PROBLEM 6:
Write a program in C to display the Boolean Truth Table
for AND, OR, NOT
CODE:
#include<stdio.h>
int find_OR(int x,int y)
{if(x==1 && y==1)
return 1;
if(x==1 && y==0 || x==0 && y==1)
return 1;
if(x==0 && y==0)
return 0;}
int find_AND(int x,int y)
{if(x==1 && y==1)
return 1;
else
return 0;}
int find_NOT(int x)
{if(x==1)
return 0;
else
return 1;}
int main()
{int ch,a,b;
printf("1. OR\n");
printf("2. AND\n");
printf("3. NOT\n");
printf("4 .exit\n");
while(1)
{printf("\nEnter your choice\n");
scanf("%d",&ch);
switch(ch)
{case 1: printf("Give two input 1 for true and 0 for false\n");
scanf("%d%d",&a,&b);
printf("%d",find_OR(a,b));
break;
case 2: printf("Give two input 1 for true and 0 for false\n");
scanf("%d%d",&a,&b);
printf("%d",find_AND(a,b));
break;
case 3: printf("Give an input 1 for true and 0 for false\n");
scanf("%d",&a);
printf("%d",find_NOT(a));
break;
case 4: exit(0);
default: printf("Wrong key\n");}}}
OUTPUT:
PROBLEM 7:
Write a C program to find Cartesian Product of two sets
CODE:
#include<stdio.h>
int main()
{
int a[10],b[10],n1,n2;
printf("Enter size of set A\n");
scanf("%d",&n1);
printf("Enter element of set A\n");
for(int i=0;i<n1;i++)
scanf("%d",&a[i]);
printf("Enter size of set B\n");
scanf("%d",&n2);
printf("Enter element of set B\n");
for(int i=0;i<n2;i++)
scanf("%d",&b[i]);
printf("{");
for(int i=0;i<n1;i++)
{for(int j=0;j<n2;j++)
{printf(" (%d %d) ",a[i],b[j]);}}
printf("}");
return 0;}
OUTPUT:
PROBLEM 8:
Write a program in C for Minimum Cost Spanning Tree
CODE:
#include<stdio.h>
int main()
{int cost[10][10],visited[10]={0},i,j,n,no_e=1,min,a,b,min_cost=0;
printf("Enter number of nodes ");
scanf("%d",&n);
printf("Enter cost in form of 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]=1000;}}
visited[1]=1;
while(no_e<n)
{min=1000;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
{if(cost[i][j]<min)
{if(visited[i]!=0)
{min=cost[i][j];
a=i;
b=j;}}}}
if(visited[b]==0)
{printf("\n%d to %d cost=%d",a,b,min);
min_cost=min_cost+min;
no_e++;}
visited[b]=1;
cost[a][b]=cost[b][a]=1000;}
printf("\nminimum weight is %d",min_cost);
return 0;}

OUTPUT:
PROBLEM 9:
Write a program in C for finding the shortest path in a
graph
CODE:

#include <limits.h>
#include <stdio.h>
#define V 9
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
int main()
{
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}

Common questions

Powered by AI

The program iterates over each element of the first set and compares it with every element of the second set. When it identifies matching elements, it adds them to a result array. This approach ensures all common elements are included in the intersection .

The program uses two sorted arrays to perform the union. It iterates through both arrays simultaneously and compares elements. If an element in the first array is smaller, it is added to the union result. If an element is larger, the element from the second array is added. If elements are equal, only one is added, and both indices are incremented. This continues until all elements are processed .

Adjacency matrices are used effectively in graph-related programs for representing the presence and cost of edges between nodes. This approach allows for direct access and manipulation of edge weights. Particularly in algorithms like finding the minimum cost spanning tree and shortest path, adjacency matrices provide a straightforward mechanism to iterate and update path costs dynamically, simplifying neighbor-node connections .

The program gathers two sets as inputs and utilizes nested loops to iterate over elements of the first set combined with elements of the second set, producing all possible ordered pairs. These pairs represent each element of the Cartesian product, displaying comprehensively within braces as part of the final output .

The program utilizes bitwise operations to generate the power set. It treats each element of the set as a bit, with total combinations equaling 2^n. It iterates from 0 to 2^n - 1 and uses a helper function to determine which elements are included in each subset by checking if the corresponding bit is set, thus generating all potential subsets efficiently .

The program first calculates the difference of set A with set B and vice versa, marking elements found only in one set. Then, it combines these two differences to form a symmetric difference. This dual comparison ensures that only unique elements to each set are included, accurately capturing the symmetric difference. The approach is systematic yet challenging to conceptualize comprehensively .

The program implements Prim's algorithm for finding the minimum cost spanning tree. It maintains a visited node array and iteratively selects the smallest edge connecting a visited node to an unvisited node, adding it to the minimal spanning tree. The process continues until all nodes are included. The algorithm efficiently finds the minimal connection paths by adjusting weights of edges dynamically .

The program calculates set differences by iterating through each element of the first set and checking if it exists in the second set. If it doesn't, and it's also not already in the result array, it is added to the difference result. The same process is repeated for the elements of the second set to find their difference from the first set, ensuring both A-B and B-A differences are captured distinctly .

The program uses Dijkstra's algorithm for finding the shortest path, which initializes all distances as infinity except the starting node set at zero. It iteratively selects the node with the minimal distance and updates the distances of adjacent nodes if a shorter path is found through this node. By marking nodes as visited, the algorithm ensures each node is processed optimally, minimizing the total traversal cost .

The C program for the Boolean truth table uses a switch-case structure facilitating user interaction for selecting AND, OR, or NOT operations. Each operation has its dedicated function returning results based on given inputs. For OR and AND, two inputs are required, while for NOT only one. This modular approach allows for clear logical separation of each Boolean operation, ensuring concise and effective calculations .

You might also like