DAA

Digital Assignment
Name-Hariesh Reddy
Reg no-21BBS0201

1.Consider a postman starts from his own office and visit all the places to deliver the letters
exactly once and return to his office. i.e. given a set of places and distance between every pair
of places, the problem is to find the shortest possible route that visits every place exactly once
and returns to the starting point. Design a solution using Brute Force Approach.

Algorithm:

Algorithm TravelingSalesmanProblem(graph, s):Let V be the

number of vertices in the graph
Create a vector 'vertex' and initialize it with all vertices except thestarting vertex s
min_path <- Infinity min_pathway
<- empty list

Do a permutation of the 'vertex'

vector: current_pathweight <- 0
k <- s pathway <-
[s]
For i from 0 to length(vertex) - 1: current_pathweight
+= graph[k][vertex[i]]k <- vertex[i]
Add vertex[i] to pathway

current_pathweight += graph[k][s]Add s to
pathway
Add current_pathweight to pathway

If current_pathweight < min_path:min_path <-

current_pathweight min_pathway <-
pathway
Print min_pathwayReturn
min_path

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int tsp(int n, vector<vector<int>>& graph, vector<bool>& visited, int curr,

int count, int cost, int& ans) {
if (count == n && graph[curr][0] != 0) {
ans = min(ans, cost + graph[curr][0]);
return ans;
}

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

if (!visited[i] && graph[curr][i] != 0) {
visited[i] = true;
tsp(n, graph, visited, i, count + 1, cost + graph[curr][i],
ans);
visited[i] = false;
}
}

return ans;
}

int main() {
int n; // Number of places
cout << "Enter the number of places: ";
cin >> n;

vector<vector<int>> graph(n, vector<int>(n,

0)); cout << "Enter the distance matrix:\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}

vector<bool> visited(n, false);

visited[0] = true; // Starting from the first place
int ans = INF;

tsp(n, graph, visited, 0, 1, 0, ans);

cout << "The shortest possible route is: " << ans << endl;

return 0;
}
Output:

Time Complexity:

The time complexity of the Brute Force approach for the Traveling Salesman Problem is factorial,
which is denoted as O(n!), where n is the number of places. This is because there are n! possible
permutations to consider. In short, the time complexity of the Brute Force approach for finding
the shortest route in the given scenario is O(n!).

1. Consider a file containing 6 unique characters and frequency of each character is given
How many bits are required to store this file using Huffman Encoding? Also decode the
text "0101101101001". Implement Huffman encoding and decoding process using Greedy
algorithm Strategy.

Algorithm:

Huffman (C)

n=|C|Q
←C
for i=1 to n-1

z= allocate-Node ()

x= left[z]=Extract-Min(Q) y= right[z]
=Extract-Min(Q)f [z]=f[x]+f[y]
Insert (Q, z)

return Extract-Min (Q)

}
Code:

#include <iostream>
#include <queue>
#include
<unordered_map> using
namespace std;

struct Node {
char character;
int frequency;
Node* left;
Node* right;

Node(char c, int f) : character(c), frequency(f), left(nullptr),

right(nullptr) {}
};

struct Compare {
bool operator()(Node* a, Node* b) {
return a->frequency > b->frequency;
}
};

unordered_map<char, string> huffmanCodes;

void generateHuffmanCodes(Node* root, string code) {

if (root->left == nullptr && root->right == nullptr)
{ huffmanCodes[root->character] = code;
return;
}

generateHuffmanCodes(root->left, code + "0");

generateHuffmanCodes(root->right, code +
"1");
}

Node* buildHuffmanTree(vector<pair<char, int>>& frequencies) {

priority_queue<Node*, vector<Node*>, Compare> pq;

for (auto& p : frequencies)

{ char c = p.first;
int f = p.second;
pq.push(new Node(c, f));
}

while (pq.size() > 1) {

Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();

Node* newNode = new Node('$', left->frequency + right-

>frequency); newNode->left = left;
newNode->right = right;

pq.push(newNode);
}

return pq.top();
}

string encodeHuffman(string text) {

string encodedText = "";

for (char c : text) {

encodedText += huffmanCodes[c];
}

return encodedText;
}

string decodeHuffman(Node* root, string encodedText) {

string decodedText = "";
Node* curr = root;

for (char c : encodedText)

{ if (c == '0') {
curr = curr->left;
} else {
curr = curr->right;
}

if (curr->left == nullptr && curr->right == nullptr) {

decodedText += curr->character;
curr = root;
}
}

return decodedText;
}

int main() {
int numCharacters = 6;
vector<pair<char, int>> frequencies = {{'c', 34}, {'d', 9}, {'g', 35},
{'u', 2}, {'m', 2}, {'a', 100}};
Node* root = buildHuffmanTree(frequencies);
generateHuffmanCodes(root, "");

string textToEncode = "cdgumac";

string encodedText = encodeHuffman(textToEncode);
cout << "Encoded text: " << encodedText << endl;

string textToDecode = "0101101101001";

string decodedText = decodeHuffman(root, textToDecode);
cout << "Decoded text: " << decodedText << endl;

return 0;
}

Output:

Time Complexity:

The time complexity of Huffman Encoding and Decoding using a Greedy algorithm strategy is
typically O(n log n), where n is the number of unique characters in the file. This is because the
algorithm involves building a priority queue (min-heap) based on character frequencies, which
requires O(n log n) time complexity. Additionally, traversing the Huffman tree to generate codes
and encoding/decoding the text also takes linear time complexity, but the dominant factor is
building the priority queue.

2. Implement N-Queens problem and analyse its time complexity using backtracking.

Algorithm:

Algorithm NQueens(k, n)
{

for i := 1 to n do

if Place(k, i) then

{ x[k]==i;
if (k = n) then write (x1: n);else
NQueens(k + 1, r);
}

Algorithm Place (k, i)

// Returns true if a queen can be placed in kith row and

/ ith column. Otherwise it returns false. xl is a

// global array whose first (k - 1) values have been set.Abs(r) returns the
absolute value of r.
for i:= 1 to k - 1 do

if ((a jl = i) / / Two in the same columnor (Abs(x jl - i)

= Abs(j - k)))
/ or in the same diagonal then return false;return true;
}

Code:

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(vector<vector<int>>& board, int row, int col, int n) {

// Check if there is a queen in the same column
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}

// Check if there is a queen in the upper left diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (board[i][j] == 1) {
return false;
}
}

// Check if there is a queen in the upper right diagonal

for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}

return true;
}

bool solveNQueensUtil(vector<vector<int>>& board, int row, int n) {

if (row == n) {
// All queens are successfully placed
// Print the board configuration
cout << "Solution:\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{
cout << board[i][j] << " ";
}
cout << endl;
}
cout << endl;

// To find multiple solutions, return false here

// To find a single solution, return true here
return true;
}

bool res = false;

for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n))
{
board[row][col] = 1; // Place the queen

// Recursive call for the next row

res = solveNQueensUtil(board, row + 1, n) || res;

board[row][col] = 0; // Backtrack: Remove the queen

}
}

return res;
}

void solveNQueens(int n) {
vector<vector<int>> board(n, vector<int>(n, 0));

if (!solveNQueensUtil(board, 0, n)) {
cout << "No solution exists for N = " << n << endl;
}
}

int main() {
int n;
cout << "Enter the value of N: ";
cin >> n;

solveNQueens(n);

return 0;
}

Output:
Time Complexity:

The time complexity of the backtracking algorithm for the N-Queens problem is exponential. In the
worst case, the algorithm needs to explore all possible configurations of queens on the board.
Therefore, the time complexity is O(N!) or O(N^N), where N is the size of the board and represents
the number of queens.

3. Consider a knapsack bag where n = 4, and the values (profits) are given by {10, 12, 12, 18}
and the weights given by {2, 4, 6, 9}. The maximum weight is given by W = 15. The solution is
to find subset of objects such that the total value is maximized, and the sum of weights of
the objects does not exceed a given capacity W .(Note: Taking fraction of objects is not
allowed). Implement the above scenario using Least Cost Branch & Bound method.

Algorithm:

1.Define a struct Item to represent an item with its value, weight, and cost (value/weight ratio).

2.Implement the compare function to compare two items based on their costs.

3. Implement the knapsack function that takes the maximum weight W, a vector of items items, and
the number of items n.

4. Sort the items in descending order based on their costs using the compare function.

5.Initialize currentWeight and currentValue to 0.

6. Iterate through the items and check if adding the current item to the knapsack exceeds the
maximum weight.

7. If it does not exceed, add the item's weight and value to currentWeight and currentValue.

8. If it exceeds, calculate the remaining weight that can be added to the knapsack and add the
proportionate value based on the item's cost.

9. Return the final currentValue as the maximum value that can be obtained.
10. In the main function, define the number of items, maximum weight, values, and weights.

11.Create a vector of items using the provided values and weights.

12. Call the knapsack function with the maximum weight and the vector of items.

13. Print the maximum value that can be obtained.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
int value;
int weight;
double cost;

Item(int v, int w) : value(v), weight(w) {

cost = static_cast<double>(value) /
weight;
}
};

bool compare(Item a, Item b) {

return a.cost > b.cost;
}

int knapsack(int W, vector<Item>& items, int n) {

sort(items.begin(), items.end(), compare);

int currentWeight = 0; // Current weight in the knapsack

double currentValue = 0; // Current value in the knapsack

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

if (currentWeight + items[i].weight <= W) {
currentWeight += items[i].weight;
currentValue += items[i].value;
}
else {
int remainingWeight = W - currentWeight;
currentValue += items[i].cost * remainingWeight;
break;
}
}

return currentValue;
}
int main() {
int n = 4; // Number of items
int W = 15; // Maximum weight

vector<int> values = {10, 12, 12, 18};

vector<int> weights = {2, 4, 6,

9}; vector<Item> items;

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

items.push_back(Item(values[i], weights[i]));
}

int maxValue = knapsack(W, items, n);

cout << "The maximum value that can be obtained is: " << maxValue << endl;

return 0;
}

Output:

Time Complexity:

The time complexity of the Least Cost Branch and Bound approach for the Knapsack problem is O(n
log n), where n is the number of items. This is because the items are sorted based on their costs.