Distributed Systems Assignment 5 Solution

In this Assignment, you will write parallel codes using mpi

[100 marks]

programming. In the earlier assignment, you have setup mpi on the

system and made sure that it is working.

Language Constraint: ​C/C++

Include a bash script to run each of the code in your submission.

Name them q1.sh, q2.sh, q3.sh, q4.sh

Q 1) Parallel QuickSort.

[25 marks]

Given an array of numbers, your task is to return the array in sorted

order by implementing parallel quick sort.

Input Format​:

-> bash q1.sh `num_process` `num_elements` `elements separated

by spaces`

Output Format :

-> `elements in sorted order`

Q 2) Stable Marriage Problem

[25 marks]

Let men and women each be array of n processes. Each man ranks

the women from 0 to n-1 and each woman ranks the men from 0 to

n-1. A pairing is a one-to-one correspondence of men and women. A

pairing is stable if, for two men m1 and m2 and their paired women

w1 and w2, both of the following conditions are satisfied:

person. The first n lines corresponds to the preferences of men and

the second n lines corresponds to preferences of women.

Output Format:

Output n sorted lines (sorted wrt indices of men) with each line

denoting the matched pair. The first element of the pair corresponds

to the index of men and the second element to the matched women.

Sample:

Input:

-> bash q2.sh `num_processes`

4

3120

1023

0123

0123

0123

0123

0123

0123

Output ( Men Women):

0 3

1 1

2 0

3 4

Q 3) Single-Source Shortest Path

[25 marks]

Given a weighted graph and the node number of source, find the shortest

distance of all nodes from the source.

Input Format​:

-> bash q3.sh `num_processes`

First line of input will be number of nodes(n), number of edges(m) and

node number of source, followed by m subsequent lines each having two

nodes between which edge is present.

Output Format:

Print node number and its shortest distance from the source for each node

in graph.

Q 4) Vertex Coloring

[25 marks]

Given an undirected graph G, assign a color to every vertex such that no

two adjacent vertices have the same color.

Total number of colors should not exceed d + 1 where d is the maximum

degree of the graph.

Write an MPI program to find the optimal coloring to given graph G. The

processes should communicate using asynchronous message passing .

Input Format ​:

-> bash q4 `num_processes`

First line of input contains two integers n and m. This is followed by m lines

where each