DISCRETE

STRUCTURES
PRACTICAL
FILE
Submitted
to- DR. REENA JAIN (Teacher In-charge)
As part of academic curriculum (FIRST YEAR- 2ND SEMESTER)
BSC. (HONS) COMPUTER SCIENCE

NAME – KASHISH MADAN

COLLEGE ROLL NUMBER- 21570006
COLLEGE NAME- KALINDI COLLEGE
PAPER CODE - 32341202
 INDEX
PRACTICAL QUESTION
NO.
1 and 2 Write a program to create a SET A and determine the
cardinality of SET for an input array of elements(repetition
allowed ) and perform the following operations on the SET.

a) ismember (a, A): check whether an element belongs

to set or not and return value as true/false.
b) powerset(A): list all the elements of power set of A.
c) Subset: Check whether one set is a subset of other or
not.
d) Union and Intersection of two Sets.
e) Complement: Assume Universal Set as per the input
elements from the user.
f) Set Difference and Symmetric Difference between two
SETS
g) Cartesian Product of Sets.

3 and 4 Create a class RELATION , use matrix notation to represent a

relation . Include functions to check if the relation is
Reflexive, Symmetric, Anti-symmetric and Transitive. Also
include functions to check whether the relation is Equivalence
or Partial Ordering.

5 Write a Program to generate the Fibonacci Series using

recursion.

6 Write a Program to implement Tower of Hanoi using recursion.

7 Write a Program to implement binary search using recursion.

8 Write a Program to implement Bubble Sort. Find the number of

comparisons during each pass and display the intermediate
result. Use the observed values to plot a graph to analyse the
complexity of algorithm.
9 Write a Program to implement Insertion Sort. Find the number
of comparisons during each pass and display the intermediate
result. Use the observed values to plot a graph to analyse the
complexity of algorithm.

10 Write a Program that generates all the permutations of a given

set of digits, with or without repetition. (For example, if the
given set is {1,2}, the permutations are 12 and 21).
11 Write a Program to calculate Permutation and Combination for
an input value n and r using recursive formula of nCr and nPr .

12 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.

13 Write a Program to accept the truth values of variables x and y,

and print the truth table of the following logical operations:
a) Conjunction f) Exclusive NOR
b) Disjunction g) Negation
c) Exclusive OR h) NAND
d) Conditional i) NOR
e) Bi-conditional
14 Write a program to accept an input n from the user and
graphically represent the values of T(n) where n varies from 0
to n for the recurrence relations. For e.g. T(n) = T(n-1) + n,
T(0)
= 1, T(n) = T(n-1) + n^2, T(0) =1, T(n) = 2*T(n)/2 + n, T(1)=1.
15 Write a Program to store a function (polynomial/exponential),
and then evaluate the polynomial. (For example store f(x) = 4n3
+ 2n + 9 in an array and for a given value of n, say n = 5, evaluate
(i.e. compute the value of f(5)).

16 Write a Program to represent Graphs using the Adjacency

Matrices and check if it is a complete graph.

17 Write a Program to accept a directed graph G and compute the

in-degree and out-degree of each vertex.
18 Given a graph G, Write a Program to find the number of paths
of length n between the source and destination entered by the
user.

19 Given an adjacency matrix of a graph, write a program to

check whether a given set of vertices {v 1,v2,v3.....,vk} forms an
Euler path / Euler Circuit (for circuit assume vk=v1).

20 Given a full m-ary tree with i internal vertices, Write a Program

to find the number of leaf nodes.
 QUESTION 1 AND 2:
Write a program to create a SET A and determine the cardinality of
SET for an input array of elements(repetition allowed ) and perform the
following operations on the SET.

a) ismember (a, A): check whether an element belongs to set or

not and return value as true/false.
b) powerset(A): list all the elements of power set of A.
c) Subset: Check whether one set is a subset of other or not.
d) Union and Intersection of two Sets.
e) Complement: Assume Universal Set as per the input elements
from the user.
f) Set Difference and Symmetric Difference between two SETS
g) Cartesian Product of Sets.

