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).

- 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**.

- 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.