A group of first year computer science students are trying to create a network of six

Arduinos $($small computers$).$ Each Arduino can be connected to any of the others directly via a cable. Any Arduino can also be connected to the internet by adding a wifi module.

The students want to create a network in which every Arduino can reach the internet,

possibly passing via a number of other Arduinos through the cable connections, before reaching an Arduino with a wifi module. To achieve this, the students need to purchase wifi modules and cables of appropriate lengths to connect the Arduinos.

The Arduinos are labelled A to F$.$ Because of the locations of the arduinos in the labs,

the cost of cabling between the various Arduinos is as follows.

Connection Cost

A $$ B $10$

A $$ D $30$

A $$ E $10$

B $$ C $10$

B $$ E $20$

B $$ F $15$

C $$ F $10$

D $$ E $25$

E $$ F $5$

Where no cost is given, you may assume it is not feasible to make a direct cable connection

$($e$.$g$.$ between A and F$).$ Any connection that is made works in both directions, so for

example making the A $$ B connection also connects B to A$.$

Wifi modules may be purchased for $20.$

The students wish to find the lowest cost network that solves their problem.

a$)$ Formulate the problem as a minimum spanning tree problem and explain your

answer.

b$)$ Using Kruskal$$s algorithm, find a minimum cost solution to the problem. Draw a

diagram showing the connections between arduinos in your solution; indicate which

arduinos have a wifi module installed in your solution; and give the total cost of

cables and wifi modules.

c$)$ You go for a job interview with a large telecommunications company who are

interested to see on your CV that you have solved this problem. They have a

similar problem, involving millions of devices. The interviewer says that they think

your approach would not scale to this size of problem. Explain how the use of

effective data structures will contribute to successful solution of this problem at

scale. Mention what data structures you would use, what the complexity of the

important operations is$,$ and what the overall complexity of the algorithm would

be$.$

d$)$ Give an estimate for how much longer the algorithm would take to create a minimumcost network of $6$ million devices, compared to the $6$ Arduinos. You may assume that, even in the large scale problem, there are only three or four potential cable connections to each device.