//CODE
#include<iostream>
#include<cmath>
using namespace std;
void menu(char arr[],int i);
void Union(int n1, int n2, char arr[], char arr1[]);
void Intersection(int n1, int n2, char arr[], char arr1[]);
void difference(int n1, int n2, char arr[], char arr1[]);
bool is_subset(int n1, int n2, char arr[],char arr1[]);
bool is_member(int n1,char ch, char arr[]);
void Complement(int n1, int n2, char arr[], char arr1[]);
void subset(char arr[],int i);
void binary(int n,int num,char arr[]);
void disjoint(int n1,int n2, char arr[], char arr1[]);
void symmetric(int n1, int n2 , char arr[], char arr1[]);
int main(){
int i;
char arr[100];
cout<<"Enter the elements of your set1 and terminates by entering
character '%'"<<endl;
cin>>arr[0];
 for(i=1; arr[i-1]!='%';i++){
cin>>arr[i];
}
menu(arr,i);
return 0;

}
void menu(char arr[], int i)
{
int choice;
char
choose; do{
cout<<"Enter your choice\n1)Subset\n2)Union\n3)Intersection\
n4)Difference\n5)Check_S ubset or not\n6)Belong to\n7)Complement\
n8)disjoint sets\n9)Symmetric Difference\n";
cin>>choice;
if(choice==1){
subset(arr,i-1);
}
else if(choice==2){
int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
Union(i-1,a-1,arr,arr1);
}
else if(choice==3){
int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
Intersection(i-1,a-1,arr,arr1);
 }
else if(choice==4)
{
int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++)
{
cin>>arr1[a];
}
difference(i-1,a-1,arr,arr1);
}
else if(choice==5)
{
int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
bool sub;
sub=is_subset(i-1,a-1,arr,arr1);
if(sub){
cout<<"first set is the SUBSET of second set"<<endl;
}
else
{
cout<<"first set is not the SUBSET of second set"<<endl;
}
}
else if(choice==6)
{
char ch;
cout<<"Enter the element want to search in your set"<<endl;
cin>>ch;
bool T; T=is_member(i-1,ch,arr);
if(T)
{
cout<<"The element "<<ch<<" is BELONG to the set
"<<endl;
}
else
{
cout<<"The element "<<ch<<" is NOT Belong to the set
"<<endl;
}
}
else if(choice==7)
{
int a;
char arr1[100];
cout<<"Enter the elements of Universal set and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
Complement(a-1, i-1, arr1,arr);
}
else if(choice==8)
{
int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
disjoint(i-1,a-1,arr,arr1);
}
else if(choice==9){

int a;
char arr1[100];
cout<<"Enter the elements of your set2 and terminates by
entering character '%'"<<endl;
 cin>>arr1[0];
for(a=1; arr1[a-1]!='%';a++){
cin>>arr1[a];
}
symmetric(i-1,a-1,arr,arr1);
}
else
{
cout<<"INVALID CHOICE enter correct choice"<<endl;
}

cout<<"\nDo you want to choose more?(y/n):"<<endl;

cin>>choose;
}while(choose=='y');
return;
}

void Union(int n1, int n2, char arr[], char arr1[])

{
int i,j,k;
char un[n1+n2];
int count=0;
for(i=0; i<n1; i++){
un[i]=arr[i];
count++;
}
for(j=0; j<n2; j++){
bool flag=false;
for(k=0; k<n1; k++){
if(arr1[j]==arr[k]){
k=n1;
flag=true;
}
}
if(flag==false)
{
un[i]=arr1[j];
count++;
cout<<"i= "<<i<<endl;
cout<<"count= "<<count<<endl;
i++;
 }
}
cout<<"The union of the sets is\n";
for(int m=0; m<count; m++)
{
cout<<un[m]<<" ";
}
}
void Intersection(int n1, int n2, char arr[], char arr1[])
{
int i=0;
int j,k;
char inter[n1+n2];
for(j=0; j<n2; j+
+)
{
for(k=0; k<n1; k++)
{
if(arr1[j]==arr[k])
{
inter[i]=arr1[j];
i++;
}
}
}
cout<<"The intersection of the sets are:\n";
for(int r=0; r<i; r++)
{
cout<<inter[r]<<" ";
}

}
void difference(int n1, int n2, char arr[], char arr1[])
{
int i=0;
int j,k;
char differ[n1+n2];
for(j=0; j<n1; j++)
{
bool flag=false;
for(k=0; k<n2; k++)
{
 if(arr[j]==arr1[k])
{
k=n2;
flag=true;
}
}
if(flag == false)
{
differ[i]=arr[j];
i++;
}
}
cout<<"The difference of set1-set2 sets are:\n";
for(int r=0; r<i; r++)
{
cout<<differ[r]<<" ";
}
}
bool is_subset(int n1, int n2, char arr[],char arr1[])
{
int i,j,k;
int count=0;
for(i=0; i<n1; i+
+)
{
for(j=0; j<n2; j++)
{
if(arr[i]==arr1[j])
{
count++;
}
}
}
if(count==n1)
{
return true;
}
else
{
return false;
}
}
bool is_member(int n1,char ch, char arr[])
{
bool flag=false;
for(int i=0; i<n1; i++)
{
if(ch==arr[i])
{
flag=true;
}
}
if(flag==true){
return true;
}
else{
return false;
}
}
void Complement(int n1, int n2, char arr[], char arr1[])
{
int i=0;
int j,k;
char differ[n1+n2];
for(j=0; j<n1; j++)
{
bool flag=false;
for(k=0; k<n2; k++)
{
if(arr[j]==arr1[k])
{
k=n2;
flag=true;
}
}
if(flag == false)
{
differ[i]=arr[j];
i++;
}
}
cout<<"The difference of set1-set2 sets are:\n";
for(int r=0; r<i; r++)
 {
cout<<differ[r]<<" ";
}
}
void binary(int n,int num,char arr[])
{
int
a1[num];
int
a2[num];
while(n!=0)
{
for(int i=0; i<num; i++)
{
if(n%2==0)
{
a1[i]=0;
n=n/2;
}
else
{
a1[i]=1;
n=n/2;
}
}
}
int a=0;
for(int i=num-1; i>=0; i--)
{
a2[a]=a1[i];
if(a2[a]==1)
{
cout<<arr[a];
}
a++;
}
return;
}
void subset(char arr[], int i)
{
int subNo = pow(2,i);
for(int j=0; j<subNo ; j++)
{
 cout<<"{";
binary(j,i,arr);
cout<<"}";
cout<<endl;
}
return ;
}
void disjoint(int n1,int n2, char arr[], char arr1[])
{
bool flag = true;
for(int i=0 ; i<n1; i+
+)
{
for(int j=0; j<n2; j++)
{
if(arr[i]==arr1[j])
{
flag =
false;
break;
}
}
}
if(flag)
{
cout<<"The two sets are disjoint sets: "<<endl;
}
else
{
cout<<"The two sets are not disjoint"<<endl;
}
}
void symmetric(int n1, int n2 , char arr[], char arr1[])
{
int i=0;
int j,k;
int a,b;
int c=0;
char differ[n1+n2];
char differ1[n1+n2];
for(j=0; j<n1; j++)
{
bool flag=false;
 for(k=0; k<n2; k++)
{
if(arr[j]==arr1[k])
{
k=n2;
flag=true;
}
}
if(flag == false)
{
differ[i]=arr[j];
i++;
// cout<<"i= "<<i<<endl;
}
}
for(a=0; a<n2; a++)
{
bool flagi=false;
for(b=0; b<n1; b++)
{
if(arr1[a]==arr[b])
{
b=n1;
flagi=true;
}
}
if(flagi == false)
{
differ1[c]=arr1[a]; c+
+;
}
}
Union(i,c,differ,differ1);

}
OUTPUT:
 QUESTION 3 AND 4:
