QUES1- Create a class SET and take two

sets as input from user to perform

following SET
Operations:
a) Subset: Check whether one set is a
subset of other or not.
b) Union and Intersection of two Sets.
c) Complement: Assume Universal Set as
per the input elements from the user.
d) Set Difference and Symmetric
Difference between two SETS
e) Cartesian Product of Sets.
CODE-
#include <iostream>

using namespace std;

class SET
{
private:
int i,j;

public:
void Subset(int *arrA, int sizeA, int *arrB,
int sizeB)
{
int c=0;

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

for(j=0; j<sizeB; j++)
if(arrA[i] == arrB[j])
c++;

if(c != sizeA)
cout << "SET A is not a subset of SET B" <<
endl;

else
cout << "SET A is a subset of SET B" <<
endl;
int c1=0;

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

for(j=0; j<sizeA; j++)
if(arrB[i] == arrA[j])
c1++;

if(c != sizeB)
cout << "SET B is not a subset of SET A" <<
endl;

else
cout << "SET B is a subset of SET A" <<
endl;
cout << "-----------------------------------------
--------" << endl;
}

void UnionInter(int *setA, int sizeA, int

*setB, int sizeB)
{
int uSize=sizeA+sizeB;
int uSet[uSize];
int unionSet[uSize];
int iSet[uSize];
int x=0,y=0;

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

{
uSet[x]=setA[i];
x++;
}

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

{
uSet[x]=setB[i];
x++;
}

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

{
for(j=i+1; j<x; j++)
{
if(uSet[i] == uSet[j])
{
iSet[y]=uSet[i];
y++;

for(int k=j; k<x-1; k++)

uSet[k]=uSet[k+1];
x--;
}

else
continue;
}
}

cout << "Union of two sets is : {";

for(i=0; i<x; i++)
cout << uSet[i] << " ";
cout << "}";

cout << endl;

if(y != 0)
{
cout << "Intersection of two sets is : {";

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

cout << iSet[i] << " ";
cout << "}";
}

else
cout << "No intersection found";

cout << endl;

cout << "-----------------------------------------
--------" << endl;
}

void Complement(int *setA, int sizeA, int

*setB, int sizeB)
{
int sizeU;
cout << "Enter the no. of elements of
universal set : ";
cin >> sizeU;

cout << "Enter the elemnts of universal

set : ";
int U[sizeU];

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

cin >> U[i];

int AC[sizeU],p=0,c=0;

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

{
for(j=0; j<sizeA; j++)
{
if(U[i] == setA[j])
c++;

else
continue;
}

if(c == 0)
{
AC[p]=U[i];
p++;
}
c=0;
}
cout << endl;

cout << "Complement of SET A is : {";

for(i=0; i<p; i++)
cout << AC[i] << " ";
cout << "}" << endl;

int BC[sizeU],q=0,ctr=0;

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

{
for(j=0; j<sizeB; j++)
{
if(U[i] == setB[j])
ctr++;

else
continue;
}

if(ctr == 0)
{
BC[q]=U[i];
q++;
}
ctr=0;
}

cout << "Complement of SET B is : {";

for(i=0; i<q; i++)
cout << BC[i] << " ";
cout << "}" << endl;

cout << "-----------------------------------------

--------" << endl;
}

void setNSymDiff(int *setA, int sizeA, int

*setB, int sizeB)
{
int ABDif[100],q=0,ctr=0;

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

{
for(j=0; j<sizeB; j++)
{
if(setA[i] == setB[j])
ctr++;

else
continue;
}
if(ctr == 0)
{
ABDif[q]=setA[i];
q++;
}

ctr=0;
}

cout << "Set difference A-B is : {";

for(i=0; i<q; i++)
cout << ABDif[i] << " ";
cout << "}" << endl;
int BADif[100],p=0,c=0;

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

{
for(j=0; j<sizeA; j++)
{
if(setB[i] == setA[j])
c++;

else
continue;
}

if(c == 0)
{
BADif[p]=setB[i];
p++;
}

c=0;
}

cout << "Set difference B-A is : {";

for(i=0; i<p; i++)
cout << BADif[i] << " ";
cout << "}" << endl;

int uSize=q+p;
int symDif[uSize];
int x=0,y=0;

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

{
symDif[x]=ABDif[i];
x++;
}

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

{
symDif[x]=BADif[i];
x++;
}
cout << "Symmetric difference b/w two
sets is : {";
for(i=0; i<x; i++)
cout << symDif[i] << " ";
cout << "}";

cout << endl;

cout << "-----------------------------------------
--------" << endl;
}

void cartesianPro(int *setA, int sizeA, int

*setB, int sizeB)
{
int sizeAB,sizeBA,x=0,y=0;

sizeAB=sizeA*sizeB;
sizeBA=sizeAB;

int AB[sizeAB*2],BA[sizeBA*2];

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

{
for(j=0; j<sizeB; j++)
{
AB[x++]=setA[i];
AB[x++]=setB[j];
}
}

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

{
for(j=0; j<sizeA; j++)
{
BA[y++]=setB[i];
BA[y++]=setA[j];
}
}

cout << "A X B = { ";

for(i=0; i<x; i++)
{
if(i%2 == 0)
cout << "(";
cout << AB[i] << " ";

if(i%2 != 0)
cout << ")";
}
cout << " }" << endl;

cout << "B X A = { ";

for(i=0; i<y; i++)
{
if(i%2 == 0)
cout << "(";
cout << BA[i] << " ";

if(i%2 != 0)
cout << ")";
}
cout << " }" << endl;

cout << "-----------------------------------------

--------" << endl;
}
};

int main()
{
cout << endl;
int i,sizeA,sizeB;

cout << "Enter the no. of elements in SET

A : ";
cin >> sizeA;

int arrA[sizeA];

cout << "Enter the elements : ";

for(i=0; i<sizeA; i++)
cin >> arrA[i];

cout << "Enter the no. of elements in SET

B : ";
cin >> sizeB;
int arrB[sizeB];

cout << "Enter the elements : ";

for(i=0; i<sizeB; i++)
cin >> arrB[i];

cout << "-----------------------------------------

--------" << endl;

SET ob;

cout << "\tSUBSET\n" << endl;

ob.Subset(arrA, sizeA, arrB, sizeB);
cout << "\tUNION and INTERSECTION\n"
<< endl;
ob.UnionInter(arrA, sizeA, arrB, sizeB);

cout << "\tCOMPLEMENT\n" << endl;

ob.Complement(arrA, sizeA, arrB, sizeB);

cout << "\tSET and SYMMETRIC

DIFFERENCE\n" << endl;
ob.setNSymDiff(arrA, sizeA, arrB, sizeB);

cout << "\tCARTESIAN PRODUCT\n" <<

endl;
ob.cartesianPro(arrA, sizeA, arrB, sizeB);
return 0;
}

OUTPUT
QUES2- Create a class RELATION, use
Matrix notation to represent a relation.
Include functions to
check if a relation is reflexive,
Symmetric, Anti-symmetric and
Transitive. Write a Program
to use this class.
CODE- #include<iostream>
#include<stdio.h>
#include<conio.h>

using namespace std;

class RELATION
{
private:
int
i,j,k,x,y,z,ctr,iA,iB,nA,nR,*A,*R,**RM,*
*T;

public:
void empty();
int inputSet();
void inputRelation();
void printSet();
void printRelation();
void Matrix();
int reflexive();
int symmetric();
bool antiSymmetric();
bool transitive();
};

void RELATION::empty()
{
cout << "Set A is empty\n";
printSet();
cout << "Set A has no member.";
cout << "\nHence, relation R is
empty.\n";
nR = 0;
printRelation();
cout << "Therefore, no matrix
notation.";
cout << "\nRelation R is NOT
REFLEXIVE.";
symmetric();
antiSymmetric();
transitive();
}

int RELATION::inputSet()
{
cout << "Enter the size of SET A : ";
cin >> nA;
A = new int[nA];

if(nA == 0)
return 1;

cout << "Enter the elements : ";

for(i=0; i<nA; i++)
cin >> A[i];
}

void RELATION::inputRelation()
{
cout << "Enter the no of relations (R on
A) : ";
cin >> nR;
R = new int[nR * 2];
cout << "Enter the relations in pair :\n";
for(i=0; i<nR*2; i++)
cin >> R[i];
}

