COMPUTER SCIENCE & ENGINEERING

Advanced Algorithms
LAB MANUAL

CHAITANYA DEEMED TO BE UNIVERSITY

HIMAYATNAGAR MOINABAD,
RANGA REDDY, TELANGANA-500075
1. Implementation of Sorting- heap sort, quick sort, topological sort using queue in
c++
Heap sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {

for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n-1; i > 0; i--) {

swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}

int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;

int arr[n];
cout << "Enter elements:\n";
for (int i = 0; i < n; i++)

2
 cin >> arr[i];

heapSort(arr, n);
cout << "Sorted array:\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}

Quick Sort
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[high]);
return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;

3
 int arr[n];
cout << "Enter elements:\n";
for (int i = 0; i < n; i++)
cin >> arr[i];

quickSort(arr, 0, n - 1);

cout << "Sorted array:\n";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}

Topological Sort using Queue (Kahn’s Algorithm)

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

void topologicalSort(int V, vector<vector<int>>& adj) {

vector<int> indegree(V, 0);

// Calculate indegree
for (int i = 0; i < V; i++) {
for (int v : adj[i]) {
indegree[v]++;
}
}

queue<int> q;

// Push nodes with 0 indegree

for (int i = 0; i < V; i++) {
if (indegree[i] == 0)
[Link](i);
}

cout << "Topological Order:\n";

while (![Link]()) {
int u = [Link]();

4
 [Link]();
cout << u << " ";

for (int v : adj[u]) {

indegree[v]--;
if (indegree[v] == 0)
[Link](v);
}
}
}

int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;

vector<vector<int>> adj(V);

cout << "Enter edges (u v):\n";

for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}

topologicalSort(V, adj);

return 0;
}

2. Implementation of BFS using queue and DFS using stack and in both
implementations use linked list to store adjacency list of each node
BFS (Queue) + DFS (Stack) using Linked List (C++)

#include <iostream>
#include <list>
#include <queue>
#include <stack>
using namespace std;

class Graph {
int V; // Number of vertices

5
 list<int>* adj; // Adjacency list using linked list

public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}

// Add edge (directed graph)

void addEdge(int u, int v) {
adj[u].push_back(v);
}

// BFS using Queue

void BFS(int start) {
bool* visited = new bool[V];

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

visited[i] = false;

queue<int> q;
visited[start] = true;
[Link](start);

cout << "BFS Traversal: ";

while (![Link]()) {
int node = [Link]();
[Link]();
cout << node << " ";

for (int neighbor : adj[node]) {

if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
cout << endl;
}

6
 // DFS using Stack (Iterative)
void DFS(int start) {
bool* visited = new bool[V];

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

visited[i] = false;

stack<int> st;
[Link](start);

cout << "DFS Traversal: ";

while (![Link]()) {
int node = [Link]();
[Link]();

if (!visited[node]) {
cout << node << " ";
visited[node] = true;

// Push neighbors
for (int neighbor : adj[node]) {
if (!visited[neighbor])
[Link](neighbor);
}
}
}
cout << endl;
}
};

int main() {
int V, E;
cout << "Enter number of vertices: ";
cin >> V;

Graph g(V);

cout << "Enter number of edges: ";

cin >> E;

cout << "Enter edges (u v):\n";

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

7
 int u, v;
cin >> u >> v;
[Link](u, v);
}

int start;
cout << "Enter starting vertex: ";
cin >> start;

[Link](start);
[Link](start);

return 0;
}

3. Implementation of strongly connected components (Kosaraju’s Algorithm in

C++)

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

class Graph {
int V;
vector<vector<int>> adj;

public:
Graph(int V) {
this->V = V;
[Link](V);
}

void addEdge(int u, int v) {

adj[u].push_back(v);
}

// Step 1: DFS to fill stack

void fillOrder(int v, vector<bool>& visited, stack<int>& st) {
visited[v] = true;

8
 for (int u : adj[v]) {
if (!visited[u])
fillOrder(u, visited, st);
}

[Link](v);
}

// Step 2: Transpose graph

Graph getTranspose() {
Graph g(V);
for (int v = 0; v < V; v++) {
for (int u : adj[v]) {
[Link][u].push_back(v);
}
}
return g;
}

// Step 3: DFS on transposed graph

void DFS(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";

for (int u : adj[v]) {

if (!visited[u])
DFS(u, visited);
}
}

// Main function to print SCCs

void printSCCs() {
stack<int> st;
vector<bool> visited(V, false);

// Fill stack with finishing times

for (int i = 0; i < V; i++) {
if (!visited[i])
fillOrder(i, visited, st);
}

// Create transpose graph

9
 Graph gr = getTranspose();

// Mark all vertices as not visited again

fill([Link](), [Link](), false);

cout << "Strongly Connected Components:\n";

// Process all vertices in order defined by stack

while (![Link]()) {
int v = [Link]();
[Link]();

if (!visited[v]) {
[Link](v, visited);
cout << endl;
}
}
}
};