Create a class RELATION , use matrix notation to represent a
relation . Include functions to check if the relation is Reflexive,
Symmetric, Anti-symmetric and Transitive. Also include functions to
check whether the relation is Equivalence or Partial Ordering.

//CODE:
#include<iostream>
#include<cstring>
using namespace std;
class RELATION
{
int n;
int A[20],R[20][20];
public:
void
input()
{
cout<<"Enter the number of elements to find their relation:"<<endl;
cin>>n;
cout<<"Enter the elements of set
A:"<<endl; for(int i=0;i<n;i++)
{
cin>>A[i];
}
cout<<"Enter the relation matrix in (0/1) format"<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>R[i][j];
}
}
void print()
{
cout<<"The elements of set
A:"<<endl; cout<<"{";
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
cout<<",";
}
cout<<"}";
cout<<"The relation matrix
:"<<endl; for(int i=0;i<n;i++)
 {
for(int j=0;j<n;j++)
{
cout<<R[i][j]<<" ";
}
cout<<endl;
}
}
int reflexive()
{
int r=1;
for(int i=0;i<n;i++)
{
if(R[i][i]!=1)
{ r=
0;
break;
}
}
return r;
}
int symmetric()
{
int s=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(R[i][j] != R[j][i])
{

s=0;
break;}
}}
return s;
}
int anti_symmetric()
{
int ans=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(R[i][j] == R[j][i])
{

ans=0;
 break;}
}}
return ans;
}
int transitive()
{
int tr=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
if((R[i][j]==1 && R[j][k]==1) && R[i][k]!=1)
{

tr=0;
break;}
}}}
return tr;
}

};
int main()
{
RELATION re;
re.input();
re.print();
int r=1;
r=re.reflexive();
if(r==1)
cout<<"The relation is reflexive"<<endl;
else
cout<<"The relation is not
reflexive"<<endl; int s=1;
s=re.symmetric();
if(s==1)
cout<<"The relation is
Symmetric"<<endl; else
cout<<"The relation is not symmetric"<<endl;
int ans=1;
ans=re.anti_symmetric();
if(ans==1 )
cout<<"The relation is AntiSymmetric"<<endl;
else
cout<<"The relation is not Antisymmetric"<<endl;
int tr=1;
 tr=re.transitive();
if(tr==1)
cout<<"The relation is Transitive"<<endl;
else
cout<<"The relation is not Transitive"<<endl;
if(r==1 && s==1 && tr==1)
cout<<"The relation is an Equivalence relation"<<endl;
else
cout<<"The relation is not an Equivalence relation"<<endl;
if(r==1 && ans==1 && tr==1)
cout<<"The relation is partial ordering relation"<<endl;
else
cout<<"The relation is not a partial ordering relation"<<endl;
return 0;
}
OUTPUT:
 QUESTION 5:

Write a program to generate the Fibonacci series

using recursion.

//CODE
#include<iostream>
using namespace std;
int fibonacci(int n)
{
if(n==0)
{
return (n);
}
else if(n==1)
{
return n;
}
els
e
{ return(fibonacci(n-1)+fibonacci(n-2));

}
}

