4. (a) An industrial process requires the drilling of holes at predefined positions in a metal sheet. The holes are bore

[answerhappygod]

4 A An Industrial Process Requires The Drilling Of Holes At Predefined Positions In A Metal Sheet The Holes Are Bore 1 (150.52 KiB) Viewed 37 times

4. (a) An industrial process requires the drilling of holes at predefined positions in a metal sheet. The holes are bored by a robot arm which moves the drill from position to position. When the drilling is complete, the robot arm returns to its initial position. The same set of holes are to be drilled in many metal sheets, so minimising the time spent in movement of the robot arm is essential. How can this problem be related to graph theory and what kind of graph if any does it correspond to? (5 marks) (b) Suggest two possible data structures to represent a weighted graph when it is to be stored in RAM, and mention if one is preferable in some circumstances and why. Then illustrate how the following graph would be stored in both representations. A 3 D 7 7 6 2 (6 marks) (c) Illustrate in detail how Prim's algorithm computes a MST for the graph below showing the heap contents and the state of the arrays distance[] and parent[] at each stage. It is not necessary to show the heap tree structure at each stage, just its contents. C B 15 12 F 4 8 15 7 5 8 5 11 E 9 G (10 marks) (d) Write Prim's algorithm in pseudocode for an adjacency lists representation of a sparse graph and discuss its complexity. What would be its complexity for a dense graph? (12 marks)