Practise D1 algorithms on lists, networks, routes, precedence tables and constraints, selecting methods and showing clear working from diagrams or data.
Figure 2
An algorithm for finding the positive real root of the equation is described by the flow chart shown in Figure 2.
Use the flow chart, with a=1, to complete the table in the answer book, stating values to at least 6 decimal places. Give the final output correct to 5 decimal places.
Given that the value of the input a is a non-negative real number,
determine the set of values for a that cannot be used to find the positive real root of using this flow chart.
Figure 2
Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.
Shortest time to travel from A to J:
Quickest route from A to J:
Use Dijkstra's algorithm to find the shortest time needed to travel from A to J.
State the quickest route.
(6)
Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer.
You do not need to find the minimum spanning tree.
Figure 2
[The total weight of the network is 458]
Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.
Use Dijkstra's algorithm to find the shortest path from A to J.
State the length of the shortest path from A to J .
The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice.
If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.
Draw the activity network described in the precedence table, using activity on arc and the minimum number of dummies.
Given that
- the activity network contains only one critical path
- activity E is on this critical path
state
which activities could never be critical,
which activities must be critical.