int main()
{
int x, i=0;
cout<<"\n Enter the number of terms: ";
cin>>x;
cout<<" Fibonacci series upto "<<x<<" terms: ";
while(i<x)
{
cout<<" "<<fibonacci(i);
i++;
}
return 0;
}
OUTPUT:
 QUESTION 6:
Write a Program to implement Tower of Hanoi
using recursion.

//CODE
#include<iostream>
using namespace std;

//tower of HANOI function implementation

void TOH(int n,char Sour, char Aux,char Des)
{
if(n==1)
{
cout<<"Move Disk "<<n<<" from "<<Sour<<" to
"<<Des<<endl;
return;
}

TOH(n-1,Sour,Des,Aux);
cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
TOH(n-1,Aux,Sour,Des);
}

//main program
int main()
{
int n=0;

cout<<"Enter no. of
disks:"; cin>>n;
//calling the TOH
TOH(n,'A','B','C');

return 0;
}
OUTPUT:
 QUESTION 7:

Write a program to implement Binary Search using recursion.

//CODE
#include<iostream>
#include<iomanip>
using namespace std;

int binarysearch(int a[],int i,int j,int p)

{

if(j>=i )
{

int m=i+(j-i)/2;
if(a[m]==p)
return m;
if(a[m]>p)
return binarysearch (a,i,m-1,p);
else
return binarysearch(a,m+1,j,p);}
return -1;

int main()
{
int arr[100];
int n=0;

cout<<"Enter the number of elements of the list:"<<endl;

cin>>n;
cout<<"Enter the elements of the list in the increasing
order:"<<endl;
for(int k=0;k<n;k++)
{
cin>>arr[k];
 }
int x=0;
cout<<"Enter the element to be searched:"<<endl;
cin>>x;

int result=0;

result= binarysearch(arr,0,n,x);

(result==-1)? cout<<"Element "<< setw(2)<< x<<"is not found in

the list":cout<<"Element "<<setw(2)<< x<<" is found at position
"<<setw(2)<< result+1;
return 0;

OUTPUT:
 QUESTION 8:

Write a Program to implement Bubble Sort. Find the number

of comparisons during each pass and display the intermediate
result.
//CODE
#include<iostream>
using namespace std;
void swap(char *x,char *y)
{
char temp=*x;
*x=*y;
*y=temp;
}
void Bubblesort(int a[], int size)
{
int i,j=0;
for( i=0;i<size;i++)
{
for( j=0;j<size-i-1;j++)
{
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
}
cout<<"\n After"<< (i+1)<<"pass:"<<endl;
for(j=0;j<size;j++)
{
cout<<a[j]<<" ";
}
cout<<endl;
}

}
int main()
{
int n=0;
int arr[100];
cout<<"Enter the size of the array:"<<endl;
cin>>n;
 cout<<"Enter the elements of the array:"<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];}
cout<<"Before sorting"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
Bubblesort(arr,n);
cout<<"\n After sorting"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
}
OUTPUT:
 QUESTION 9:

Write a program to implement Insertion sort. Find the

number of comparisons during each pass and display the
intermediate result. Use the observed values to plot a
graph to analyse the complexity of algorithm.

//CODE

#include<iostream>
using namespace std;
void Insertion_sort(int a[],int size)
{
int i,j,k=0;
for(i=1;i<=size-1;i++)
{
k=a[i];
j=i-1;
while(j>=0 && a[j]>k)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=k;
cout<<"\n After pass"<<(i)<<endl;
for(j=0;j<size;j++)
{
cout<<a[j]<<" ";
}
cout<<endl;
}
}
int main()
{
int n=0;
 int arr[100];
cout<<"Enter the size of the array:"<<endl;
cin>>n;
cout<<"Enter the elements of the array:"<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"Before sorting"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
Insertion_sort(arr,n);
cout<<"\n After sorting"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
}

OUTPUT:
 QUESTION 10:

Write a program that generates all the permutations of a

given set of digits,with or without repetition.(For example,if
the given set is {1,2},the permutation are 12 and 21).(One
method is given in liu).

//CODE
#include<iostream>
#include<cstring> using
namespace std;

double factorial(int num)

{
if(num<0)
return 0;
else if(num==0||num==1)
return 1;
else
return num*factorial(num-1);
}
void swap(char *x, char *y)
{
char temp;
temp =
*x;
*x = *y;
*y = temp;
}
void permute(char *a, int l, int r)
{
 int i;
if(l==r)
{
cout<<a<<endl;
}
els
e
{ for(i=l; i<=r; i++ )
{
swap((a+l),(a+i));
permute(a, l+1, r);
swap((a+l), (a+i));
}
}
}

int main()
{
char str[10];
int size;
cout<<" Enter the size of array: ";
cin>>size;
cout<<" Total number of permutations will be: ";
cout<<factorial(size);
cout<<"\n Enter the elements of the array: \n";for(int
i=0; i<size; i++)
{
cin>>str[i];
}
cout<<"\n PERMUTATIONS are: \n";
permute(str, 0, size-1);
 return 0;
}

