Notes

Experiment No: 1.1
Objective: TO IMPLEMENT CONJUNCTION, DISJUNCTION AND NEGATION


Here's a complete example that uses these logical operators in C:

```c
#include <stdio.h>

int main() {
int x = 5;
int y = 10;

if (x > 0 && y < 20) {
printf("Both conditions are true.n");
}

if (x == 0 || y == 0) {
printf("At least one condition is true.n");
}

if (!(x < 0)) {
printf("Negation of x < 0 is true (x >= 0).n");
}

return 0;
}
```

In this example, we use conjunction to check if both `x > 0` and `y < 20` are true, disjunction to check if at least one of `x == 0` or `y == 0` is true, and negation to check if `x` is not less than 0 (i.e., `x >= 0`).
Demonstration
3.1.Program 1
To implement conjunction, disjunction and negation in c program.
Source Code:
#include<stdio.h>
#include<stdbool.h>
bool conjunction (bool a, bool b){
return a&&b;
}
bool disjunction (bool a, bool b){
return a||b;
}
bool negation (bool a){
return !a;
}
void display (bool a){
if(a==true){
printf("Tt");
}
else{
printf("Ft");
}
}
int main(){
int i;
bool res;
bool a[]={true,true,false,false};
bool b[]={true,false,true,false}; printf("npt!ptqt!qtp^qtpvqn");
printf("------------------------------------------------n");
for(i=0;i<4;i++){
display(a[i]);
res=negation(a[i]);
display(res);
display(b[i]);
res=negation(b[i]);
display(res);
res=conjunction(a[i],b[i]);
display(res);
res=disjunction(a[i],b[i]);
display(res);
printf("n");
}
}
Output and discussion
In the above program, we have implemented the conjunction, disjunction and then negation using c programming.
Conclusion
Hence, the conjunction, disjunction and then negation was implemented using c programming and dev c.






Experiment No: 1.2
Objective: TO IMPLEMENT IMPLICATION AND BICONDITIONAL IN C PROGRAMMING LANGUAGE
• To study how to implement implication and biconditional in C language.
Theory
Certainly! In C language, you can implement implication and biconditional (if and only if) logical operations using the following functions:

1. **Implication (`implies`) function:**

```c
#include <stdbool.h>

bool implies(bool a, bool b) {
return !a || b;
}
```

The implication (`implies`) function returns `true` if either the first condition is `false` or the second condition is `true`, effectively implementing the implication operation (`a -> b`).

2. **Biconditional (`iff`) function:**

```c
#include <stdbool.h>

bool iff(bool a, bool b) {
return (a && b) || (!a && !b);
}
```

The biconditional (`iff`) function returns `true` if both conditions are either `true` or `false`, effectively implementing the biconditional operation (`a <-> b`).



Demonstration
3.1.Program 1
To demonstrate the implication and biconditional logic and execute it. Source Code:
#include<stdio.h>
#include<stdbool.h>
bool conjuction(bool a,bool b){
return a&&b;
}
bool disjunction(bool a, bool b){
return a||b;
}
bool implication(bool a,bool b){
return !a||b;
}
bool bicondition(bool a, bool b){
return (!a||b)&&(!b||a);
}
void display(bool a){
if(a==true){
printf("Tt");
}
else{
printf("Ft");
}
}
int main(){
int i;
bool res;
bool a[]={true,true,false,false};
bool b[]={true,false,true,false};
printf("nptqtp^qtpvqtp->qtp<->qn");
printf("------------------------------------------------n");




for(i=0;i<4;i++){
display(a[i]);
display(b[i]);
res=conjuction(a[i],b[i]);
display(res);
res=disjunction(a[i],b[i]);
display(res);
res=implication(a[i],b[i]);
display(res);
res=bicondition(a[i],b[i]);
display(res);
printf("n");
}
}
Output and discussion

In the above program, we have implemented implication and bi-conditional.


Conclusion
Hence, implication and bi-conditional logic are executed using the Dev C++.






Experiment No: 1.3
Objective: TO GENERATE THE TRUTH TABLE OF [P->Q^Q->R]->[P- >R]
• To generate the Truth table of proposition [p->q^q->r]->[p->r].
Theory
A truth table is a logical tool used in propositional logic and boolean algebra to systematically evaluate and analyze the truth values of compound propositions (statements) based on the truth values of their constituent propositions and logical operators. It lists all possible combinations of truth values for the input propositions and shows the resulting truth value of the compound proposition for each combination. In a truth table, you represent each input proposition (e.g., p, q, r) and the compound proposition (e.g., [p->q^q->r]->[p->r]) and then list all possible truth value combinations for the input propositions. For each combination, you evaluate the compound proposition to determine its truth value.
Here's the truth table for the proposition [p->q^q->r]->[p->r]:
p
q
r
p->q
q->r
p->r
p->q^q->r
[p->q^q->r]->[p->r]
T
T
T
T
T
T
T
T
T
T
F
T
F
F
F
T
T
F
T
F
T
T
F
T
T
F
F
F
T
F
F
T
F
T
T
T
T
T
T
T
F
T
F
T
F
T
F
T
F
F
T
T
T
T
T
T
F
F
F
T
T
T
T
T


