Untitled

CSE Assignment 02

Name: MD Fahad Hossain Lam

ID: 2233081509

Batch: 60E

Date: 05/05/2024

Merge Sort:

#include <stdio.h>

void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l; while (i < n1 && j < n2) {

if (L[i] <= R[j]) { arr[k] = L[i]; i++;

} else {

arr[k] = R[j]; j++;

} k++;

}

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

}

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

}

}

void mergeSort(int arr[], int l, int r) {

if (l < r) { int m = l + (r - l) / 2;

mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r);

}

}

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

printf("Given array is: "); for (int i = 0; i < arr_size; i++) printf("%d ", arr[i]); printf("\n");

mergeSort(arr, 0, arr_size - 1);

printf("Sorted array is: "); for (int i = 0; i < arr_size; i++) printf("%d ", arr[i]); printf("\n");

return 0;

}

Graph Creation (Directed and weighted): #include <bits/stdc++.h> using namespace std;

void addEdge(vector <pair<int, int> > adj[], int u,

int v, int wt)

{

adj[u].push_back(make_pair(v, wt)); adj[v].push_back(make_pair(u, wt));

}

void printGraph(vector<pair<int,int> > adj[], int V)

{

int v, w;

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

{

cout << "Node " << u << " makes an edge with \n"; for (auto it = adj[u].begin(); it!=adj[u].end(); it++)

{

v = it->first; w = it->second;

cout << "\tNode " << v << " with edge weight ="

<< w << "\n";

}

cout << "\n";

}

}

int main()

{

int V = 5; vector<pair<int, int> > adj[V]; addEdge(adj, 0, 1, 10); addEdge(adj, 0, 4, 20); addEdge(adj, 1, 2, 30); addEdge(adj, 1, 3, 40); addEdge(adj, 1, 4, 50); addEdge(adj, 2, 3, 60); addEdge(adj, 3, 4, 70); printGraph(adj, V); return 0;

}