Solved-Assignment IX -Solution

Description

1. In a city, name of a house is given as per the name of its owner. Moreover, a person say X is neighbor of another person say Y if you can get X from Y in following ways

1. 1. if you drop one character (from any position) from X and make any arrangement of remaining characters which results into Y ii) if you add one character in X and make any arrangement which results into Y. There are total N houses in the city. Every house requires water supply. It can be either arranged by boring a well in a house or through a pipeline from other neighboring house where there is a bore-well or if the neighboring house is connected via pipeline to some bore-well. Cost of boring a well in i^th house is w[i] and cost of pipeline between house i and j is c[i][j]. c[i][j] is infinite if i and j are not neighbor of each other otherwise c[i][j] is defined as difference between ascii sum between name of i^th and j^th house (For example if X=”Suman” and Y=”Manu” the cost of pipeline is between these two houses is ascii value of „S‟). Find a cost effective efficient solution for supplying water in all the houses of the city. Note: w[i] is the average ascii value of the i^th house, For example if name of a house is “Manu” then cost of boring a well will be sum of ascii value of „M‟, „a‟, „n‟,‟u‟ divided by 4.

Hint: Minimum Spanning Tree in this edge-weighted graph. Upload file Assignment9A.c

2. We are given a directed graph G =(V, E). Each edge (u,v) € E has an associated value r(u,v), which is a real number in the range 0 ≤ r(u,v) ≤ 1 and it represents the reliability of the communication channel from vertex u to vertex v. We interpret r(u,v) as the probability that the channel from u to v will not fail, and we assume that these probabilities are independent. Write a C program to find the most reliable path between two given vertices.

Upload file Assignment9B.c

3. Dominos wants to set few pizza restaurants in a city so that all localities (N) of that city become reachable in 30 minutes from at least one restaurant. Time taken to reach a locality say y from another locality say x depends on distance and traffic between x and y. And it can be computed as (dist(x,y)*traffic(x,y)). While traffic(x,y) varies between 0.5 to 2 and dist(x,y) is the edit distance between two localities. They choose a greedy strategy to set up restaurants. They always set up restaurant which can cover maximum localities that are not covered till now. Write a C program to show location of restaurants and the path chosen for delivery with a given traffic condition.

Upload file Assignment9C.c