In the truth table above:
- p, q, and r represent the truth values of three propositions.
- p->q, q->r, q^q->r, and p->r represent intermediate steps in evaluating the compound proposition.
- [p->q^q->r]->[p->r] represents the final compound proposition we want to evaluate. The last column in the table shows the truth values of the compound proposition for all possible combinations of truth values for p, q, and r. In this case, the compound proposition is always true for all combinations of truth values, which means it is a tautology.

Demonstration
3.1.Program 1
To demonstrate the truth table of proposition [p->q^q->r]->[p->r] and execute it. Source Code:
#include <stdio.h>
#include <stdbool.h>
// Function to evaluate the proposition [p->q^q->r]->[p->r]
bool implication(bool a, bool b){
return (!a||b);
}
bool conjuction(bool a, bool b){
return a&&b;
}
void display(bool a){
if(a==true)
printf("Ttt");
else
printf("Ftt");
}
int main(){
bool p[]={true,true,true,true,false,false,false,false};
bool q[]={true,true,false,false,true,true,false,false};
bool r[]={true,false,true,false,true,false,true,false};
int i;
bool pq,qr,pr,con,imp;
printf("nPtQtRtP->QtQ->RtP->Rt[P->Q^Q->R]t[P->Q^Q->R]->[P->R]n"); printf("-------------------------------------------------------------n");
for(i=0;i<8;i++){
display(p[i]);
display(q[i]);
display(r[i]);
pq=implication(p[i],q[i]);
display(pq);
qr=implication(q[i],r[i]);
display(qr);
pr=implication(p[i],r[i]);
display(pr);
con=conjuction(pq,qr);
display(con);
imp=implication(con,pr);
display(imp);
printf("n");
}
return 0;
}
Output and discussion


In the above program, we have implemented the proposition [p->q^q->r]->[p->r] and displayed its truth table.
Conclusion
hence, the proposition [p->q^q->r]->[p->r] are executed using the Dev C++.
Experiment 1.4
OBJECTIVE: TO CHECK WHETHER THE GIVEN PREPOSITION IS TAUTOLOGY, CONTRADICTION, OR CONTINGENCY.
• To learn when a preposition is said to be a tautology preposition.
• To learn when a preposition is called a contradiction preposition.
• To learn when a preposition is known as a contingency preposition

THEORY:
1. **Tautology :** A tautology is a statement that is always true, regardless of the circumstances or the truth values of its components. It is a redundancy in language or logic. For example, the statement "All humans are mammals or not all humans are mammals" is a tautology because it is always true. Eg: p v ⌐p For example the statement-pair: “All humans are mammals.”
2. **Contradiction :** A contradiction is a statement that is always false, regardless of the circumstances or the truth values of its components. It represents an inconsistency or logical error. For example, the statement "The sky is both completely sunny and completely cloudy at the same time" is a contradiction because it cannot be true. Eg: p ^⌐p For example the statement-pair: "All ball are black," and "It is not true that all ball are black" is contradictory.
3. **Contingency :** Contingency refers to a statement whose truth value depends on specific conditions or circumstances. It is neither always true (tautology) nor always false (contradiction). An example of contingency is the statement "It will rain tomorrow." This statement can be true or false depending on the actual weather conditions on the following day. In other words, it is logically possible for the statement to be true and it is also logically possible for it to be false. Eg: ⌐p ^ ⌐q
Program No 1: For Tautology Preposition
Source code:
#include <stdio.h>
#include<stdbool.h>
void display(bool n)
{
if (n==1)
printf ("T t");
else
printf ("F t");
}


void display(bool n);
int main(){
bool p[]={0,0,1,1};
bool q[]={0,1,0,1};
int i;
printf("ptqtp^qtpv~(p^q)n");
printf("---------------------------------------------------n"); for(i=0;i<4;i++){
display (p[i]);
display (q[i]);
display (p[i]&&q[i]);
display (p[i]||!(p[i]&&q[i]));
printf("n");
}
}
Output:

Program No 2: For Contingency Preposition.
Source Code:
#include <stdio.h>
#include<stdbool.h>
void display(bool n){
if (n==1)
printf (" T t");
else
printf (" F t");
}
void display(bool n);
int main(){
bool p[]={0,0,0,0,1,1,1,1};
bool q[]={0,0,1,1,0,0,1,1};


bool r[]={0,1,0,1,0,1,0,1};
int i;
printf(" pt qt rt p^qt p^q-->rn");
printf("--------------------------------------------n");
for(i=0;i<8;i++){
display (p[i]);
display (q[i]);
display (r[i]);
display (p[i]&&q[i]);
display (!(p[i]&&q[i])||r[i]);
printf("n");
}
}
Output:

Program 3: For contradiction preposition.
Source Code:
#include <stdio.h>
#include<stdbool.h>
void display(bool n){
if (n==1)
printf ("T t");
else
printf ("F t");
}
void display(bool n);
int main(){
bool p[]={0,0,1,1};
bool q[]={0,1,0,1};
int i;
printf("ptqtpvqt (~p^~q)t (pvq)^(~p^~q)n");
printf("---------------------------------------------------n");
for(i=0;i<8;i++)
{
display (p[i]);
display (q[i]);
display (p[i]||q[i]);
printf(" ");
display ((!p[i])&&(!q[i]));
printf("tt");
display ((p[i]||q[i])&&(!p[i])&&(!q[i]));
printf("n");
}
}
Output:





Discussion:
Here we have written 3 different programs to check whether the given preposition is tautology, contradiction or contingency. 1st program was written to check for tautology, 2nd for contingency and 3rd for contradiction.
Conclusion:
After doing the above experiment, we have become able to distinguish whether the given preposition is a tautology, contradiction, or contingency.












Experiment 2.1
Objective: TO IMPLEMENT THE EUCLIDEAN ALGORITH IN C PROGRAM
Theory :
The Euclidean Algorithm is a fundamental algorithm in number theory used to find the greatest common divisor (GCD) of two integers. The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder. The algorithm is named after the ancient Greek mathematician Euclid, who described it in his work "Elements" around 300 BCE.
Here's how the Euclidean Algorithm works:
1. Start with two positive integers, a and b, where a is greater than or equal to b. 2. Divide a by b and find the remainder. Let r be the remainder: r = a % b. 3. Replace a with b and b with r: a = b, b = r.
4. Repeat steps 2 and 3 until the remainder r becomes zero.
5. The last non-zero remainder obtained in step 2 is the GCD of the original two integers a and b.
Mathematically, you can express the Euclidean Algorithm as follows:
GCD(a, b) = GCD(b, a % b)
Certainly, let's find the greatest common divisor (GCD) of 79 and 7 using the Euclidean algorithm.

Step 1: Initialize the algorithm with the two numbers, `a` and `b`.
- `a = 79` - `b = 7`
Step 2: Calculate the remainder of `a` divided by `b`.
- `a % b = 79 % 7 = 6`
3: Update `a` to be `b`, and `b` to be the remainder from the previous step.

- `a = 7`
- `b = 6`

Step4: Repeat Steps 2 and 3 until `b` becomes 0.
- Calculate `a % b`: `7 % 6 = 1`
- Update `a` and `b`:
- `a = 6`
- `b = 1`
- Calculate `a % b`: `6 % 1 = 0`
- Update `a` and `b`:
- `a = 1`
- `b = 0`
Step 5: When `b` becomes 0, the GCD is the current value of `a`. In this case, GCD(79, 7) = 1.

So, the GCD of 79 and 7 is 1. The Euclidean Algorithm is efficient and widely used in various applications, including simplifying fractions, solving modular arithmetic problems, and cryptography. It's a simple and elegant way to find the GCD of two numbers and has been known and used for over two millennia.
Demonstration:
Program: To implement the Euclidean Algorithm in C
Source code:
#include<stdio.h>
int enclidean(int a,int b){
int r;
while (b!=0){r=a%b;
a=b;
b=r;
}
return a;
}
int main(){
int a,b;
printf("Enter the numbers:n");
scanf("%d%d",&a,&b);
printf("GCD(%d,%d)=%d",a,b,enclidean(a,b));
return 0;
}
Output and Discussion


Here, the above output takes 2 integers as input from user and display their GCD using Euclidean algorithm. In this output when 48 and 18 were given then the program uses the algorithm and display their GCD which is 6.
Conclusion
Here, we have completely implemented the Euclidean algorithm using C language and display the GCD of two numbers using the algorithm in the IDE Dev C++.




