A2 June 2019 Q3
3.
In Figure 1 the weight of arc SB is denoted by \(x\) where \(x \geqslant 0\)
It is given that the minimum weight route from S to T passes through B.
| Scheme | Marks | AO |
|---|---|---|
| Dijkstra’s algorithm cannot be used on a network with negative weights | 1B1 | 3.5b |
| (1) |
Notes
1B1: CAO – Do not accept ‘Dijkstra’s cannot be used on a directed network’
Condone any reference to negative (weights) or ‘negative edges’. Also condone ‘cannot be used with positive and negative arcs.’ But NOT answers which include incorrect statements.
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
(i)
| 1B1 | 3.1a | ||||||||||||||||||||||||||||||||||||||||
| 1M1 1A1 2A1 | 3.1a 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||
| 2M1 3A1ft 4A1 | 1.1b 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||
| 3M1 5A1ft | 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||
| \(x - 30 < 24\) \((0 \leqslant)\ x < 54\) | 4dM1 6A1 | 3.1a 2.2a | ||||||||||||||||||||||||||||||||||||||||
| (ii) Route: S – B – F – J – T | 1B1 | 2.2a | ||||||||||||||||||||||||||||||||||||||||
| (12) | ||||||||||||||||||||||||||||||||||||||||||
| (13 marks) |
Notes
Throughout (b):
- Condone lack of destination column and/or reversed stage numbers throughout
- Only penalise incorrect result in value – ie ignore working values
- Penalise absence of state or action column with first two A marks earned only
- Penalise empty/errors in stage column with first A mark earned only
- Penalise occurrence of single errors in state/action/destination with the relevant A mark - once only.
- Interchanged state and destination columns penalise with first two A marks
M marks - must bring earlier optimal results into calculations at least once per stage
1B1: Stage 0 correct
1M1: Stage 1 completed with 3 states and at least 7 rows. Bod if something in each cell
1A1: any two states in Stage 1 correct
2A1: CAO all 3 states correct in Stage 1 (must be 7 rows and no extra rows)
2M1: Stage 2 completed with 3 states and at least 6 rows. Bod if something in each cell
3A1ft: CAO any 2 states correct in Stage 2 on the follow through
4A1: CAO all 3 states in Stage 2 (no extra rows) (corrected from the printed mark scheme, which says “Stage 1” here)
3M1: Stage 3 completed with 1 state and at least 3 rows. Bod if something in each cell
5A1ft: CAO for Stage 3 following through their optimal values (no extra rows)
4dM1: Dependent on scoring 3rd method mark and at least one of the first two method marks. Award for forming a correct inequality using their SB and the least of their SA and their SC. Allow \(\leqslant\) for this mark. Must follow from stage 3 in their table. So M0 if no \(x\) appears in stage 3. This M mark could be implied, however by ‘\(x < 54\)’ if stage 3 is correct.
6A1: CSO correct deduction of range of possible values of \(x\). Strict inequality required for this mark.
1dB1: Correct route. Dependent on 3rd method mark.
SC in part b:
Minimax/Maximin approach
Could score a maximum of B1 M1A0A0 M1A0A0 M1A0 M0A0 (max 4 marks) for the following:
1M1: Stage 1 completed with 3 states and at least 7 rows. Bod if something in each cell
2M1: Stage 2 completed with 3 states and at least 6 rows. Bod if something in each cell
3M1: Stage 3 completed with 1 state and at least 3 rows. Bod if something in each cell
NB must bring earlier optimal results into calculations at least once per stage for each M mark.