void RELATION::printSet()
{
cout << "A = {";
for(i=0; i<nA; i++)
cout << A[i] << " ";
cout << "}\n";
}

void RELATION::printRelation()
{
cout << "R = {";
for(i=0; i<nR*2; i++)
{
if(i%2 == 0)
cout << "(";
cout << R[i] << " ";
if(i%2 != 0)
cout << ")";
}
cout << "}\n";
}

void RELATION::Matrix()
{
cout << "\nMATRIX NOTATION\n\n";
RM = new int *[nA];
for(i=0; i<nA; i++)
RM[i]=new int[nA];
for(i=0; i<nA; i++)
{
for(j=0; j<nA; j++)
{
RM[i][j]=0;
}
}

for(i=0; i<nR*2; i+=2)

{
for(j=0; j<nA; j++)
{
if(R[i] == A[j])
{
iA=j;
break;
}
}
for(k=0; k<nA; k++)
{
if(R[i+1] == A[k])
{
iB=k;
break;
}
}
RM[iA][iB]=1;
}

cout << " ";

for(int x=0; x<nA; x++)
cout << " " << A[x] << " ";
cout << endl << endl;
for(i=0; i<nA; i++)
{
cout << A[i] << " | ";
for(j=0; j<nA; j++)
{
cout << RM[i][j] << " ";
}
cout << "|";
cout << endl;
}
}

