Network Algorithms

Question 1

What are the six steps to Prims algorithm (graphically) ?

Answer 1

Question 2

Answer 2

Question 3

What are some common errors in doing prims algorithm graphically?

Answer 3

• not starting from specific node given in the question
• forming a cycle by accident
• not looking at all the connected vertices
• not showing working out of each edge
• not stating the total weight

Question 4

What are the steps to Prims algorithm (tabular)?

Answer 4

Question 5

What are some common errors when doing Prims Algorithm (tabular)

Answer 5

• not deleting a row
• not looking down on all the avaible rows
• not recording edges and weights
• not showing working out
• not stating the total weight of MST

Question 6

Answer 6

Question 7

What is a greedy algorithm?

Answer 7

it maximises the immediate rewards without considering future choices/consequences

Question 8

Why are the steps for carrying out Kruskal’s algorithm?

Answer 8

Question 9

What are the common errors in kruskals algorithm?

Answer 9

• not listing the order of arcs
• accidentally forming cycles (constnatly look at the graph)

Question 10

Why can kruskals algorithm not be used in tabular form?

Answer 10

no way of knowing when cycle will be made

∴ cannot be used by computers

Question 11

Answer 11

Question 12

Answer 12

Question 13

what is a common mistake in dijkstras?

Answer 13

not starting the order of becoming permenant from 1

this is dijkstras not critical path

Question 14

What are the steps for Dijkstra’s algorithm?

Answer 14

Question 15

Answer 15

Question 16

How would you find the shortest route and length from this completed

Answer 16

Question 17

what is the complexity of kruksals, primms and dijksras?

Answer 17

O (n^^2)
* Dijkstra’s is as a function of number of vertices
* Primms/ Kruksals is a function of the number of edges

Question 18

Answer 18

Question 19

What is the shortest distance from A-E and A-F

Answer 19