OUTPUT:
 QUESTION 11:

Write a program to calculate permutation and combination

for an input value n and r using recursive formula of nCr and
nPr.

//CODE
#include<iostream>
using namespace std;

double permutation(int
a, int b);
double combination(int
a, int b);
double factorial(int
num)
{
if(num<0)
return 0;
else
if(num==0||num==1)
return 1;
else
return
num*factorial(num-1);
}

double permutation(int
a, int b)
{
cout<<"\n
Permutation for
"<<a<<" and "<<b<<"
is: "<<a<<"P"<<b<<" =
"<<factorial(a)/factorial
(a-b);
}

double combination(int
a, int b)
{
cout<<"\n
Combination for
"<<a<<" and "<<b<<"
is: "<<a<<"C"<<b<<" =
"<<factorial(a)/(factoria
l(b)*factorial(a-b));
}

int main()
{
int n, r;
char ch;
cout<<" Enter the
value or n and r
respectively: ";
cin>>n>>r;
cout<<"\n MENU:
\n 1. Press 1 to calculate
the permutation for
input values of n and
r.";
cout<<" \n 2. Press
2 to calculate the
combination for input
values of n and r.";
do
{
int v;
cout<<"\n
Choose any operation (1
or 2) :";cin>>v;
switch(v)
{
case 1:

{permutation(n,r);

break;}
case 2:
{combination(n,r);

break;}
default:

{cout<<"\n TRY
AGAIN!! \n";}

}
cout<<"\n Do
you want to continue
(Y/N):";cin>>ch;
}
while((ch=='Y')||(c
h=='y'));
return 0;
}

OUTPUT:
 QUESTION 12:

For any number n, write a program to list all the solutions

ofthe 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;

class Combos

public:

//Function to diaplay

combination void display (int

b[],int n)

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

+) cout<<b[i]<<" ";

//Function to calculte possible combination

int combos(int b[],int k,int n,int s)

if (k==0)

b[k]=s;
display(b,n);
 cout<<"\n";

return 0;

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

b[k]=i;

combos(b,k-1,n,s-i);

};

int main()

Combos obj;

int s,n;

cout<<"Enter the no. of groups

::"; cin>>n;

cout<<"Enter the sum

::"; cin>>s;

int b[n];

obj.combos(b,n-1,n,s);

return 0;}
OUTPUT:
 QUESTION 13:

Write a Program to accept the truth values of variables x

and y, and print the truth table of the following
logical operations:
a) Conjunction f) Exclusive NOR
b) Disjunction g) Negation
c) Exclusive OR h) NAND
d) Conditional i) NOR
e) Bi-conditional

//CODE
#include<iostream>
using namespace std;
int main()
{
int n;
char x,y;
cout << "Enter the no. of trials:
"; cin >> n;
bool value[n][2];
for(int i=0; i<n; i++)
{
cout << "Enter the truth value for x" << i+1 << " y" << i+1
<< ": ";
cin >> x >> y;
value[i][0] = (x == 't' || x == 'T');
value[i][1] = (y == 't' || y == 'T');
}
cout << endl;
cout << "x\ty\tAND\tOR\tXOR\tx->y\tx<-
>y\tXNOR\tNOT\tNAND\tNOR";
cout << "\n------------------------------------------------------"
<< " \n";

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

 {
int x = value[i][0], y = value[i][1];
cout << (x ? "T" : "F") << "\t" << (y ? "T" : "F") << "\t"
<< ((x && y) ? "T" : "F") << "\t"
<< ((x || y) ? "T" : "F") << "\t"
<< (((x || y) && !(x && y)) ? "T" : "F") << "\t"
<< ((!x || y) ? "T" : "F") << "\t"
<< (((!x || y) && (!y || x)) ? "T" : "F") << "\t"
<< ((!((x || y) && !(x && y))) ? "T" : "F") << "\t"
<< ((!x) ? "T" : "F") << " " << ((!y) ? "T" : "F") << "\t"
<< (!(x && y) ? "T" : "F") << "\t"
<< (!(x || y) ? "T" : "F") << "\n";
cout << endl;
}

return 0;
}
OUTPUT:
 QUESTION 14:

Write a program to accept an input n from the user and

graphically represent the values of T(n) where n varies from
0 to n for the recurrence relations. For e.g. T(n) = T(n-1) + n,
T(0) = 1, T(n) = T(n-1) + n^2, T(0) =1,T(n) = 2*T(n)/2 + n,
T(1)=1.

//CODE
#include<iostream>
using namespace
std;

int firstRecurrence(int n)
{
if(n == 0)
return 1;
return
firstRecurrence(n-1) +
n;
}

int secondRecurrence(int n)
{
if(n == 0)
return 1;
return
secondRecurrence(n-1)
+ n*n;
}

int thirdRecurrence(int n)
{
if(n == 1)
return 1;
return 2 *
thirdRecurrence(n/2) +
n;
}