int RELATION::reflexive()
{
x=0;
for(i=0; i<nA; i++)
{
if(RM[i][i] == 1)
x++;
}
if(x == nA)
{
cout << "\nRelation R is REFLEXIVE.";
return x = 0;
}

else
{
cout << "\nRelation R is NOT
REFLEXIVE.";
return x = 1;
}
}
int RELATION::symmetric()
{
ctr = 0;

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

{
for(j=0; j<nA; j++)
{
if(RM[i][j] == RM[j][i])
continue;

else
{
ctr++;
break;
}
}
}

if(ctr != 0)
cout << "\nRelation R is NOT
SYMMETRIC.";

else
cout << "\nRelation R is SYMMETRIC.";

return ctr;
}

bool RELATION::antiSymmetric()
{
bool flag = true;

for(i=0; i<nR*2; i+=2)

{
for(j=0; j<nR*2; j+=2)
{
if((R[i] == R[j+1]) && (R[i+1] == R[j]))
if(R[i] == R[i+1])
{
continue;
}

else
{
flag = false;
}
}
}

if(flag != true)
cout << "\nRelation R is NOT ANTI-
SYMMETRIC.";

else
cout << "\nRelation R is ANTI-
SYMMETRIC.";

return flag;
}

bool RELATION::transitive()
{
bool flag = true;

for(i=0; i<nR*2; i+=2)

{
for(j=0; j<nR*2; j+=2)
{
if(R[i+1] == R[j])
for(k=0; k<nR*2; k+=2)
{

if((R[k] == R[i]) && (R[k+1] == R[j+1]))

{
flag = true;
break;
}

else
flag = false;
}
}
}

if(flag != true)
cout << "\nRelation R is NOT
TRANSITIVE.";

else
cout << "\nRelation R is TRANSITIVE.";

return flag;
}

int main()
{
int p = 0;

RELATION ob;

p = ob.inputSet();

if(p == 1)
ob.empty();

else
{
ob.printSet();
ob.inputRelation();
ob.printRelation();
ob.Matrix();
ob.reflexive();
ob.symmetric();
ob.antiSymmetric();
ob.transitive();
}

return 0;
}
OUTPUT-
QUES3- Write a Program that
generates all the permutations of a
given set of digits, with or without
repetition.

CODE- #include<iostream>
#include<stdio.h>
#include<conio.h>
#define MAX_DIM 100

using namespace std;

void withRepetition(int*, int);

void withoutRepetition(int*, int);
void printWithRepetition(int*, int, int*,
int, int);
void printWithoutRepetition(int*, int,
int, int);
void swap(int &, int &);

int main()
{
int size;
char ch;

cout << "Enter the size of set: ";

cin >> size;
int array[MAX_DIM];
cout << "Enter the elements: ";
for(int i=0; i<size; i++)
cin >> array[i];

cout << "\nIs repetition allowed (Y/N):

";
cin >> ch;

switch(ch)
{
case 'Y':
withRepetition(array, size);
break;
case 'N':
withoutRepetition(array, size);
break;
default:
cout << "\nWrong Choice";
}

return 0;
}

