Algorithm Design and Problem Solving

Project 2: Network

Hand-out 5.10., deadline: 26.10.

Story: Let us imagine you are a network expert. You are to check optimality of information flows in a network of some of your customer. The computers are already connected into a network, costs for communication in each communication channel are known (it can be a capacity, length, financial conditions...) The network contains maximally 100 nodes or computers, channel weights/costs are positive integers. Network connections may form a complete graph. We are interested in cost minimization when sending information – you are to find which from the existing communication channels should be used and which should be avoided (being too expensive).

1. Implement a suitable solution based on some of algorithmic strategies (greedy, incremental, D&C...). Is it an exact solution or a heuristic? What is its complexity? No network visualization is required, data can be read from a text file, see input format below:

nV nE i.e. 1^st row gives the total number of nodes and edges)

ei ej wij .... (i.e. n rows, each row gives 2 nodes for one edge and its cost – cost is the same in both directions)

Output to a screen or again to a textfile (output is the number of edges recommended to use and their specification in some proper format).

You gain 4 points.

2. If your solution will be maximally O(E log E), where E is the number of channels/edges, you gain another 4 points. Again it is necessary to explain and prove whether it is an exact or an approximate solution.