Experiment 2.2
Objective: TO IMPLEMENT THE EXTENDED EUCLIDEAN ALGORITHM IN C PROGRAM
Theory
The Extended Euclidean Algorithm is an extension of the basic Euclidean Algorithm. While the basic Euclidean Algorithm is used to find the greatest common divisor (GCD) of two integers, the Extended Euclidean Algorithm is used to find not only the GCD but also the coefficients (usually denoted as x and y) that can be used to express the GCD as a linear combination of the two input numbers. This is particularly useful in number theory, cryptography, and modular arithmetic.
The Extended Euclidean Algorithm works as follows:
1. Start with two positive integers, a and b, where a is greater than or equal to b. 2. Apply the basic Euclidean Algorithm to find the GCD of a and b. This is done by repeatedly dividing a by b and updating the values of a and b until the remainder becomes zero. The GCD is the last non-zero remainder.
3. During the execution of the basic Euclidean Algorithm, maintain two sets of variables, x and y, initialized as follows:
- x0 = 1, x1 = 0
- y0 = 0, y1 = 1
4. As you progress through the steps of the basic Euclidean Algorithm (dividing a by b and updating a and b), update x and y as follows:
- xn+1 = x(n-1) - (a // b) * xn
- yn+1 = y(n-1) - (a // b) * yn
5. Continue these updates until the remainder becomes zero.
6. At the end of the Extended Euclidean Algorithm, the GCD of a and b is the last non-zero remainder. Additionally, x and y will be the coefficients that satisfy the equation: GCD(a, b) = ax + by
These coefficients x and y can be either positive or negative integers and represent a linear combination of a and b that results in the GCD. The Extended Euclidean Algorithm is particularly useful in solving modular equations and modular inverses in modular arithmetic. It is a key component in many cryptographic algorithms, including RSA encryption and decryption, as it helps find the modular multiplicative inverse, which is essential for encryption and decryption operations.





Demonstration:
Program: To implement the Extended Euclidean Algorithm in C.

Source code:
#include <stdio.h>
int extendedEuclidean(int a, int b, int *x, int *y) {
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = extendedEuclidean(b % a, a, &x1, &y1);
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
int main() {
int a, b;
printf("Enter two integers: n");
scanf("%d %d", &a, &b);
int x, y;
int gcd = extendedEuclidean(a, b, &x, &y);
printf("GCD(%d, %d) = %dn", a, b, gcd);
printf("x = %d, y = %dn", x, y);
return 0;
}




Output and Discussion

Here, the above output takes 2 integers as input from user and display their GCD using Extended Euclidean algorithm. In this output when 46 and 4 were given then the program uses the algorithm and display their GCD which is 2.Since it is using extended Euclidean algorithm it has also display the value of x and y and which can be shown in equation like
GCD(a,b) = xa+yb

Conclusion
Here, we have completely implemented the Extended Euclidean algorithm using C language and display the GCD of two numbers using the algorithm in the IDE Dev C++.















Experiment 2.3
Objective: TO FIND THE BOOLEAN JOIN AND BOOLEAN PRODUCT OF BOOLEAN MATRIX IN C PROGRAM
Theory :
In the context of Boolean algebra and matrices, "Boolean join" and "Boolean product" typically refer to two different operations that can be performed on Boolean matrices. 1. Boolean Join (Logical OR):
- The Boolean join of two Boolean matrices is essentially the element-wise logical OR operation. - Given two Boolean matrices A and B of the same dimensions, the Boolean join (often denoted as ∨) results in a new matrix C, where each element C[i][j] is the result of the logical OR operation between A[i][j] and B[i][j].
- Mathematically, for each element: C[i][j] = A[i][j] ∨ B[i][j]
2. Boolean Product (Logical AND):
- The Boolean product of two Boolean matrices is the element-wise logical AND operation. - Given two Boolean matrices A and B of the same dimensions, the Boolean product (often denoted as ∧) results in a new matrix C, where each element C[i][j] is the result of the logical AND operation between A[i][j] and B[i][j].
- Mathematically, for each element: C[i][j] = A[i][j] ∧ B[i][j]
These operations are often used in various fields, including computer science and digital logic design, to perform element-wise combinations of Boolean values stored in matrices. The resulting Boolean matrices reflect the combination of values from the original matrices based on the specified Boolean operation (OR or AND).
In the Boolean join (OR) example, each element of the resulting matrix is obtained by performing a logical OR operation on the corresponding elements of matrices A and B. In the Boolean product (AND) example, each element of the resulting matrix is obtained by performing a logical AND operation on the corresponding elements of matrices A and B.
Demonstration:
Program: To find Boolean join of Boolean matrix in C.
Source code:
#include <stdio.h>

// Function to perform Boolean join (union) of two matrices
void booleanJoin(int A[][10], int B[][10], int result[][10], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result[i][j] = A[i][j] || B[i][j]; // Logical OR operation
}
}
}

// Function to display a Boolean matrix
void displayMatrix(int matrix[][10], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("n");
}
}