int main()
{
int n,ch;
cout << "\nChoose
recurrence relation to
evaluate:\n"
<< "(1) T(n) = T(n
- 1) + n and T(0) = 1\n"
<< "(2) T(n) =
T(n - 1) + n^2 and T(0) =
1\n"
<< "(3) T(n) =
2 * T(n / 2) + n and T(1) =
1\n";
cout << "Enter
the choice: ";
cin >> ch;

switch(ch)
{
case 1:
cout <<
"\nEnter the value of n: ";
cin >>
n; cout
<<
"\nValues for T(n) = T(n -
1) + n:\n";
for(int
i=0; i<=n; i++)
{
if(i
== 0)

cout << "T(0) = " <<

firstRecurrence(i) << endl;

else

cout << "T(" << i

<< ") = T(" << (i-1) << ")
+"

<< i << " = "

<<
firstRecurrence(i) << endl;
}
break;
case 2:
 cout <<
"\nEnter the value of n: ";
cin >>
n; cout
<<
"\nValues for T(n) = T(n -
1) + n^2:\n";
for(int
i=0; i<=n; i++)
{
if(i
== 0)

cout << "T(0) = " <<

secondRecurrence(i) <<
endl;

else

cout << "T(" << i <<

") = T(" << (i-1) << ") + "

<< i*i << " = "

<<
secondRecurrence(i) <<
endl;
}
break;

case 3:
cout <<
"\nEnter the value of n: ";
cin >>
n; cout
<<
"\nValues for T(n) = 2 *
T(n / 2) + n:\n";
for(int
i=1; i<=n; i++)
{
if(i
== 1)

cout << "T(1) = " <<

thirdRecurrence(i) << endl;
 else

cout << "T(" << i <<

") = 2 * T(" << i << " / 2)
+"

<< i << " = " << "2 * T("

<< i/2 << ") + "

<< i << " = "

<<
thirdRecurrence(i) << endl;
}
break;

default:
cout <<
"\nWrong choice!!!";
break;
}

return 0;
}

OUTPUT:
 QUESTION 15:

Write a Program to store a function (polynomial/exponential), and

then evaluate the polynomial. (For ex: store f(x) = 4n3 + 2n + 9 in an
array and for a given value of n, say n = 5, evaluate (i.e. compute the
value of f (5)).

//CODE
#include<iostream>
#include <cstdlib>
#include <cmath> using
namespace std;int
main(){
int n,x,p=0;
float polysum;
int A[100];
cout<<"enter the degree of polynomial"<<endl;
cin>>n;
cout<<"enter"<< (n+1)<<"coefficents"<<endl;
for(int i=0;i<=n;i++){
cin>>A[i];

}
p=n;
cout<<"the required polynomial is:"<<endl;
for(int i=0;i<=n;i++){
if(p<0){
break;
}
 if(A[i]>0)
cout<<"+";
else if (A[i])
cout<<"-";
else
cout<<" ";
cout<<abs(A[i])<<"n"<<"^"<<p--;

}
cout<<"enter the value of x:"<<endl;
cin>>x;
polysum=A[0]; for(int
i=1;i<=n;i++){
polysum=polysum*x+A[i];
}
cout<<"sum of polynomials is:"<<"
"<<"f("<<x<<")"<<"=";
cout<<polysum;
}

OUTPUT:
 QUESTION 16:

Write a program to represent Graphs using the

Adjacency matrices and check if it is a complete graph.

//CODE
#include<iostream>
#include<iomanip>
using namespace std;
int arr[20][20];
void createAdjMatrix(int m)
{

// Initialise all value to 0for

(int i = 0; i < m; i++) {

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

arr[i][j] = 0;
}
}}
void add_edge(int u,int v,int c)
{

if(c==1) arr[u]
[v]=1; else if
(c==0)
{
arr[u][v]=1;
arr[v][u]=1;
}
}

void print_adjacencymatrix(int m)
{
cout<<"\n\n"<<setw(4)<<"";
for(int i=0;i<m;i++)
 cout<<setw(3)<<"("<<i+1<<")";cout<<"\n\n";
for(int i=0;i<m;i++)
{

cout<<setw(3)<<"("<<i+1<<")";
for(int j=0;j<m;j++)
{

cout<<setw(4)<<arr[i][j]<<" ";
}
cout<<endl;
}
}

int main()
{

int v[10];

int n,e=0;
cout<<"Enter the number of vertices "<<endl;
cin>>n;
cout<<"Enter the vertices:"<<endl;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cout<<"Enter the number of edges:"<<endl;
cin>>e;
int a[e][2];

cout<<" Enter the edges :"<<endl;

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

cin>>a[i][0]>>a[i][1];
}
int option,i=0;
cout<<"The edges are Directed or undirected -Enter 1 ifDirected
or else 0:"<<endl;
cin>>option;
cout<<"The edges
are:"<<endl; cout<<"{";
for( i=0;i<e;i++)
{

if(option==1)
{ cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}
else if(option==0)
{

cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<","<<"("<<a[i][1]<
<","<<a[i][0]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}

}cout<<"}";

cout<<" \n THE ADJACENCY MATRIX OF THE

GRAPH"<<endl;
print_adjacencymatrix(n);int
check,check1=0;
for( i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)
{
if(arr[i][j]==0)
check=0;
 }
els
e
{ if(arr[i][j]==0)
check1=1;
}

if(check==0 && check1==0)

cout<<"A complete
Graph"<<endl;else
cout<<"Not a Complete GRaph"<<endl;
}