int main() {
int V, E;
cout << "Enter number of vertices: ";
cin >> V;

Graph g(V);

cout << "Enter number of edges: ";

cin >> E;

cout << "Enter edges (u v):\n";

for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
[Link](u, v);
}

[Link]();

return 0;
}

10
Sample Input
Enter number of vertices: 5
Enter number of edges: 5
02
21
10
03
34

Output
Strongly Connected Components:
012
3
4

4. Implementation of Minimum Spanning Trees

Minimum Spanning Tree (MST), examines usually two standard algorithms
Prim’s Algorithm (greedy, uses priority queue)
Kruskal’s Algorithm (greedy, uses sorting + disjoint set)

Prim’s Algorithm (Using Priority Queue)

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

typedef pair<int, int> pii; // (weight, vertex)

void primMST(int V, vector<vector<pii>>& adj) {

priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<bool> inMST(V, false);

[Link]({0, 0}); // {weight, start vertex}

int totalCost = 0;

cout << "Edges in MST:\n";

while (![Link]()) {
int weight = [Link]().first;
int u = [Link]().second;

11
 [Link]();

if (inMST[u]) continue;

inMST[u] = true;
totalCost += weight;

cout << "Include vertex: " << u << " with weight " << weight << endl;

for (auto edge : adj[u]) {

int v = [Link];
int w = [Link];

if (!inMST[v]) {
[Link]({w, v});
}
}
}

cout << "Total cost of MST: " << totalCost << endl;
}

int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;

vector<vector<pii>> adj(V);

cout << "Enter edges (u v weight):\n";

for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;

adj[u].push_back({v, w});
adj[v].push_back({u, w}); // undirected graph
}

primMST(V, adj);
return 0;
}

12
Kruskal’s Algorithm (Using Disjoint Set / Union-Find)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
int u, v, weight;
};

bool cmp(Edge a, Edge b) {

return [Link] < [Link];
}

class DSU {
vector<int> parent, rank;

public:
DSU(int n) {
[Link](n);
[Link](n, 0);
for (int i = 0; i < n; i++)
parent[i] = i;
}

int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}

void unite(int x, int y) {

int px = find(x);
int py = find(y);

if (px == py) return;

if (rank[px] < rank[py])

parent[px] = py;
else if (rank[px] > rank[py])
parent[py] = px;
else {
parent[py] = px;

13
 rank[px]++;
}
}
};

void kruskalMST(int V, vector<Edge>& edges) {

sort([Link](), [Link](), cmp);

DSU dsu(V);
int totalCost = 0;

cout << "Edges in MST:\n";

for (auto e : edges) {

if ([Link](e.u) != [Link](e.v)) {
[Link](e.u, e.v);
cout << e.u << " - " << e.v << " : " << [Link] << endl;
totalCost += [Link];
}
}

cout << "Total cost of MST: " << totalCost << endl;
}

int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;

vector<Edge> edges(E);

cout << "Enter edges (u v weight):\n";

for (int i = 0; i < E; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].weight;
}

kruskalMST(V, edges);
return 0;
}

14
5. Implementation of Maximum Sub-Array Problem, Stassen’s Matrix Multiplication
Maximum Subarray Problem (Kadane’s Algorithm)
This solves the problem of finding the contiguous subarray with the largest sum in O(n)
time.

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

int maxSubArray(vector<int>& nums) {

int max_so_far = nums[0];
int current_sum = nums[0];

for (int i = 1; i < [Link](); i++) {

current_sum = max(nums[i], current_sum + nums[i]);
max_so_far = max(max_so_far, current_sum);
}

return max_so_far;
}

int main() {
vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

cout << "Maximum Subarray Sum: " << maxSubArray(arr) << endl;
return 0;
}

Strassen’s Matrix Multiplication

Strassen’s algorithm multiplies matrices faster than the naive method:
Time Complexity ≈ O(n^2.81)
#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int>> Matrix;