void withRepetition(int* array, int size)

{
int data[MAX_DIM] = {0};
printWithRepetition(array, size, data,
size-1, 0);
cout << endl;
}

void printWithRepetition(int* array, int

size, int *data, int last, int index)
{
for(int i=0; i<size; i++)
{
data[index] = array[i];
if(index == last)
{
cout << "{";
for(int j=0; j<index+1; j++)
cout << data[j] << " ";
cout << "}";
}

else
{
printWithRepetition(array, size, data,
last, index+1);
}
}
}
void withoutRepetition(int* array, int
size)
{
printWithoutRepetition(array, size, 0,
size-1);
cout << endl;
}

void printWithoutRepetition(int* array,

int size, int start, int end)
{
if(start == end)
{
cout << "{";
for(int i=0; i<size; i++)
cout << array[i] << " ";
cout << "}";
}

else
{
for(int i=start; i<end+1; i++)
{
swap(array[start], array[i]);
printWithoutRepetition(array, size,
start+1, end);
swap(array[start], array[i]);
}
}
}

void swap(int &a, int &b)

{
int t = b;
b = a;
a = t;
}
OUTPUT-
QUES4-. For any number n, write a
program to list all the solutions of the
equation x1 + x2 + x3 + ...+ xn = C,
where C is a constant (C<=10) and x1,
x2,x3,...,xn are nonnegative integers,
using brute force strategy.

CODE- #include<iostream>

using namespace std;

void bruteForce(int*, int, int*, int, int,

int, int&);
int main()
{
int n, C, counter = 0, size = 11;
int arr[size], data[100] = {0};

cout << "\nFinding solutions to x1 + x2

+ ... + xn = C\n";
cout << "Enter the value of n: ";
cin >> n;
for (int i=0; i <= 10; i++)
arr[i] = i;
cout << "Enter the sum constant (C <=
10): ";
cin >> C;
cout << "Possible Non-negative
Integral solutions [ ";
for(int i=0; i<n; i++)
cout << "x" << i+1 << " ";
cout << " ] :" << endl;

bruteForce(arr, size, data, n-1, 0, C,

counter);
cout << "\nFound " << counter << "
Solutions\n";
return 0;
}
void bruteForce(int* arr, int size, int*
data, int last, int index, int C, int
&counter)
{
for(int i=0; i<size; i++)
{
data[index] = arr[i];
if(index == last)
{
int sum = 0;
for(int j=0; j<index+1; j++)
sum += data[j];

if(sum == C)
{
cout << "[ ";
for(int j=0; j<index+1; j++)
cout << data[j] << " ";
cout << "] ";
counter++;
}
}

else
bruteForce(arr, size, data, last,
index+1, C, counter);
}
}
OUTPUT-
QUES5- Write a Program to evaluate a
polynomial function. (For example
store f(x) = 4n2 + 2n + 9 in an array and
for a given value of n, say n = 5,
compute the value of f(n))

CODE- #include<iostream>
#include<stdio.h>
#include<conio.h>
#include<cmath>
using namespace std;

int i;

class FUNCTION
{
private:
int n;
double *coefficient;
double *exponential;

public:
void input();
void display();
double evaluate(double);
};

void FUNCTION::input()
{
int n;
cout << "\nEnter the number of terms:
";
cin >> this->n;

coefficient = new double[n];

exponential = new double[n];

for(i=0; i<this->n; i++)

{
cout << "Enter coefficient and
exponential of term " << i+1 << ": ";
cin >> coefficient[i] >> exponential[i];
}
}

void FUNCTION::display()
{
for(i=0; i<this->n; i++)
{
if(coefficient[i] >= 0)
cout << " + ";
else
cout << " - ";
cout << abs (coefficient[i]);
if(exponential[i] != 0)
cout << "(x^" << exponential[i] << ")";
}
}

double FUNCTION::evaluate(double x)
{
double result = 0.0;
for(i=0; i<this->n; i++)
{
result += coefficient[i] * (pow(x,
exponential[i]));
}

return result;
}

int main()
{
double x;

FUNCTION ob;

ob.input();
cout << "Function is f(x) = ";
ob.display();
cout << "\nEnter the value of x: ";
cin >> x;
cout << "\nValue of f(" << x << "): " <<
ob.evaluate(x) << endl;

return 0;
}