OUTPUT:
 QUESTION 17:

Write a Program to accept a directed graph G and

compute the in-degree and out-degree of each vertex.

//CODE
#include<iostream>
#include<iomanip>
using namespace std;
int arr[20][20];
void createAdjMatrix(int m)
{

// Initialise all value to 0

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

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

arr[i][j] = 0;
}
}}
void add_edge(int u,int v,int c)
{

if(c==1) arr[u]
[v]=1; else
if(c==0)
{
arr[u][v]=1;
arr[v][u]=1;
}}
void print_adjacencymatrix(int m)
{
cout<<"\n\n"<<setw(4)<<"";
for(int i=0;i<m;i++)

cout<<setw(3)<<"("<<i+1<<")";cout<<"\n\n";
for(int i=0;i<m;i++)
{

cout<<setw(3)<<"("<<i+1<<")";
for(int j=0;j<m;j++)
{

cout<<setw(4)<<arr[i][j]<<" ";
}
cout<<endl;
}
}

int main()
{

int v[10];

int n,e=0;
cout<<"Enter the number of vertices "<<endl;
cin>>n;
cout<<"Enter the vertices:"<<endl;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cout<<"Enter the number of edges:"<<endl;
cin>>e;
int a[e][2];

cout<<" Enter the edges :"<<endl;

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

cin>>a[i][0]>>a[i][1];

}
int option,i=0;
cout<<"The edges are Directed or undirected -Enter 1 ifDirected
or else 0:"<<endl;
cin>>option;

cout<<"The edges
are:"<<endl; cout<<"{";
for( i=0;i<e;i++)
{

if(option==1)
{ cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}
else if(option==0)
 {

cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<","<<"("<<a[i][1]<
<","<<a[i][0]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}

}cout<<"}";

cout<<" \n THE ADJACENCY MATRIX OF THE

GRAPH"<<endl;
print_adjacencymatrix(n);

int insum,outsum=0;
for(int i=0;i<n;i++)
{
insum=0;

for(int j=0;j<n;j++)
{
insum=arr[j][i]+insum;

}
cout<<"The in-Degree of
vertex ("<<i+1<<")"<<":";
cout<<insum;
cout<<endl;

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

for(int j=0;j<n;j++)
{
outsum=arr[i][j]+outsum;

}
cout<<"The out-Degree of vertex
("<<i+1<<")"<<":";
cout<<outsum;
cout<<endl;

}}

OUTPUT:
 QUESTION 18:

Given a graph G, write a Program to find the number of

paths of length n between the source and destination
entered by the user.

//CODE
#include<iostream>
#include<iomanip>
using namespace std;int
arr[20][20];
int h[10][10];
void productMatrix(int x,int y)
{
int p[y][y];
int mul[y][y];
if(x==1)
{

for(int i=0;i<y;i++)
{
for(int j=0;j<y;j++)
{
h[i][j]=arr[i][j];

}
}
}
else
{
for(int i=0;i<y;i++)
{
for(int j=0;j<y;j++)
{
mul[i][j]=0;
 for(int k=0;k<y;k++)
{
mul[i][j]+=arr[i][k]*arr[k][j]; p[i]
[j]=mul[i][j];
h[i][j]=p[i][j];
}
}
}
}
if(x!=1)
{
for(int d=0;d<x/2-1;d++)
{
for(int i=0;i<y;i++)
{
 for(int j=0;j<y;j++)
{
mul[i][j]=0;
for(int k=0;k<y;k++)
{
mul[i][j]+=p[i][k]*p[k][j]; h[i]
[j]=mul[i][j];
}
}
}
}
if(x%2!=0)
{
for(int i=0;i<y;i++)
{
for(int j=0;j<y;j++)
{
mul[i][j]=0;
for(int k=0;k<y;k++)
{
mul[i][j]+= h[i][k]*arr[k][j];
h[i][j]=mul[i][j];
}
}
}
}

}
for(int i=0;i<y;i++)
{
for(int j=0;j<y;j++)
 {
cout<<setw(4)<<h[i][j]<<" ";
}

cout<<endl;
}
}

void createAdjMatrix(int m)
{

// Initialise all value to 0for

(int i = 0; i < m; i++) {

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

arr[i][j] = 0;
}
}}
void add_edge(int u,int v,int c)
{

if(c==1) arr[u]
[v]=1; else if
(c==0)
{
arr[u][v]=1;
arr[v][u]=1;
}
}