// Add two matrices

Matrix add(Matrix A, Matrix B) {
int n = [Link]();
Matrix C(n, vector<int>(n));

15
 for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
return C;
}

// Subtract two matrices

Matrix subtract(Matrix A, Matrix B) {
int n = [Link]();
Matrix C(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] - B[i][j];
return C;
}

// Strassen multiplication
Matrix strassen(Matrix A, Matrix B) {
int n = [Link]();
Matrix C(n, vector<int>(n));

if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return C;
}

int k = n / 2;

Matrix A11(k, vector<int>(k)), A12(k, vector<int>(k)),

A21(k, vector<int>(k)), A22(k, vector<int>(k));
Matrix B11(k, vector<int>(k)), B12(k, vector<int>(k)),
B21(k, vector<int>(k)), B22(k, vector<int>(k));

//
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + k];
A21[i][j] = A[i + k][j];
A22[i][j] = A[i + k][j + k];

B11[i][j] = B[i][j];
B12[i][j] = B[i][j + k];

16
 B21[i][j] = B[i + k][j];
B22[i][j] = B[i + k][j + k];
}
}

// 7 multiplications
Matrix M1 = strassen(add(A11, A22), add(B11, B22));
Matrix M2 = strassen(add(A21, A22), B11);
Matrix M3 = strassen(A11, subtract(B12, B22));
Matrix M4 = strassen(A22, subtract(B21, B11));
Matrix M5 = strassen(add(A11, A12), B22);
Matrix M6 = strassen(subtract(A21, A11), add(B11, B12));
Matrix M7 = strassen(subtract(A12, A22), add(B21, B22));

// Combine results
Matrix C11 = add(subtract(add(M1, M4), M5), M7);
Matrix C12 = add(M3, M5);
Matrix C21 = add(M2, M4);
Matrix C22 = add(subtract(add(M1, M3), M2), M6);

// Join submatrices
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
C[i][j] = C11[i][j];
C[i][j + k] = C12[i][j];
C[i + k][j] = C21[i][j];
C[i + k][j + k] = C22[i][j];
}
}

return C;
}

// Print matrix
void printMatrix(Matrix A) {
for (auto row : A) {
for (auto val : row)
cout << val << " ";
cout << endl;
}
}

17
int main() {
Matrix A = {{1, 2}, {3, 4}};
Matrix B = {{5, 6}, {7, 8}};

Matrix C = strassen(A, B);

cout << "Result Matrix:\n";

printMatrix(C);

return 0;
}

6. Implementation of Shortest Path Algorithms

a) Dijkstra’s Algorithm (Greedy, no negative weights)
Best for: Non-negative weighted graphs (most common case)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

void dijkstra(int V, vector<vector<pii>>& adj, int src) {

vector<int> dist(V, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;

dist[src] = 0;
[Link]({0, src});

while (![Link]()) {
int u = [Link]().second;
int d = [Link]().first;
[Link]();

if (d > dist[u]) continue;

for (auto edge : adj[u]) {

int v = [Link];
int weight = [Link];

if (dist[u] + weight < dist[v]) {

18
 dist[v] = dist[u] + weight;
[Link]({dist[v], v});
}
}
}

cout << "Vertex Distance from Source:\n";

for (int i = 0; i < V; i++)
cout << i << " -> " << dist[i] << endl;
}

b) Bellman-Ford Algorithm (handles negative weights)

Best for: Graphs with negative weights and detecting negative cycles
#include <bits/stdc++.h>
using namespace std;

struct Edge {
int u, v, w;
};

void bellmanFord(int V, int E, vector<Edge>& edges, int src) {

vector<int> dist(V, INT_MAX);
dist[src] = 0;

// Relax edges V-1 times

for (int i = 1; i < V; i++) {
for (auto edge : edges) {
if (dist[edge.u] != INT_MAX &&
dist[edge.u] + edge.w < dist[edge.v]) {
dist[edge.v] = dist[edge.u] + edge.w;
}
}
}

// Check for negative cycles

for (auto edge : edges) {
if (dist[edge.u] != INT_MAX &&
dist[edge.u] + edge.w < dist[edge.v]) {
cout << "Negative weight cycle detected\n";
return;
}

19
 }

cout << "Vertex Distance from Source:\n";

for (int i = 0; i < V; i++)
cout << i << " -> " << dist[i] << endl;
}

c) Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Best for: Finding shortest paths between all pairs (dense graphs)

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

void floydWarshall(vector<vector<int>>& graph, int V) {

vector<vector<int>> dist = graph;

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]);
}
}
}

cout << "Shortest distances between all pairs:\n";

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}

Example Graph Input (for testing)

int main() {
int V = 5;

20
 vector<vector<pair<int,int>>> adj(V);

adj[0].push_back({1, 2});
adj[0].push_back({2, 4});
adj[1].push_back({2, 1});
adj[1].push_back({3, 7});
adj[2].push_back({4, 3});
adj[3].push_back({4, 1});

dijkstra(V, adj, 0);

return 0;
}

7. Implementation of Longest Common Subsequence.

A. LCS Length (Dynamic Programming)
Build a DP table where dp[i][j] = LCS length of first i chars of string A and first j chars
of string B
#include <bits/stdc++.h>
using namespace std;

int lcsLength(string X, string Y) {

int m = [Link]();
int n = [Link]();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}

return dp[m][n];
}

21
B. Print the Actual LCS
To reconstruct the subsequence, it will trace back from dp[m][n].

#include <bits/stdc++.h>
using namespace std;

string lcs(string X, string Y) {

int m = [Link]();
int n = [Link]();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

// Build DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}

// Reconstruct LCS
int i = m, j = n;
string lcsStr = "";

while (i > 0 && j > 0) {

if (X[i - 1] == Y[j - 1]) {
lcsStr += X[i - 1];
i--; j--;
}
else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}

reverse([Link](), [Link]());
return lcsStr;
}

22
C. Example Usage
int main() {
string X = "AGGTAB";
string Y = "GXTXAYB";

cout << "LCS Length: " << lcsLength(X, Y) << endl;

cout << "LCS String: " << lcs(X, Y) << endl;

return 0;
}
Output:
LCS Length: 4
LCS String: GTAB

8. Implementation of Matrix Chain Multiplication, Simplex Algorithm, Floyd-

Warshall algorithm.
A. Matrix Chain Multiplication (MCM)
Find minimum number of scalar multiplications needed to multiply a chain of matrices.

DP Approach
#include <bits/stdc++.h>
using namespace std;

int matrixChainMultiplication(vector<int>& p) {
int n = [Link](); // number of matrices = n-1
vector<vector<int>> dp(n, vector<int>(n, 0));

for (int len = 2; len < n; len++) {

for (int i = 1; i < n - len + 1; 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-1]*p[k]*p[j];
dp[i][j] = min(dp[i][j], cost);
}
}
}

return dp[1][n-1];
}

23
B. Simplex Algorithm (Linear Programming)
Solve linear programming problems of form
Maximize: Z = c1x1 + c2x2 + ...
Subject to constraints.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;

double tableau[MAX][MAX];
int m, n; // m constraints, n variables

void pivot(int row, int col) {

double pivot = tableau[row][col];

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

tableau[row][j] /= pivot;

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

if (i != row) {
double factor = tableau[i][col];
for (int j = 0; j <= n; j++)
tableau[i][j] -= factor * tableau[row][j];
}
}
}

bool simplex() {
while (true) {
int pivotCol = -1;
for (int j = 0; j < n; j++) {
if (tableau[m][j] < 0) {
pivotCol = j;
break;
}
}
if (pivotCol == -1) return true; // optimal

int pivotRow = -1;

double minRatio = 1e9;

24
 for (int i = 0; i < m; i++) {
if (tableau[i][pivotCol] > 0) {
double ratio = tableau[i][n] / tableau[i][pivotCol];
if (ratio < minRatio) {
minRatio = ratio;
pivotRow = i;
}
}
}

if (pivotRow == -1) return false; // unbounded

pivot(pivotRow, pivotCol);
}
}

C. Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Find shortest distances between all pairs of vertices.
#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

void floydWarshall(vector<vector<int>>& graph) {

int V = [Link]();
vector<vector<int>> dist = graph;

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]);
}
}
}

cout << "Shortest distance matrix:\n";

for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF ";

25
 else
cout << dist[i][j] << " ";
}
cout << endl;
}
}

Example Usage
int main() {
// Matrix Chain Multiplication
vector<int> dims = {10, 20, 30, 40};
cout << "MCM Min Cost: " << matrixChainMultiplication(dims) << endl;

// Floyd-Warshall
vector<vector<int>> graph = {
{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}
};

floydWarshall(graph);

return 0;
}

26