Experiment No .

05: BRANCH & BOUND ALGORITHM Date:09/05/2023

Aim:- Write C program to implement the following using Branch and Bound Algorithm.
a) 0/1 Knapsack

THEORY:
● The Branch and Bound algorithm are used to solve optimization problems, particularly
combinatorial optimization problems.
● It involves dividing the problem into smaller subproblems and constructing a search tree.
● The algorithm starts with an initial solution and initializes upper and lower bounds.
● The search process begins by exploring the search tree using a depth-first search (DFS) or
breadth-first search (BFS) strategy.
● At each node of the search tree, the algorithm evaluates the bounds to determine if further
exploration is warranted.
● If the lower bound of a node is higher than the current best solution, the subtree rooted at that
node is pruned.
● If the upper bound of a node is lower than the current best solution, the algorithm backtracks to
the parent node.
● At each node, a decision is made to include or exclude a particular element or constraint from the
solution.
● The current solution and the bounds are updated accordingly.
● The algorithm continues exploring the search tree until all nodes have been visited or until the
best solution is found.
● The final solution obtained is the optimal solution to the optimization problem.

RollNo.211105036 |Pa g e
 a) 0/1 KNAPSACK
Date:09/05/2023
Problem Statement

Solve the 0/1 knapsack problem for the knapsack instance n = 4 and m = 35
(w1 . . . . w4) = (5,7,4,2) (p1 . . . . . p4) = (30,28,20,24)

Algorithm
Algorithm UBound(cp,cw,k,m)
//w[i] and p[i] are respectively the weight and profit of the ith object .
{
B:= cp ;
C:= cw;
For i:= k+1 to n do
{
If(c+w[i] ≤ m) then
{
c:=c + w[i] ;
b:=b-p[i];
}
}
return b;
}

Algorithm bnb (level ,w,p)

//bestp->best profit so far
{
If(w ≤m )then
{
bestp := p;
copy elements from currentsol to bestsol
}
If((level =n ) or (ub (level , w ,p ) ≤bestp ))
{
return;
}
Set currentsol[level] =1;
Bnb(level +1 , w+weight[level],p+profit[level])

Set currentsol[level] = 0;
Bnb(level +1,w,p)
}
Time and Space Complexity
Time Complexity = O(2n + n2)
Space complexity = O(n)
Where , n is the number of Elements .

RollNo.211105036 |Pa g e
Code:
/*code for 0/1 knapsack bnb problem*/
#include <stdio.h>
#define N 100

void fill();
int uppbound(int level, int w, int p);
void sort();
void bnb(int level, int w, int p);

struct ITEM
{
int w, p;
};

int m, n, currentsoln[N], bestsoln[N], cw, cp, bestp,i,j;

struct ITEM items[N];

int main()
{
printf("Enter the knapsack capacity: "), scanf("%d",&m);
printf("Enter the total no. of items: "), scanf("%d",&n);
printf("Enter the profit and weight for each item:\n");
for (i = 0; i < n; i++)
printf("Item %d: ",i+1), scanf("%d",&items[i].p),
scanf("%d",&items[i].w);
cw = cp = bestp = 0;
fill();
sort();
bnb(0, cw, cp);

printf("Knapsack Solution is:\nMax Profit = %d\nItems Included: ", bestp);

for ( i = 0; i < n; i++)
printf(" %d", bestsoln[i]);
printf("\n");

return 0;
}

void fill()
{
for (i = 0; i < n; i++)
currentsoln[i] = bestsoln[i] = 0;
}

int uppbound(int level, int w, int p)

{
int r = m - w;
int ub = p;

for (i = level; i < n; i++)

{
if (items[i].w <= r)
{
r -= items[i].w;
ub += items[i].p;
}
else
{
ub += (r / items[i].w) * items[i].p;

RollNo.211105036 |Pa g e
 break;
}
}
return ub;
}

void sort()
{
for ( i = 0; i < n; i++)
{
for ( j = 0; j < n - i - 1; j++)
{
if ((items[j].p / items[j].w) < (items[j + 1].p / items[j + 1].w))
{
int tempp = items[j].p, tempw = items[j].w;
items[j].p = items[j + 1].p, items[j].w = items[j + 1].w;
items[j + 1].p = tempp, items[j + 1].w = tempw;
}
}
}
}

void bnb(int level, int w, int p)