int main() {
int rows, cols;

printf("Enter the number of rows and columns: ");
scanf("%d %d", &rows, &cols);

int matrixA[10][10], matrixB[10][10], resultMatrix[10][10];

printf("Enter the elements of the first Boolean matrix (0 or 1):n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &matrixA[i][j]);
}
}

printf("Enter the elements of the second Boolean matrix (0 or 1):n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &matrixB[i][j]);
}
}

// Perform Boolean join
booleanJoin(matrixA, matrixB, resultMatrix, rows, cols);

printf("Boolean Join Result:n");
displayMatrix(resultMatrix, rows, cols);

return 0;
}

Output and Discussion
Page | 20
Here, the above program we take 2 Boolean matrix and use logical Or to join the matrixes. Here first we take no of rows and columns of 1st matrix and we enter the matrix then no of rows and columns of 2nd matrix then we join them.
Program: To find Boolean product of Boolean matrix in C.
Source code:
#include <stdio.h> //bool product
int main(){
int r1,c1,r2,c2,i,j,k,sum=0;
int first[5][5],second[5][5],mul[5][5];
printf("enter the no of rows and columns of 1st matrix:n");
scanf("%d %d",&r1,&c1);
printf("Enter the 1st matrix:n");
for(i=0;i<r1;i++){
for(j=0;j<c1;j++){
scanf("%d",&first[i][j]);
}
}
printf("enter the no of rows and columns of 2nd matrix:n");
scanf("%d %d",&r2,&c2);
if(c1 !=r2){
printf("product doesnot exit");
}
else{
printf("Enter the 2nd matrix:n");
for(i=0;i<r2;i++){
for(j=0;j<c2;j++){
scanf("%d",&second[i][j]);
}
}
//multiplying bool matrix
for(i=0;i<r1;i++){
for(j=0;j<c2;j++){
for(k=0;k<r2;k++){
sum=sum||first[i][k]&&second[k][j];
}
mul[i][j]=sum;
sum=0;
}
}
//display
printf("The product matrix is:n");
for(i=0;i<r1;i++){


for(j=0;j<c2;j++){
printf("%dt",mul[i][j]);
}
printf("n");
}
}
return 0;
}
Output and Discussion

Here, the above program we take 2 Boolean matrix and use logical OR and logical AND to multiply the matrixes. Here first we take no of rows and columns of 1st matrix and we enter the matrix then no of rows and columns of 2nd matrix then we multiply them to get the Boolean product.
Conclusion
Here, we have completely find the Boolean join and Boolean product of 2 Boolean matrix in the IDE Dev C++.







Experiment No. 2.4:
Objectives: TO IMPLEMENT BINARY ADDITION AND MULTIPLICATION
• To implement binary addition.
• To implement binary multiplication in C++.
Theory:

Binary Addition:

Binary addition is the process of adding two binary numbers together. In binary, there are only two digits, 0 and 1. The addition rules are similar to those in the decimal system but with simpler carry-over rules:

1. **0 + 0 = 0:** Adding two binary 0s results in 0.
2. **0 + 1 = 1:** Adding 0 and 1 results in 1.
3. **1 + 0 = 1:** Adding 1 and 0 also results in 1.
4. **1 + 1 = 10:** Adding two binary 1s results in 0, with a carry-over of 1 to the next higher bit.

Carry-overs continue until there are no more digits to add. Binary addition is fundamental in digital electronics and computer arithmetic.

Binary Multiplication:

Binary multiplication is the process of multiplying two binary numbers together. It involves the following key rules:

1. **0 × 0 = 0:** Multiplying two binary 0s results in 0.
2. **0 × 1 = 0:** Multiplying 0 by any binary digit (0 or 1) results in 0.
3. **1 × 0 = 0:** Multiplying 1 by 0 also results in 0.
4. **1 × 1 = 1:** Multiplying two binary 1s results in 1.

Binary multiplication is analogous to multiplication in the decimal system, but simpler due to the limited set of digits. When multiplying binary numbers with multiple digits, you apply these rules for each bit position and handle carry-overs similarly to binary addition.

Binary multiplication is essential in digital circuits and computer processors for various operations, such as shifting and scaling data.

