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.
Table 1
Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.
Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
State the weight of the minimum spanning tree.
Table 2
Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H.
The journey time between towns E and J is x minutes where x>28
A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound.
Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer.
Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
Determine the value of x. You must make your method and working clear.
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.