Advanced Data Structures and Algorithms Analysis Lab

Exercise :5

A C# program to find biconnected components in a given Graph

// A C# program to find biconnected components in a given undirected graph.

// This class represents a directed graph using adjacency list representation public class Graph.

{
private int V, E; // No. of vertices & Edges respectively
private List<int> []adj;

// Count is number of biconnected components. time is used to find discovery times.

int count = 0, time = 0;

class Edge
{
public int u;
public int v;
public Edge(int u, int v)
{
this.u = u;
this.v = v;
}
};

// Constructor
public Graph(int v)
{
V = v;
E = 0;
adj = new List<int>[v];
for (int i = 0; i < v; ++i)
adj[i] = new List<int>();
}

// Function to add an edge into the graph

void addEdge(int v, int w)
{
adj[v].Add(w);
E++;
}

void BCCUtil(int u, int []disc, int []low, List<Edge> st,

int []parent)
{

// Initialize discovery time and low value

disc[u] = low[u] = ++time;
int children = 0;

// Go through all vertices adjacent to this

foreach(int it in adj[u])
{
int v = it; // v is current adjacent of 'u'

// If v is not visited yet, then recur for it

if (disc[v] == -1)
{
children++;
parent[v] = u;

// store the edge in stack

st.Add(new Edge(u, v));
BCCUtil(v, disc, low, st, parent);

// Check if the subtree rooted with 'v' has a connection to one of the ancestors of 'u'.
// Case 1 -- per Strongly Connected Components Article
if (low[u] > low[v])
low[u] = low[v];

// If u is an articulation point, pop all edges from stack till u – v.

if ((disc[u] == 1 && children > 1) ||

(disc[u] > 1 && low[v] >= disc[u]))
{
while (st[st.Count-1].u != u ||
st[st.Count-1].v != v)
{
Console.Write(st[st.Count - 1].u + "--" +
 st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);
}
Console.WriteLine(st[st.Count - 1].u + "--" +
st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);

count++;
}
}

// Update low value of 'u' only if 'v' is still in stack (i.e. it's a back edge, not cross edge).
// Case 2 -- per Strongly Connected Components Article
else if (v != parent[u] && disc[v] < disc[u] )
{
if (low[u] > disc[v])
low[u] = disc[v];

st.Add(new Edge(u, v));

}
}
}

// The function to do DFS traversal. It uses BCCUtil()

void BCC()
{
int []disc = new int[V];
int []low = new int[V];
int []parent = new int[V];
List<Edge> st = new List<Edge>();

// Initialize disc and low, and parent arrays.

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

{
disc[i] = -1;
low[i] = -1;
parent[i] = -1;
}

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

{
if (disc[i] == -1)
BCCUtil(i, disc, low, st, parent);
 int j = 0;

// If stack is not empty, pop all edges from stack.

while (st.Count > 0)

{
j = 1;
Console.Write(st[st.Count - 1].u + "--" +
st[st.Count - 1].v + " ");
st.RemoveAt(st.Count - 1);
}
if (j == 1)
{
Console.WriteLine();
count++;
}
}
}

// Driver code
public static void Main(String []args)
{
Graph g = new Graph(12);
g.addEdge(0, 1);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(2, 1);
g.addEdge(1, 3);
g.addEdge(3, 1);
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(2, 4);
g.addEdge(4, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(1, 5);
g.addEdge(5, 1);
g.addEdge(0, 6);
g.addEdge(6, 0);
g.addEdge(5, 6);
g.addEdge(6, 5);
g.addEdge(5, 7);
g.addEdge(7, 5);
g.addEdge(5, 8);
g.addEdge(8, 5);
g.addEdge(7, 8);
 g.addEdge(8, 7);
g.addEdge(8, 9);
g.addEdge(9, 8);
g.addEdge(10, 11);
g.addEdge(11, 10);

g.BCC();

Console.WriteLine("Above are " + g.count +

" biconnected components in graph");
}
}
Exercise : 6

Implement Quick Sort and merge sort and observe the execution time for various input
sizes(Average, Worst, and Best Cases.

1) Quick Sort
#include <stdio.h>
int partition (int a[], int start, int end)
{
int pivot = a[end]; // pivot element
int i = (start - 1);

for (int j = start; j <= end - 1; j++)

{
// If current element is smaller than the pivot
if (a[j] < pivot)
{
i++; // increment index of smaller element
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}

/* function to implement quick sort */

void quick(int a[], int start, int end)

/* a[] = array to be sorted, start = Starting index, end = Ending index */

{
if (start < end)
{
int p = partition(a, start, end); //p is the partitioning index
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
 /* function to print an array */
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}

2) Merge Sort
// C program for the implementation of merge sort
#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].

// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int leftArr[n1], rightArr[n2];

// Copy data to temporary arrays

for (i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0;
j = 0;
 k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
}
else {
arr[k] = rightArr[j];
j++;
}
k++;
}

// Copy the remaining elements of leftArr[], if any

while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}

// Copy the remaining elements of rightArr[], if any

while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}