OUTPUT-
QUES6- Write a Program to check if a
given graph is a complete graph.
Represent the graph using the
Adjacency Matrix representation.

CODE- #include<iostream>

using namespace std;

int countPaths(int graph[][100], int n,

int src, int dest, int len)
{
int count[n][n][len + 1];
for(int e=0; e<=len; e++)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
count[i][j][e] = 0;
if(e == 0 && i == j)
count[i][j][e] = 1;

if(e == 1 && graph[i][j])

count[i][j][e] = 1;
if(e > 1)
for(int a=0; a<n; a++)
if(graph[i][a])
count[i][j][e] += count[a][j][e - 1];
}
}
}

return count[src][dest][len];
}

int main()
{
int v;
cout << "\nEnter the nunber of
vertices: ";
cin >> v;

int matrix[100][100];
cout << "Enter the adjacency
matrix:\n";
for(int i=0; i<v; i++)
for(int j=0; j<v; j++)
cin >> matrix[i][j];

int src, dest;

cout << "Enter the source node: ";
cin >> src;
cout << "Enter the destinastion node:
";
cin >> dest;

int len;
cout << "Enter the path lemgth: ";
cin >> len;

cout << "Total paths from node " << src

<< " to node " << dest << " having "
<< len << " edges: "
<< countPaths(matrix, v, src-1, dest-1,
len);
return 0;
}

OUTPUT-

GRAPH-
QUES8- Write a Program to accept a
directed graph G and compute the in-
degree and outdegree of each vertex.
CODE- #include<iostream>
#include<cmath>

using namespace std;

int main()
{
int v, nin, nout, inver, outver;
cout << "\nEnter the no. of vertices: ";
cin >> v;

int matrix[v][v];
for(int i=0; i<v; i++)
for(int j=0; j<v; j++)
matrix[i][j] = 0;

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

{
cout << "Enter the no. of edges
incoming to vertex " << i+1 << ": ";
cin >> nin;
for(int x=0; x<nin; x++)
{
cout << "Enter the vertex from which
incoming edge to vertex " << i+1 << " is
emerging from: ";
cin >> inver;
matrix[i][inver -1] = -1;
}

cout << "Enter the no. of edges

outgoing from vertex " << i+1 << ": ";
cin >> nout;
for(int y=0; y<nout; y++)
{
cout << "Enter the vertex to which
outgoing edge from vertex " << i+1 << "
is ending at: ";
cin >> outver;
matrix[i][outver -1] = 1;
}
}

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

{
int indegree=0, outdegree=0;
for(int j=0; j<v; j++)
{
if(matrix[i][j] == 1)
outdegree += matrix[i][j];

if(matrix[i][j] == -1)
indegree += matrix[i][j];
}

cout << "\n\nIn-degree of vertex " <<

i+1 << " is " << abs(indegree)
<< "\tOut-degree of vertex " << i+1 << "
is " << outdegree;
}

return 0;
}

OUTPUT-
GRAPH-
QUES7-. Write a Program to check if a
given graph is a complete graph.
Represent the graph using the
Adjacency List representation.

CODE- # Adjascency List

representation in Python

class AdjNode:
def __init__(self, value):
self.vertex = value
self.next = None
class Graph:
def __init__(self, num):
self.V = num
self.graph = [None] * self.V

# Add edges
def add_edge(self, s, d):
node = AdjNode(d)
node.next = self.graph[s]
self.graph[s] = node

node = AdjNode(s)
node.next = self.graph[d]
self.graph[d] = node
 # Print the graph
def print_agraph(self):
for i in range(self.V):
print("Vertex " + str(i) + ":",
end="")
temp = self.graph[i]
while temp:
print(" ->
{}".format(temp.vertex), end="")
temp = temp.next
print(" \n")

if __name__ == "__main__":
V=5
 # Create graph and edges
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(1, 2)

graph.print_agraph()

OUTPUT-
GRAPH-

INTRODUCTION
Name-Sumit Kumar
ROLL. NO- 23020570053
COURSE- Bsc.(hons.)
computer science
SEMESTER-
SUBJECT- DISCRETE
MATHEMATICAL
STRUCTURES
SUBMITTED TO- Dr. Aakash