{
if (w <= m)
{
if (p > bestp)
{
bestp = p;
for (i = 0; i < n; i++)
bestsoln[i] = currentsoln[i];
}
}

if (level == n || uppbound(level, w, p) <= bestp)

return;

currentsoln[level] = 1;
bnb(level + 1, w + items[level].w, p + items[level].p);

currentsoln[level] = 0;
bnb(level + 1, w, p);
}

OUTPUT :

C:\Users\Nidhi Shanbhag \Documents\knapsackbnb.exe

Enter the knapsack capacity: 12
Enter the total no. of items: 4
Enter the profit and weight for each item:
Item 1: 30 5
Item 2: 28 7
Item 3: 20 4
Item 4: 24 2

RollNo.211105036 |Pa g e
Knapsack Solution is:
Max Profit = 74
Items Included: 1 1 1 0

--------------------------------
Process exited after 28.13 seconds with return value 0
Press any key to continue . . .

Conclusion:

Branch & Bound algorithm was studied .

The program for

a) 0/1 Knapsack

was studied and implemented successfully.

RollNo.211105036 |Pa g e
Experiment No . 06: INTERNET ALGORITHMS Date:12/05/2023

Aim:- Write C program to implement the following using Internet Algorithm.

a. KMP Pattern Matching
b. BM Pattern Matching
c. Huffman Coding (Text Compression)
d. Longest common Subsequence. (Text Similarities)

Theory
 Internet algorithms are specifically designed algorithms used in various aspects of the internet to
solve specific problems efficiently.
 These algorithms address challenges related to data transmission, routing, network optimization,
information retrieval, and security, among others.
 Internet algorithms often consider factors such as latency, bandwidth, scalability, fault tolerance,
and resource constraints to ensure efficient and reliable operations.

Knuth-Morris-Pratt (KMP) Algorithm:

 The KMP algorithm is used for pattern matching in strings efficiently.
 It avoids unnecessary comparisons by utilizing information from previous matches.
 It pre-processes the pattern to construct a lookup table (also called the "failure function") that
helps skip unnecessary comparisons during matching.
 The algorithm compares the pattern with the input text character by character, utilizing the
lookup table to determine the next position for comparison in case of a mismatch.
 The KMP algorithm achieves a time complexity of O(n + m), where n is the length of the input
text and m is the length of the pattern, making it efficient for large-scale pattern matching.

Boyer-Moore (BM) Algorithm:

 The Boyer-Moore algorithm is another efficient pattern matching algorithm, particularly suitable
for searching in large texts.
 It pre-processes the pattern and utilizes two heuristics: the "bad character rule" and the "good
suffix rule."
 The bad character rule skips comparisons by shifting the pattern to align the rightmost
occurrence of a mismatched character in the text with the corresponding position in the pattern.
 The good suffix rule utilizes information about matching suffixes in the pattern to skip
unnecessary comparisons.

RollNo.211105036 |Pa g e
  The Boyer-Moore algorithm achieves a best-case time complexity of O(n/m) and an average-
case time complexity of O(n + m), making it efficient for practical use.

Huffman Coding:
 Huffman coding is a compression algorithm used to encode data efficiently by assigning shorter
codes to frequently occurring characters and longer codes to less frequent characters.
 The algorithm builds a binary tree (Huffman tree) based on the frequency of characters in the
input data.
 The characters with higher frequency are assigned shorter codes, and those with lower frequency
are assigned longer codes, ensuring prefix-free codes.
 Huffman coding achieves compression by representing the input data using the generated
Huffman codes, reducing the overall number of bits required for storage or transmission.
 The time complexity of the Huffman coding algorithm is O(n log n), where n is the number of
unique characters in the input.

Longest Common Subsequence (LCS) Algorithm:

 The LCS algorithm is used to find the longest common subsequence between two sequences,
typically strings.
 It determines the longest subsequence that is present in both sequences but does not necessarily
have to be contiguous.
 The algorithm utilizes dynamic programming to build a table that stores the lengths of the
longest common subsequences for various subproblems.
 Starting from the end of the sequences, the algorithm fills the table by considering two cases:
matching characters or non-matching characters.
 Finally, the algorithm traces back the table to reconstruct the LCS.
 The time complexity of the LCS algorithm is O(mn), where m and n are the lengths of the input
sequences, making it efficient for practical use.

RollNo.211105036 |Pa g e
 a) KMP PATTERN MATCHING

Date:12/05/2023
Problem Statement
Write a C program to implement KMP pattern matching for
T = aabbbaababbbabab and P = bbaba

Algorithm
Algorithm KMPMatch(T,P):
Input: Strings T (text) with n characters and P (pattern) with m characters
Output: Starting index of the first substring of T matching P, or an indication
that P is not a substring of T
f ← KMPFailureFunction(P) // construct the failure function f for P
i←0
j←0
while i<n do
if P[j] = T[i] then
if j = m − 1 then
return i − m + 1 // a match!
i←i+1
j←j+1
else if j > 0 // no match, but we have advanced in P then
j ← f(j − 1) // j indexes just after prefix of P that must match
else
i←i+1
return “There is no substring of T matching P.”

Algorithm KMPFailureFunction(P):
Input: String P (pattern) with m characters
Output: The failure function f for P, which maps j to the length of the longest
prefix of P that is a suffix of P[1..j]
i←1
j←0
f(0) ← 0
while i<m do
RollNo.211105036 |Pa g e
if P[j] = P[i] then
// we have matched j + 1 characters
f(i) ← j + 1
i←i+1
j←j+1
else if j > 0 then
// j indexes just after a prefix of P that must match
j ← f(j − 1)
else
// we have no match here
f(i) ← 0
i←i+1

Time and Space Complexity

Time Complexity = O(m+n)
Space complexity = O(m)
Where , n is the length of text and m is the length of pattern .

CODE:
#include <stdio.h>
#include <string.h>
#define N 256

int f[N],n,m;

int KMPfailure(char p[N])

{
int i, j;
i = 1, j = 0;
f[0] = 0;
while (i < m)
{
if (p[j] == p[i])
{
f[i] = j + 1;
i++, j++;
}
else if (j > 0)
j = f[j - 1];
else
{
f[i] = 0;
i++;
}
}
}

void kmpMatch(char t[N], char p[N])

RollNo.211105036 |Pa g e
{
KMPfailure(p);
int i, j;
i = j = 0;
while (i < n)
{
if (p[j] == t[i])
{
if (j == m - 1)
{
printf("Pattern %s found at index %d in %s\n", p, i - m + 1,
t);
return;
}
i++, j++;
}
else if (j > 0)
j = f[j - 1];
else
i++;
}
printf("substring %s is not present in string %s\n", p, t);
return;
}

int main(int argc, char const *argv[])

{
char t[] = "aabbbaababbbabab";
char p[] = "bbaba";
n=strlen(t);
m= strlen(p);
kmpMatch(t, p);
return 0;
}

OUTPUT:
C:\Users\Nidhi Shanbhag \ Documents\kmp.exe
Pattern bbaba found at index 10 in aabbbaababbbabab

--------------------------------
Process exited after 0.2755 seconds with return value 0
Press any key to continue . . .

RollNo.211105036 |Pa g e
 b) BOYER MOORE PATTERN MATCHING
Date:16/05/2023
Problem Statement
Write a C program to implement Boyer Moore pattern matching for
T = 1123114234112113 and P= 4112113

Algorithm
Algorithm BMMatch(T,P):
Input: Strings T (text) with n characters and P (pattern) with m characters
Output: Starting index of the first substring of T matching P, or an indication
that P is not a substring of T
compute function last
i←m−1
j←m−1
repeat
if P[j] = T[i] then
if j = 0 then
return i // a match!
else
i←i−1
j←j−1
else
i ← i + m − min(j, 1 + last(T[i])) // jump step
j←m−1
until i>n − 1
return “There is no substring of T matching P.”

Time and Space Complexity

Time Complexity = O(m+n)
Space complexity = O(m+k)
Where , n is the length of text and m is the length of pattern .

CODE:
#include <stdio.h>
#include <string.h>
#define charnum 256
int i;

int lastc[charnum];

void last(char p[charnum], int m)

{
for ( i = 0; i < charnum; i++)
lastc[i] = -1;
RollNo.211105036 |Pa g e
 for ( i = 0; i < m; i++)
lastc[(int)p[i]] = i;
}

int fmin(int a, int b)

{
return a < b ? a : b;
}

void bm(char t[], char p[], int n, int m)

{
last(p, m);
int i, j;
i = m - 1;
j = m - 1;
do
{
if (p[j] == t[i])
{
if (!j)
{
printf("Pattern %s found at index %d in %s\n", p, i, t);
return;
}
else
i -= 1, j -= 1;
}
else
{
i = i + m - fmin(j, 1 + lastc[(int)t[i]]);
j = m - 1;
}

} while (i <= n - 1);

printf("No substring\n");
}

int main(int argc, char const *argv[])

{
char t[] = "1123114234112113";
char p[] = "4112113";
printf("String 1 is: %s\n",t);
printf("String 2 is: %s\n",p);
bm(t, p, strlen(t), strlen(p));
return 0;
}

OUTPUT:
C:\Users\Nidhi Shanbhag \Documents\bm.exe
String 1 is: 1123114234112113
String 2 is: 4112113
Pattern 4112113 found at index 9 in 1123114234112113
--------------------------------
Process exited after 0.2885 seconds with return value 0
Press any key to continue . . .

RollNo.211105036 |Pa g e
 c) HUFFMAN CODING (Text Compression)
Date:19/05/2023
Problem Statement
Write a C program to implement Huffman Encoding for
“j is the position of the partitioning element “

Algorithm
Algorithm Huffman(C):
Input: A set, C, of d characters, each with a given weight, f(c)
Output: A coding tree, T, for C, with minimum total path weight
Initialize a priority queue Q.
for each character c in C do
Create a single-node binary tree T storing c.
Insert T into Q with key f(c).
while Q.size() > 1 do
f1 ← Q.minKey()
T1 ← Q.removeMin()
f2 ← Q.minKey()
T2 ← Q.removeMin()
Create a new binary tree T with left subtree T1 and right subtree T2.
Insert T into Q with key f1 + f2.
return tree Q.removeMin()

Time and Space Complexity

Time Complexity = O(nlogn+m)
Space complexity = O(n+mlogn)

CODE:
#include <stdio.h>
#include <stdlib.h>
#define N 50
int i;

struct minheap
{
int size, cap;

RollNo.211105036 |Pa g e
 struct minheapnode **array;
};

struct minheapnode
{
char item;
int freq;
struct minheapnode *left, *right;
};

struct minheapnode *newnode(char item, int freq)

{
struct minheapnode *temp = (struct minheapnode *)malloc(sizeof(struct
minheapnode));
temp->left = temp->right = NULL;
temp->item = item, temp->freq = freq;

return temp;
}

struct minheap *createminh(int cap)

{
struct minheap *minh = (struct minheap *)malloc(sizeof(struct minheap));
minh->size = 0, minh->cap = cap;

minh->array = (struct minheapnode **)malloc(minh->cap * sizeof(struct

minheapnode *));

return minh;
}

void swap(struct minheapnode **a, struct minheapnode **b)

{
struct minheapnode *temp = *a;
*a = *b;
*b = temp;
}

void heapify(struct minheap *minh, int current_index)

{
int smallest = current_index, left = 2 * current_index + 1, right = 2 *
current_index + 2;

if (left < minh->size && minh->array[left]->freq < minh->array[smallest]-

>freq)
smallest = left;

if (right < minh->size && minh->array[right]->freq < minh->array[smallest]-

>freq)
smallest = right;

if (smallest != current_index)
{
swap(&minh->array[smallest], &minh->array[current_index]);
heapify(minh, smallest);
}
}

int checksize(struct minheap *minh)

{
return (minh->size == 1);
}
RollNo.211105036 |Pa g e
struct minheapnode *getminnode(struct minheap *minh)
{
struct minheapnode *temp = minh->array[0];
minh->array[0] = minh->array[minh->size - 1];
--minh->size;

heapify(minh, 0);

return temp;
}

void insert(struct minheap *minh, struct minheapnode *minnode)

{
++minh->size;
int i = minh->size - 1;
while (i && minnode->freq < minh->array[(i - 1) / 2]->freq)
{
minh->array[i] = minh->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minh->array[i] = minnode;
}

void buildminheap(struct minheap *minh)

{
int n = minh->size - 1;

for ( i = (n - 1) / 2; i >= 0; --i)

heapify(minh, i);
}

int isleaf(struct minheapnode *root)

{
return (!(root->left) && !(root->right));
}

struct minheap *createandbuild(char item[], int freq[], int size)

{
struct minheap *minh = createminh(size);

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

minh->array[i] = newnode(item[i], freq[i]);

minh->size = size;
buildminheap(minh);

return minh;
}

struct minheapnode *buildhuffman(char item[], int freq[], int size)

{
struct minheapnode *left, *right, *top;
struct minheap *minh = createandbuild(item, freq, size);

while (!checksize(minh))
{
left = getminnode(minh);
right = getminnode(minh);

top = newnode('$', left->freq + right->freq);

RollNo.211105036 |Pa g e
 top->left = left, top->right = right;

insert(minh, top);
}
return getminnode(minh);
}

void show(int arr[], int n)

{
for (i = 0; i < n; i++)
printf("%d", arr[i]);
printf("\n");
}

void huffcodes(struct minheapnode *root, int arr[], int top)

{
if (root->left)
{
arr[top] = 0;
huffcodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
huffcodes(root->right, arr, top + 1);
}
if (isleaf(root))
{
printf("%c\t", root->item);
show(arr, top);
}
}

void huffman(char item[], int freq[], int size)

{
struct minheapnode *root = buildhuffman(item, freq, size);
int arr[N], top = 0;
huffcodes(root, arr, top);
}

int main(int argc, char const *argv[])

{
char arr[] = {'j', 'i', 's', 't', 'h', 'e', 'p', 'o', 'n', 'f', 'a',
'r','g','m',' ','l'};
int freq[] = {1,6,2,6,2,5,2,4,4,1,1,1,1,1,7,1};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Huffman Codes\n");
huffman(arr, freq, size);
return 0;
}

OUTPUT:
RollNo.211105036 |Pa g e
C:\Users\Nidhi Shanbhag \Documents\huffman.exe
Huffman Codes
n 000
s 0010
p 0011
f 01000
a 01001
m 01010
r 010110
g 010111
e 011
i 100
t 101
110
o 1110
j 111100
l 111101
h 11111
--------------------------------
Process exited after 0.3133 seconds with return value 0
Press any key to continue . . .

d)LCS (Text Similarity)

RollNo.211105036 |Pa g e
 Date:23/05/2023
Problem Statement
Write a C program to implement LCS for X= KLOKMKNKLOK and Y=KLLKNKLLKNYY

Algorithm
Algorithm LCS(X, Y ):
Input: Strings X and Y with n and m elements, respectively
Output: For i = 0,...,n − 1, j = 0,...,m − 1, the length L[i, j] of a longest
common subsequence of X[0..i] and Y [0..j]
for i ← −1 to n − 1 do
L[i, −1] ← 0
for j ← 0 to m − 1 do
L[−1, j] ← 0
for i ← 0 to n − 1 do
for j ← 0 to m − 1 do
if X[i] = Y [j] then
L[i, j] ← L[i − 1, j − 1] + 1
else
L[i, j] ← max{L[i − 1, j] , L[i, j − 1]}
return array L

Time and Space Complexity

Time Complexity = O(mn)
Space complexity = O(mn)
Where , n and m are the lengths of the strings.

CODE:
#include <stdio.h>
#include <string.h>
#define N 256

int L[N][N],i,j;

int smax(int a, int b)

{
return a > b ? a : b;
}

void lcs(char x[], char y[], int n, int m)

RollNo.211105036 |Pa g e
{
for ( i = 0; i <= m; i++)
L[i][0] = 0;
for ( j = 0; j <= n; j++)
L[0][j] = 0;
for ( i = 1; i <= m; i++)
{
for ( j = 1; j <= n; j++)
{
if (x[j - 1] == y[i - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = smax(L[i - 1][j], L[i][j - 1]);
}
}
}

void sequence(int ss[], int m, int n)

{
int i = m, j = n, k = m;
while (i > 0)
{
if (L[i][j] == L[i - 1][j])
ss[k] = 0, k--, i--;
else
ss[k] = 1, i--, j--, k--;
}
}

void show(char y[], int ss[], int m)

{
for ( i = 1, j = 0; i <= m, j < m; i++, j++)
{
if (ss[i])
printf("%c", y[j]);
}
printf("\n");
}

int main()
{
char x[] = "KLOKMKNKLOK", y[] = "KLLKNKLLKNYY";
int m = strlen(y), n = strlen(x), ss[strlen(y)];
lcs(x, y, n, m), sequence(ss, m, n);
printf("The string 1: %s\nThe string 2: %s\n",x,y);
printf("Length of the longest common subsequence is: %d\nThe longest
subsequence is: ", L[m][n]), show(y, ss, m);
return 0;
}

OUTPUT:

RollNo.211105036 |Pa g e
C:\Users\ Nidhi Shanbhag \Documents\lcs.exe
The string 1 is KLOKMKNKLOK
The string 2 is KLLKNKLLKNYY
Length of the longest common subsequence is: 7
The longest subsequence is: KLKNKLK
--------------------------------
Process exited after 0.6355 seconds with return value 0
Press any key to continue . . .

CONCLUSION:

Internet algorithms were studied . The programs for

a. KMP Pattern Matching
b. BM Pattern Matching
c. Huffman Coding
d. Longest Common Subsequence

were studied and implemented successfully.

RollNo.211105036 |Pa g e