Both binary addition and multiplication form the basis of binary arithmetic, which is fundamental in computer science, digital logic, and information technology. They are crucial for performing various operations in computers and other digital systems.
Demonstration:
Program 1
// Program to add two binary numbers
#include <stdio.h>
#include <string.h>
char* addBinary(const char* a, const char* b) {
int lenA = strlen(a);
int lenB = strlen(b);
int maxLen = (lenA > lenB) ? lenA : lenB;
char* sum = (char*)malloc((maxLen + 2) * sizeof(char)); // +1 for sum and +1 for '' int s = 0;
int i = lenA - 1;
int j = lenB - 1;
int k = 0;






while (i >= 0 || j >= 0 || s == 1) { if (i >= 0) {
s = s + (a[i] - '0');
} else {
s = s + 0;
}
if (j >= 0) {
s = s + (b[j] - '0');
} else {
s = s + 0;
}
sum[k++] = (char)(s % 2 + '0'); s = s / 2;
i = i - 1;
j = j - 1;
}
sum[k] = '';
// Reverse the sum to get the correct result int start = 0;
int end = k - 1;
while (start < end) {
char temp = sum[start];
sum[start] = sum[end];
sum[end] = temp;
start++;
end--;
}
return sum;
}
int main(void) {
char a[100];
char b[100];
printf("Enter first binary number: "); scanf("%s", a);
printf("Enter second binary number: "); scanf("%s", b);
char* result = addBinary(a, b);




printf("Sum is %sn", result);
free(result);
return 0;
}
Output

Program 2
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* addBinary(const char* a, const char* b) {
int lenA = strlen(a);
int lenB = strlen(b);
int maxLen = (lenA > lenB) ? lenA : lenB;
char* sum = (char*)malloc((maxLen + 2) * sizeof(char)); // +1 for sum and +1 for '' int s = 0;
int i = lenA - 1;
int j = lenB - 1;
int k = 0;
while (i >= 0 || j >= 0 || s == 1) {
if (i >= 0) {
s = s + (a[i] - '0');
} else {
s = s + 0;
}
if (j >= 0) {
s = s + (b[j] - '0');
} else {
s = s + 0;
}




sum[k++] = (char)(s % 2 + '0');
s = s / 2;
i = i - 1;
j = j - 1;
}
sum[k] = '';
// Reverse the sum to get the correct result
int start = 0;
int end = k - 1;
while (start < end) {
char temp = sum[start];
sum[start] = sum[end];
sum[end] = temp;
start++;
end--;
}
return sum;
}
char* multiply(const char* num1, const char* num2) {
char* result = (char*)malloc(2 * sizeof(char));
result[0] = '0';
result[1] = '';
int digit = 0;
for (int i = strlen(num2) - 1; i >= 0; i--) {
int carry = 0;
char* temp = (char*)malloc((strlen(num1) + digit + 2) * sizeof(char)); int tempIndex = 0;
for (int j = strlen(num1) - 1; j >= 0; j--) {
int product = (num2[i] - '0') * (num1[j] - '0') + carry; temp[tempIndex++] = (char)(product % 2 + '0');
carry = product / 2;
}
temp[tempIndex++] = (char)(carry + '0');
for (int j = 0; j < digit; j++) {
temp[tempIndex++] = '0';
}

temp[tempIndex] = '';
char* previousResult = result;
result = addBinary(result, temp);
free(previousResult);
digit++;
free(temp);
}
return result;
}
int main(void) {
char a[100];
char b[100];
printf("Enter first binary number: ");
scanf("%s", a);
printf("Enter second binary number: ");
scanf("%s", b);
char* result = multiply(a, b);
printf("Product is %sn", result);
free(result);
return 0;
}

Output

Discussion:
In the first program, we calculated the sum of two user given binary numbers. Similarly, in the second program we calculated the production of two binary numbers given by the user.


Conclusion:
Hence, from the above experiment we can implement binary addition and binary multiplication in C programming language.
Experiment 3.1
Objective: TO SOLVE THE FOLLOWING RECURSIVE PROBLEMS
• Sum of first n natural number
• Factorial of n
• Value of 12+22+32+…+n2
• Nth Fibonacci series
• Power(a,b)
Theory :
Recursion is a fundamental concept in programming and computer science. It refers to a programming technique where a function calls itself to solve a problem. In other words, a recursive function is one that breaks down a complex problem into smaller, more manageable subproblems of the same type until the subproblems become simple enough to be solved directly.
Here are some key concepts and characteristics of recursion in programming:
1. Base Case: A recursive function must have one or more base cases, which are the simplest instances of the problem that can be solved directly without further recursion. Base cases are essential to prevent the recursion from continuing indefinitely and to ensure that the recursion eventually terminates.
2. Recursive Case: In the recursive case, the function calls itself with a modified version of the original problem. This typically involves reducing the size or complexity of the problem in some way. The goal is to make progress toward reaching the base case.
3. Stack: Recursion uses a call stack to keep track of function calls. Each time a function is called recursively, a new instance of that function is added to the call stack. When the base case is reached, the function calls are resolved and removed from the stack in a last-in-first-out (LIFO) order.
4. Divide and Conquer: Many recursive algorithms follow the "divide and conquer" paradigm. They break a problem into smaller subproblems, solve the subproblems recursively, and then combine the solutions of the subproblems to solve the original problem.
5. Recursive Functions: A recursive function consists of two main parts: the base case and the recursive case. The base case provides the termination condition, and the recursive case defines how the function calls itself with a modified input.


Recursion is a powerful and elegant technique, but it should be used with care. Infinite recursion (where the base case is not reached) can lead to stack overflow errors, and recursive algorithms can sometimes be less efficient than their iterative counterparts. However, in many cases, recursion provides a concise and intuitive way to solve complex problems.
Demonstration:
Program 1: To find the sum of first n natural number in C
Source code:
#include<stdio.h> //sum of first n natural number
int sumofN(int n){
if(n==0){
return 0;
}
else
return n+sumofN(n-1);
}
int main(){
int n;
printf("enter the number:n");
scanf("%d",&n);
printf("Sum is:n%d",sumofN(n));
return 0;
}
Output

Program 2: To find the factorial of n in C
Source code:
#include<stdio.h> //n!
int factofN(int n){
if(n==0){
return 1;
}
else
return n*factofN(n-1);
}
int main(){
int n;
printf("enter the number:n");
scanf("%d",&n);
printf("factorial is:n%d",factofN(n));
return 0;
}
Output


Program 3: To find the value of 12+22+32+…+n2in C
Source code:
#include<stdio.h> //sum of 1^2+2^2...+n^2
int sumofNsq(int n){
if(n==0){
return 0;
}
else
return n*n+sumofNsq(n-1);
}
int main(){
int n;
printf("enter the number:n");
scanf("%d",&n);
printf("Sum is:n%d",sumofNsq(n));
return 0;
}

Output

Program 4: To find the nth Fibonacci number in C
Source code:
#include<stdio.h> //fibo
int fibo(int n){
if(n==0){
return 0;
}
else if(n==1)
return 1;
else
return fibo(n-1)+fibo(n-2);
}
int main(){
int n;
printf("enter the number:n");
scanf("%d",&n);
printf("Fibo number is:n%d",fibo(n));
return 0;
}
Output



Program 5: To find the power(a,b) in C
Source code:


#include <stdio.h> //power(A,B) using recursion
int power(int a,int b){
if(b==0){
return 1;
}
else{
return a*power(a,b-1);
}
}
int main (){
int x,y,ans;
printf("enter the base and exponent:n");
scanf("%d %d",&x,&y);
ans=power(x,y);
printf("Ans:%d",ans);
return 0;
}
Output

Discussion
Here for every problem we have write different codes and they have use recursion to solve the problem. Program 1 find the sum of first n natural numbers using recursion, program 2 factorial of n , program 3 sum of square of first n natural numbers, program 4 Fibonacci series and finally last program find the power(a,b) using recursion respectively.
Conclusion
Here, we have completely solve the problems using recursion and demonstrate the output using the IDE Dev C++.




Experiment 3.2
Objective: TO SOLVE THE TOH PROBLEM
• To study and write a program to solve the TOH problem
Theory :
The Tower of Hanoi (TOH) problem is a classic puzzle and mathematical problem that involves a set of rules for moving a stack of disks from one peg to another while following specific constraints. The problem is typically stated as follows:
Problem Statement:
- There are three pegs: source (A), auxiliary (B), and destination (C).
- There is a set of disks, initially stacked in decreasing order of size on one peg (the source), with the largest disk at the bottom and the smallest disk at the top.
- Only one disk can be moved at a time, and it must be the top disk from one of the stacks. - A larger disk cannot be placed on top of a smaller disk.
The goal of the Tower of Hanoi problem is to move all the disks from the source peg to the destination peg, using the auxiliary peg as a temporary location, while adhering to the rules. Key concepts and characteristics of the Tower of Hanoi problem:
1. Recursion: The Tower of Hanoi problem can be elegantly solved using recursion. The recursive algorithm breaks down the problem into smaller subproblems and solves them recursively. 2. Base Case: The base case is when there is only one disk to move. In this case, it is straightforward to move the single disk directly from the source peg to the destination peg. 3. Recursive Case: In the recursive case, the problem is divided into three main steps: - Move `n-1` disks from the source peg to the auxiliary peg, using the destination peg as temporary storage.
- Move the largest disk (the nth disk) from the source peg to the destination peg. - Move the `n-1` disks from the auxiliary peg to the destination peg, using the source peg as temporary storage.
4. Optimal Solution: The optimal solution to the Tower of Hanoi problem requires a minimum number of moves, which is 2^n - 1, where 'n' is the number of disks. This is achieved by following the recursive algorithm.
5. Mathematical Background: The Tower of Hanoi problem has connections to various mathematical concepts, including binary representation and powers of 2. The formula for the minimum number of moves is derived from these mathematical properties.
The Tower of Hanoi problem is not just a puzzle but also serves as a classic example of recursion and algorithm design. It is often used in computer science and programming courses to teach recursion and algorithmic thinking. Additionally, it has practical applications in areas like computer programming, data sorting, and problem-solving.