// The subarray to be sorted is in the index range [left-right]

void mergeSort(int arr[], int left, int right) {
if (left < right) {

// Calculate the midpoint

int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
 int n = sizeof(arr) / sizeof(arr[0]);

// Sorting arr using mergesort

mergeSort(arr, 0, n - 1);

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

printf("%d ", arr[i]);
return 0;
}
Exercise 7:

Compare the performance of single source shortest paths using Greedy method when the graph is
represented by adjacent matrix and adjacency lists.

/ C program for Dijkstra's single source shortest path algorithm. The program is for
adjacency matrix representation of the graph

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 9

// A utility function to find the vertex with minimum

// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

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

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance array

void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t\t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

 dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

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

if (!sptSet[v] && graph[u][v]
&& dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}

// driver's code
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

// Function call
dijkstra(graph, 0);

return 0;
}
Exercise :8

Implement Job sequencing with deadlines using greedy method.

// C program for the above approach
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a job

typedef struct Job {

char id; // Job Id

int dead; // Deadline of job
int profit;
} Job;

// This function is used for sorting all jobs according to

// profit
int compare(const void* a, const void* b)
{
Job* temp1 = (Job*)a;
Job* temp2 = (Job*)b;
return (temp2->profit - temp1->profit);
}

// Find minimum between two numbers.

int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}

// Returns maximum profit from jobs

void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to decreasing order of profit
qsort(arr, n, sizeof(Job), compare);

int result[n]; // To store result (Sequence of jobs)

bool slot[n]; // To keep track of free time slots

// Initialize all slots to be free

for (int i = 0; i < n; i++)
slot[i] = false;

// Iterate through all given jobs

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

// Find a free slot for this job (Note that we start

// from the last possible slot)
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

// Free slot found

if (slot[j] == false) {
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}

// Print the result

for (int i = 0; i < n; i++)
if (slot[i])
printf("%c ", arr[result[i]].id);
}

// Driver's code
int main()
{
Job arr[] = { { 'a', 2, 100 },
{ 'b', 1, 19 },
{ 'c', 2, 27 },
{ 'd', 1, 25 },
{ 'e', 3, 15 } };
int n = sizeof(arr) / sizeof(arr[0]);
printf(
"Following is maximum profit sequence of jobs \n");

// Function call
printJobScheduling(arr, n);
return 0;
}
Exercise :9

A c program to solve 0/1 knapsack problem using dynamic programming.

/* A Naive recursive implementation of 0-1 Knapsack problem */

#include <stdio.h>

// A utility function that returns maximum of two integers

int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W

int knapSack(int W, int wt[], int val[], int n)

{
// Base Case
if (n == 0 || W == 0)
return 0;

if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases: (1) nth item included, (2) not included.

else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver code
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
printf("%d", knapSack(W, weight, profit, n));
return 0;
}
Exercise : 10

Implement N Queens problem using back tracking.

// C program to solve N Queen Problem using backtracking

#define N 4
#include <stdbool.h>
#include <stdio.h>

// A utility function to print solution

void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(board[i][j])
printf("Q ");
else
printf(". ");
}
printf("\n");
}
}

bool isSafe(int board[N][N], int row, int col)

{
int i, j;

// Check this row on left side

for (i = 0; i < col; i++)
if (board[row][i])
return false;

// Check upper diagonal on left side

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

// Check lower diagonal on left side

for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;

return true;
}
bool solveNQUtil(int board[N][N], int col)
{
// Base case: If all queens are placedthen return true
if (col >= N)
return true;

// Consider this column and try placingthis queen in all rows one by one
for (int i = 0; i < N; i++) {

// Check if the queen can be placed on board[i][col]

if (isSafe(board, i, col)) {

// Place this queen in board[i][col]

board[i][col] = 1;

// Recur to place rest of the queens

if (solveNQUtil(board, col + 1))
return true;

board[i][col] = 0; // BACKTRACK
}
}
return false;
}
bool solveNQ()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}

printSolution(board);
return true;
}
// Driver program to test above function
int main()
{
solveNQ();
return 0;
}
Exercise 11

Use back tracking strategy to solve 0/1 knapsack problem

// C Program for 0-1 KnapSack Problem using Recursion

#include <stdio.h>

// Function to find maximum between two numbers

int max(int a, int b)
{
if (a > b)
return a;
return b;
}