void print_adjacencymatrix(int m)
{
cout<<"\n\n"<<setw(4)<<"";
for(int i=0;i<m;i++)

cout<<setw(3)<<"("<<i+1<<")";cout<<"\n\n";
for(int i=0;i<m;i++)
{

cout<<setw(3)<<"("<<i+1<<")";
for(int j=0;j<m;j++)
{

cout<<setw(4)<<arr[i][j]<<" ";
}
cout<<endl;
}
}

int main()
{

int v[10];

int n,e=0;
cout<<"Enter the number of vertices "<<endl;
cin>>n;
cout<<"Enter the vertices:"<<endl;
for(int i=0;i<n;i++)
{
 cin>>v[i];
}
cout<<"Enter the number of edges:"<<endl;
cin>>e;
int a[e][2];

cout<<" Enter the edges :"<<endl;

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

cin>>a[i][0]>>a[i][1];

}
int option,i=0;
cout<<"The edges are Directed or undirected -Enter 1 ifDirected
or else 0:"<<endl;
cin>>option;

cout<<"The edges
are:"<<endl; cout<<"{";
for( i=0;i<e;i++)
{

if(option==1)
{ cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}
else if(option==0)
{
 cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<","<<"("<<a[i][1]<
<","<<a[i][0]<<")"<<",";
add_edge(--a[i][0],--a[i][1],option);
}

}cout<<"}";

cout<<" \n THE ADJACENCY MATRIX OF THE

GRAPH"<<endl;
print_adjacencymatrix(n);int
srcv,desv,len=0;
cout<<"Enter the source vertex :"<<endl;
cin>>srcv;
cout<<"Enter the destination vertex :"<<endl;
cin>>desv;
cout<<"Enter the length of the path :"<<endl;
cin>>len;
cout<<"\n THE RESULTANT MATRIX:"<<endl;
productMatrix(len,n);

cout<<"The number of paths of length

len from"<<"("<<srcv<<")"<<"to"<<"("<<desv<<"):";
cout<<h[--srcv][--desv];
}
OUTPUT:
 QUESTION 19:

Given an adjacency matrix of a graph, write a program to

check whether a given set of vertices {v 1,v2,v3.....,vk} forms an
Euler path / Euler Circuit (for circuit assume vk =v1).

//CODE
#include<iostream>
#include<iomanip>
using namespace std;
int arr[20][20];
void createAdjMatrix(int m)
{

// Initialise all value to 0

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

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

arr[i][j] = 0;
}
}}
void add_edge(int u,int v)
{

arr[u][v]=1;
arr[v][u]=1;

void print_adjacencymatrix(int m)
{
cout<<"\n\n"<<setw(4)<<"";
for(int i=0;i<m;i++)

cout<<setw(3)<<"("<<i+1<<")";
cout<<"\n\n";
 for(int i=0;i<m;i++)
{

cout<<setw(3)<<"("<<i+1<<")";
for(int j=0;j<m;j++)
{

cout<<setw(4)<<arr[i][j]<<" ";
}
cout<<endl;
}
}

int main()
{

int v[10];

int n,e=0;
cout<<"Enter the number of vertices "<<endl;
cin>>n;
cout<<"Enter the vertices:"<<endl;
for(int i=0;i<n;i++)
{
cin>>v[i];
}
cout<<"Enter the number of edges:"<<endl;
cin>>e;
int a[e][2];

cout<<" Enter the edges :"<<endl;

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

cin>>a[i][0]>>a[i][1];

}
 cout<<"The edges
are:"<<endl; cout<<"{";
for( int i=0;i<e;i++)
{

cout<<"("<<a[i][0]<<","<<a[i][1]<<")"<<","<<"("<<a[i][1]<<","
<<a[i][0]<<")"<<",";
add_edge(--a[i][0],--a[i][1]);
}
cout<<"}";

cout<<" \n THE ADJACENCY MATRIX OF THE

GRAPH"<<endl;
print_adjacencymatrix(n);
int sum=0;
int b[10];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(arr[i][j]==1)
{
sum++;
}
}
b[i]=sum;
}
int k=0;
for(int i=0;i<n;i++)
{
if(b[i]%2!=0)
{

k++;}
}

if(k>2)
 {

cout<<"Not an euler path"<<endl;}

else
{

cout<<"An euler path"<<endl;

if(k==0)
{

cout<<"An euler circuit"<<endl;}

else
{

cout<<"Not an euler circuit"<<endl;}

}
return 0;
}

OUTPUT:
 QUESTION 20:

Given a full m-ary tree with i internal vertices, write a

Program to find the number of leaf nodes.

//CODE
#include<iostream>
using namespace std;int
main()
{

int m,i,n=0;
cout<<"Enter the value of m"<<endl;
cin>>m;
cout<<"Enter the number of internal vertices"<<endl;cin>>i;
n=m*i+1;
cout<<"The number of leaf nodes of the
tree"<<endl; cout<<((m-1)*n+1)/m;
return 0;
}
OUTPUT: