BTCS 405-18 DAA FILE 2301605
DESIGN & ANALYSIS OF ALGORITHM
LAB PRACTICAL FILE
BTCS: 405-18
SUBMITTED TO: SUBMITTED BY:
Ms Navdeep Kaur NAME: Dhruv Malhotra
Asst. Professor B.TECH CSE A (4th Sem)
(CSE DEPT). Class Roll No: 120/23
Uni Roll No: 2301605
1
BTCS 405-18 DAA FILE 2301605
INDEX
Sr. Practical Name Page No. Signature
No
1 Code and analyze solutions to following 3-4
problem with given strategies:
i. Knap Sack using greedy approach
ii. Knap Sack using dynamic approach
2 Code and analyze to find an optimal 5
solution to matrix chain multiplication
using dynamic programming.
3 Code and analyze to find an optimal 6
solution to TSP using dynamic
programming
4 Implementing an application of DFS 7-8
such as:
i. to find the topological sort of
a directed acyclic graph
ii. ii. to find a path from source
to goal in a maze.
5 Implement an application of BFS such 9-10
as:
i. to find connected
components of an undirected
graph
ii. ii. to check whether a given
graph is bipartite.
6 Code and analyze to find shortest paths 11
in a graph with positive edge weights
using Dijkstra’s algorithm.
7 Code and analyze to find shortest paths 12
in a graph with arbitrary edge weights
using Bellman-Ford algorithm
8 Code and analyze to find shortest paths 13
in a graph with arbitrary edge weights
using Flyods’ algorithm.
9 Code and analyze to find the minimum 14
spanning tree in a weighted, undirected
graph using Prims’ algorithm
10 Code and analyze to find the minimum 15-16
spanning tree in a weighted, undirected
graph using Kruskals’ algorithm.
11 Coding any real world problem or TSP 17-18
algorithm using any heuristic technique.
2
BTCS 405-18 DAA FILE 2301605
PRACTICAL1: Code and analyze solutions to following problem with given
strategies:
i. Knap Sack using greedy approach
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int value, weight;
double ratio;
};
bool cmp(Item a, Item b) {
return a.ratio > b.ratio;
}
double fractionalKnapsack(int W, vector<int> value, vector<int> weight) {
int n = value.size();
vector<Item> items(n);
for (int i = 0; i < n; i++) {
items[i] = {value[i], weight[i], (double)value[i] / weight[i]};
}
sort(items.begin(), items.end(), cmp);
double totalValue = 0.0;
for (int i = 0; i < n && W > 0; i++) {
if (items[i].weight <= W) {
W -= items[i].weight;
totalValue += items[i].value;
} else {
totalValue += items[i].ratio * W;
break;
}
}
return totalValue;
}
OUTPUT:
3
BTCS 405-18 DAA FILE 2301605
ii. Knap Sack using dynamic approach
#include <iostream>
#include <vector>
using namespace std;
int knapsackDP(int W, vector<int> value, vector<int> weight) {
int n = value.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weight[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], value[i - 1] + dp[i - 1][w - weight[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
OUTPUT:
4
BTCS 405-18 DAA FILE 2301605
PRACTICAL 2: Code and analyze to find an optimal solution to matrix chain
multiplication using dynamic programming
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int matrixChainMultiplication(vector<int> p) {
int n = p.size() - 1;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}
return dp[0][n - 1];
}
OUTPUT:
5
BTCS 405-18 DAA FILE 2301605
PRACTICAL 3: Code and analyze to find an optimal solution to TSP using dynamic
programming
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = 1e9;
int tsp(int n, vector<vector<int>>& cost) {
int fullMask = (1 << n);
vector<vector<int>> dp(fullMask, vector<int>(n, INF));
dp[1][0] = 0; // Start from city 0, only city 0 is visited
for (int mask = 1; mask < fullMask; ++mask) {
for (int u = 0; u < n; ++u) {
if (!(mask & (1 << u))) continue;
for (int v = 0; v < n; ++v) {
if (mask & (1 << v)) continue;
int nextMask = mask | (1 << v);
dp[nextMask][v] = min(dp[nextMask][v], dp[mask][u] + cost[u][v]);
}
}
}
// Return to the starting city
int ans = INF;
for (int i = 1; i < n; i++) {
ans = min(ans, dp[fullMask - 1][i] + cost[i][0]);
}
return ans;
}
OUTPUT:
6
BTCS 405-18 DAA FILE 2301605
PRACTICAL 4: Implementing an application of DFS such as:
i. to find the topological sort of a directed acyclic graph
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void dfsTopo(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>&
topoStack) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor])
dfsTopo(neighbor, adj, visited, topoStack);
}
topoStack.push(node); // postorder push
}
void topologicalSort(int V, vector<vector<int>>& adj) {
vector<bool> visited(V, false);
stack<int> topoStack;
for (int i = 0; i < V; i++) {
if (!visited[i])
dfsTopo(i, adj, visited, topoStack);
}
cout << "Topological Sort: ";
while (!topoStack.empty()) {
cout << topoStack.top() << " ";
topoStack.pop();
}
cout << endl;
}
OUTPUT:
7
BTCS 405-18 DAA FILE 2301605
ii. to find a path from source to goal in a maze
#include <iostream>
#include <vector>
using namespace std;
bool dfsMaze(int x, int y, vector<vector<int>>& maze, vector<vector<bool>>& visited, int
gx, int gy, vector<pair<int, int>>& path) {
int n = maze.size(), m = maze[0].size();
if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] || maze[x][y] == 1)
return false;
visited[x][y] = true;
path.push_back({x, y});
if (x == gx && y == gy)
return true;
if (dfsMaze(x + 1, y, maze, visited, gx, gy, path) ||
dfsMaze(x - 1, y, maze, visited, gx, gy, path) ||
dfsMaze(x, y + 1, maze, visited, gx, gy, path) ||
dfsMaze(x, y - 1, maze, visited, gx, gy, path))
return true;
path.pop_back(); // backtrack
return false;
}
OUTPUT:
8
BTCS 405-18 DAA FILE 2301605
PRACTICAL 5: Implement an application of BFS such as:
i. to find connected components of an undirected graph
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsComponent(int start, vector<vector<int>>& adj, vector<bool>& visited) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front(); q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int countConnectedComponents(int V, vector<vector<int>>& adj) {
vector<bool> visited(V, false);
int count = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
bfsComponent(i, adj, visited);
count++;
}
}
return count;
}
OUTPUT:
9
BTCS 405-18 DAA FILE 2301605
ii. to check whether a given graph is bipartite.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool isBipartite(int V, vector<vector<int>>& adj) {
vector<int> color(V, -1);
for (int start = 0; start < V; start++) {
if (color[start] == -1) {
queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
for (int neighbor : adj[node]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[node];
q.push(neighbor);
} else if (color[neighbor] == color[node]) {
return false;
}
}
}
}
}
return true;
}
OUTPUT:
10
BTCS 405-18 DAA FILE 2301605
PRACTICAL 6: Code and analyze to find shortest paths in a graph with
positive edge weights using Dijkstra’s algorithm
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii; // {distance, vertex}
vector<int> dijkstra(int V, vector<vector<pii>>& adj, int source) {
vector<int> dist(V, INT_MAX);
dist[source] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, source}); // {distance, node}
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue; // Skip if already found better
for (auto edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
OUTPUT:
11
BTCS 405-18 DAA FILE 2301605
PRACTICAL 7: Code and analyze to find shortest paths in a graph with
arbitrary edge weights using Bellman-Ford algorithm
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Edge {
int u, v, weight;
};
bool bellmanFord(int V, int E, vector<Edge>& edges, int source, vector<int>& dist) {
dist.assign(V, INT_MAX);
dist[source] = 0;
// Relax all edges V - 1 times
for (int i = 0; i < V - 1; ++i) {
for (const auto& edge : edges) {
if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
dist[edge.v] = dist[edge.u] + edge.weight;
}
}
}
// Check for negative-weight cycles
for (const auto& edge : edges) {
if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
return false; // Negative cycle found
}
}
return true; // No negative cycle
}
OUTPUT:
12
BTCS 405-18 DAA FILE 2301605
PRACTICAL 8: Code and analyze to find shortest paths in a graph with
arbitrary edge weights using Flyods’ algorithm.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = 1e9;
void floydWarshall(int V, vector<vector<int>>& dist) {
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
OUTPUT:
13
BTCS 405-18 DAA FILE 2301605
PRACTICAL 9: Code and analyze to find the minimum spanning tree in a
weighted, undirected graph using Prims’ algorithm.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii; // {weight, node}
int primMST(int V, vector<vector<pii>>& adj) {
vector<bool> inMST(V, false); // Track vertices included in MST
priority_queue<pii, vector<pii>, greater<pii>> pq; // Min-heap
pq.push({0, 0}); // Start from node 0, weight = 0
int totalCost = 0;
while (!pq.empty()) {
auto [weight, u] = pq.top();
pq.pop();
if (inMST[u]) continue;
inMST[u] = true;
totalCost += weight;
for (auto& [v, w] : adj[u]) {
if (!inMST[v]) {
pq.push({w, v});
}
}
}
return totalCost;
}
OUTPUT:
14
BTCS 405-18 DAA FILE 2301605
PRACTICAL 10: Code and analyze to find the minimum spanning tree in
a weighted, undirected graph using Kruskals’ algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight; // Sort edges by weight
}
};
class DisjointSet {
public:
vector<int> parent, rank;
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]); // Path compression
}
return parent[u];
}
void unionSets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
// Union by rank
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
15
BTCS 405-18 DAA FILE 2301605
}
};
int kruskalMST(int V, vector<Edge>& edges) {
DisjointSet ds(V);
sort(edges.begin(), edges.end()); // Sort edges by weight
int mstCost = 0;
for (const Edge& e : edges) {
int u = e.u;
int v = e.v;
int weight = e.weight;
if (ds.find(u) != ds.find(v)) {
ds.unionSets(u, v);
mstCost += weight; // Add edge to MST
}
}
return mstCost;
}
OUTPUT:
16
BTCS 405-18 DAA FILE 2301605
PRACTICAL 11: Coding any real world problem or TSP algorithm using
any heuristic technique.
#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>
using namespace std;
double euclideanDistance(int x1, int y1, int x2, int y2) {
return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}
double tspNearestNeighbor(int n, vector<pair<int, int>>& cities) {
vector<bool> visited(n, false);
double totalDistance = 0.0;
int currentCity = 0; // Start from the first city
visited[currentCity] = true;
int visitedCities = 1;
while (visitedCities < n) {
double minDist = INT_MAX;
int nextCity = -1;
// Find the nearest unvisited city
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
double dist = euclideanDistance(cities[currentCity].first,
cities[currentCity].second, cities[i].first, cities[i].second);
if (dist < minDist) {
minDist = dist;
nextCity = i;
}
}
}
// Move to the next city
visited[nextCity] = true;
totalDistance += minDist;
currentCity = nextCity;
visitedCities++;
}
17
BTCS 405-18 DAA FILE 2301605
// Return to the start city
totalDistance += euclideanDistance(cities[currentCity].first,
cities[currentCity].second, cities[0].first, cities[0].second);
return totalDistance;
}
OUTPUT:
18
