Exam Q Flashcards
State three differences between Prim’s algorithm and Kruskal’s algorithm.
1) Kruskal starts with the shortest arc, Prim starts with any node.
2) You have to check for cycles when using loops, not with prim
3) Prim can be used when the network is given in matrix form.
define tree (kuskall)
a tree is a connected graph with no cycles
define minimum spanning tree
a tree which includes all the nodes and has a minimum weight
how do you know if your minimum spanning tree is unique. Justify your answer. (kuskall)
its not unique if one path of the same length has been chosen over another path of the same length
State whether your minimum spanning tree is unique. Justify your answer. (model answer) (june 2011)
The tree is not unique because EF could have been chosen instead of CF
Explain why a complete matching is not possible.
both K and G can only be allocated to R
define the term ‘total float’
the total float is the total amount of time that an activity can be delayed from its early start without delaying the project finish time.
Total float = latest finish – earliest start – duration of activity
2 reasons for needing a dummy
1st reason – no two activities must share the same start and end event
2nd reason – J depends on D and G but I depends on D only
Explain how you determined your shortest route from your labelled diagram.
(Dijkstra)
do what you do when highlighting backwards to find route
last value-path length=previous value: write path.
so just write:
71 – 12 = 59 : GH
59 – 10 = 49 : EG
49 – 10 = 39 : FE
39 – 15 = 24 : DF
24 – 13 = 11 : CD
11 – 11 = 0 : AC
*the routes are written in order as if you were going from the start to finish, not backwards like how you find the path.
The track between E and F is now closed for resurfacing and cannot be used.
(Dijkstra)
find whichever path is closed then choose a new route that goes to the end of the closed path, then carry on along the original route you had found to be the shortest originally.
IN SHORT: get the original route, then find the shortest way to bypass the closed route, then carry on along the original route.
By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
Between days 7 and 16, there are 9 days to do work. With 3 workers you can get (3x9) 27 days work done.
Activities C, D, E, F, G, H, I and 4 days of J are all between days 7 and 16 and need to be done. adding up the total job duration of all jobs, it would be 31 days work.
since 3 workers can only do 27 days work, it is not possible to complete the project with three workers.
with binary search, how do you end every question
you MUST write:
single item list so 7 | L.
then..
search complete + ‘found’
Explain why J, rather than C1 or C2, should be chosen as the starting vertex.
We would only need to apply Dijkstra’s algorithm once.
use your gannt chart to determine the minimum number of workers required to complete the process in the minimum time.
four workers are required because at day 14.5; I, E, H and C MUST all be happening.
look for any events that cannot be moved out the way, it doesn’t really matter what day it takes place on as long as you state the day and how many actvities are taking place. e.g. you could just as well have said on day 15…
Define ‘bipartite graph’
A graph which consists of two sets of vertices, where the edges only join vertices to the other set, not vertices within a set