{
// Base Case
if (n == 0 || W == 0)
return 0;

if (wt[n - 1] > W)
return knapsackRecursive(W, wt, val, n - 1);

else
return max(val[n - 1]
+ knapsackRecursive(W - wt[n - 1],
wt, val, n - 1),
knapsackRecursive(W, wt, val, n - 1));
}
// Driver Code
int main()
{
int values[] = { 3, 4, 5, 6 };
int weight[] = { 2, 3, 4, 5 };
int W = 8;
// Find the number of items
int n = sizeof(values) / sizeof(values[0]);

// Output the maximum profit for the knapSack

printf(
"Maximum value that can be put in knapsack: %d\n",
knapsackRecursive(W, weight, values, n));

return 0;
}
Exercise 12

Implement travelling sales person problem using branch and bound approach.

/ C# program to solve Traveling Salesman Problem

// using Branch and Bound.
using System;

public class GFG {

static int N = 4;

// final_path[] stores the final solution ie, the path of the salesman.
static int[] final_path = new int[N + 1];

// visited[] keeps track of the already visited nodes in a particular path.

static bool[] visited = new bool[N];

// Stores the final minimum weight of shortest tour.

static int final_res = Int32.MaxValue;

// Function to copy temporary solution to the final solution.

static void copyToFinal(int[] curr_path)

{
for (int i = 0; i < N; i++)
final_path[i] = curr_path[i];
final_path[N] = curr_path[0];
}

// Function to find the minimum edge cost having an end at the vertex i
static int firstMin(int[, ] adj, int i)
{
int min = Int32.MaxValue;
for (int k = 0; k < N; k++)
if (adj[i, k] < min && i != k)
min = adj[i, k];
return min;
}

// function to find the second minimum edge cost having an end at the vertex i
static int secondMin(int[, ] adj, int i)
{
int first = Int32.MaxValue, second = Int32.MaxValue;
 for (int j = 0; j < N; j++) {
if (i == j)
continue;

if (adj[i, j] <= first) {

second = first;
first = adj[i, j];
}
else if (adj[i, j] <= second
&& adj[i, j] != first)
second = adj[i, j];
}
return second;
}

static void TSPRec(int[, ] adj, int curr_bound,

int curr_weight, int level,
int[] curr_path)
{
// base case is when we have reached level N which means we have covered all the nodes once.
if (level == N) {
// check if there is an edge from last vertex in path back to the first vertex.
if (adj[curr_path[level - 1], curr_path[0]]
!= 0) {
// curr_res has the total weight of the solution we got.
int curr_res = curr_weight
+ adj[curr_path[level - 1],
curr_path[0]];

// Update final result and final path if current result is better.

if (curr_res < final_res) {
copyToFinal(curr_path);
final_res = curr_res;
}
}
return;
}

// for any other level iterate for all vertices to build the search space tree recursively.
for (int i = 0; i < N; i++) {
if (adj[curr_path[level - 1], i] != 0
&& visited[i] == false) {
int temp = curr_bound;
curr_weight += adj[curr_path[level - 1], i];

// different computation of curr_bound for

 // level 2 from the other levels
if (level == 1)
curr_bound
-= ((firstMin(adj,
curr_path[level - 1])
+ firstMin(adj, i))
/ 2);
else
curr_bound
-= ((secondMin(adj,
curr_path[level - 1])
+ firstMin(adj, i))
/ 2);

if (curr_bound + curr_weight < final_res) {

curr_path[level] = i;
visited[i] = true;

TSPRec(adj, curr_bound, curr_weight,

level + 1, curr_path);
}

// Else we have to prune the node by resetting all changes to curr weight and curr_bound.
curr_weight -= adj[curr_path[level - 1], i];
curr_bound = temp;

// Also reset the visited array

Array.Fill(visited, false);
for (int j = 0; j <= level - 1; j++)
visited[curr_path[j]] = true;
}
}
}

// This function sets up final_path[]

static void TSP(int[, ] adj)
{
int[] curr_path = new int[N + 1];

int curr_bound = 0;
Array.Fill(curr_path, -1);
Array.Fill(visited, false);

// Compute initial bound

for (int i = 0; i < N; i++)
curr_bound
 += (firstMin(adj, i) + secondMin(adj, i));

// Rounding off the lower bound to an integer

curr_bound = (curr_bound == 1) ? curr_bound / 2 + 1
: curr_bound / 2;

// We start at vertex 1 so the first vertex

// in curr_path[] is 0
visited[0] = true;
curr_path[0] = 0;

// Call to TSPRec for curr_weight equal to

// 0 and level 1
TSPRec(adj, curr_bound, 0, 1, curr_path);
}

// Driver code
static public void Main()
{
// Adjacency matrix for the given graph
int[, ] adj = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };

TSP(adj);

Console.WriteLine("Minimum cost : " + final_res);

Console.Write("Path Taken : ");
for (int i = 0; i <= N; i++) {
Console.Write(final_path[i] + " ");
}
}
}