Demonstration:
Program: To solve the TOH problem in C.
Source code:
#include<stdio.h> //TOH problem
void TOH(int n,char a, char b, char c){
if(n>0){
TOH(n-1,a,c,b);
printf("Move %d disk from %c to %cn",n,a,c);
TOH(n-1,b,a,c);
}
}
int main(){
int n;
char a='a',b='b',c='c';
printf("Enter the number of disk:n");
scanf("%d",&n);
TOH(n,a,b,c);
return 0;
}
Output and Discussion

In this program we have demonstrated the steps to solve the TOH problem. Here in above code for 3 disk it take total of 7 steps to solve the TOH problem.

Conclusion
Here, we have written and demonstrated the output to solve the TOH problem in the IDE Dev C++.
Experiment 3.3
Objective: TO IMPLEMENT THE MERGE SORT ALGORITHM • To study and write a program to implement the merge sort algorithm
Theory :
Merge sort is a sorting algorithm that is used to sort array that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.
It can sort larger arrays relatively faster than normal sorting like bubble sort and insertion sort. It is also a stable sort; it means that order of elements with equal values are preserved during the sort.
It is an algorithm which divides an array into half until it cannot be divided further. This means that if array becomes empty or it has only one element left, the dividing will stop. If the array has multiple elements , split the array into halves and recursively invoke the merge sort on each of the halves. Finally, when both halves are sorted, the merge operation is applied. Merge operation is the process of taking two smaller sorted arrays1 and combining them to eventually make a larger one.
ALGORITHM FOR MERGE SORT:
step1: Start.
step2: declare array and left, right, mid-value.
step3: perform merge functions:
if left<right
return
mid=(left+right)/2;
mergesort(array, left, mid)
mergesort(array , mid+1, right)
mergesort(array, left, mid, right)
step4: Stop.
Demonstration:
Program: To implement the merge sort algorith in C.
Source code:
#include<stdio.h>//merge sort
void Merge(int a[],int L,int mid,int H)
{
int n1 = mid-L+1;
int n2 =H-mid;
int i,j,k;





int A[n1], B[n2];
for ( i = 0; i < n1; i++)
A[i] = a[L + i];
for ( j = 0; j < n2; j++)
B[j] = a[mid + 1 + j];
i = 0;
j = 0;
k = L;
while (i < n1 && j < n2) { if (A[i] <= B[j]) {
a[k] = A[i];
i++;
} else {
a[k] = B[j];
j++;
}
k++;
}
while (i < n1) {
a[k] = A[i];
i++;
k++;
}
while (j < n2) {
a[k] = B[j];
j++;
k++;
}
}
void MergeSort(int a[],int L,int H) {
if(L<H)
{
int mid=(L+H)/2;
MergeSort(a,L,mid);
MergeSort(a,mid+1,H); Merge(a,L,mid,H);
}
}
int main()
{
int n,Array[100],i=0;
printf("Enter no. of elements in array:n");
scanf("%d",&n);
printf("Enter elements of Array:n");
for(i=0;i<n;i++)
scanf("%d",&Array[i]);
printf("Array Without Sort:n");
for(i=0;i<n;i++)
printf("%dt",Array[i]);
MergeSort(Array,0,n-1);
printf("nArray with Sorting:n");
for(int i=0;i<n;i++)
printf("%dt",Array[i]);
return 0;
}
Output and Discussion


Here, the above program we have use merge sort algorithm to sort an array. Above program has sort the 5 number in ascending order using merge sort algorithm.

Conclusion
Here, we have completely implemented the merge sort algorithm in IDE Dev C++.