**(a)** $y \leq 16$ and $y \leq 2x$ | B1; M1 A1 | (3)

**(b)** $4x + 3y \leq 120$ | M1 A1 | (2)

**(c)** $x \leq \frac{3}{4}(x + y)$ so $4x \leq 3x + 3y$ so $x \leq 3y$ | M1 A1 | (2)

**(d)** The correct two lines ($4x + 3y = 120$, $x = 3y$)
R labelled correctly | B1 B1 B1 | (3)

**(e)** $(P = )45x + 30y$ | B1 | (1)

**(f)** At (0,0) $P = 0$
At (8, 16) $P = 840$
At (18, 16) $P = 1290$
At (24, 8) $P = 1320$ | M1 A1 (any 2) A1 (any 3) A1 (all 4) |

**(g)** So optimal point is (24, 8) giving (£)1 320 | B1 | (5)

---

# Notes for Questions

**Question 1 Notes:**
- a1M1: An alternating path from C to 6 or vice versa
- a1A1: CAO – a correct path including change status (stated or shown) with all symbols interchanged
- a2A1: CAO must follow from correct stated path. Accept on clear diagram (with five arcs only)
- b1B1: A good, clear, complete, correct answer (all relevant nodes must be referred to and must be correct)
- c1M1: An alternating path from A to 3 or vice versa
- c1A1: CAO including change status (stated or shown), chosen path clear
- c2A1: CAO must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on clear diagram (with six arcs only)

**Question 2 Notes:**
- a1M1: Prim's – first three arcs correctly chosen or first four nodes correctly chosen, in order. Any rejections seen during selection is M0. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, -,  -}
- a1A1: First four arcs correctly chosen or all six nodes correctly chosen {A, B, C, D, F, E}. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, 5, 6}
- a2A1: CSO (must be considering arcs for this final mark)

**Misread:** Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct.

| Starting at | Minimum arcs required for M1 | Nodes | order |
|---|---|---|---|
| A | AB BC BD | ABCD(FE) | 1234(65) |
| B | AB BC BD | BACD(FE) | 2134(65) |
| C | BC AB BD | CBAD(FE) | 3214(65) |
| D | BD AB BC | DBAC(FE) | 3241(65) |
| E | EF BF AB | EFBA(CD) | 43(56)12 |
| F | EF BF AB | FEBA(CD) | 43(56)21 |

- b1B1: CAO (weights on arcs not required)
- c1B1: CAO (condone lack of/incorrect units)
- d1B1: One correct statement
- d2B1: A second correct statement
- d3B1: A third correct statement

In part (d) all technical language must be correct (so do not condone point for vertex/node etc.)

**Question 3 Notes:**
- a1M1: All top boxes complete, values generally increasing left to right, condone one rogue
- a1A1: CAO
- a2M1: Bottom boxes complete, values generally decreasing right to left, condone missing 0 or 37 for the M mark only
- a2A1: CAO
- b1M1: Correct calculation seen. All three numbers correct (ft)
- b1A1: Float correct (no follow through on this mark)
- c1M1: Attempt to find lower bound. [$82 - 104 / $ their finish time] accept awrt 2.5
- c1A1: CAO – correct calculation seen or awrt 2.5, then 3. (Beware 37/13 gives 3 also, so 3 with no working gets M0A0.)
- d1M1: Not a cascade chart. 4 workers used at most. At least 8 new (10 in total) activities placed
- d1A1: The critical activities (F I K M) and B correct. F – 8; I – 9; K – 5; M – 6; B – 7. B completed by 9 (its late finish time)

Now check the last 6 activities – the last two marks are for D, E, G, H, J and L only

First check that there are only three workers and that all 11 new (13 in total) activities are present (just once).

Then check precedences (see table below) – each row of the table could give rise to 1 error only in precedences

Finally check the length of each activity (see number in brackets in the activity column in the table below)

| Activity | I.P.A | Activity | I.P.A |
|---|---|---|---|
| A (8) | - | H (5) | C |
| B (7) | - | I (9) | E F |
| C (9) | - | J (11) | G H |
| D (9) | A | K (5) | D I |
| E (5) | A | L (4) | D I |
| F (8) | B C | M (6) | E F J K |
| G (7) | B C | | |

- d2M1: 3 workers. All 11 new (13 in total) activities present (just once). Condone one error either precedence, or activity length, on activities D, E, G, H, J and L.
- d2A1: 3 workers. All 11 new (13 in total) activities present (just once). No errors on activities D, E, G, H, J and L.

**Question 4 Notes:**
- a1M1: Quick sort – pivots, p, selected and first pass gives <p, p, >p
- a1A1: First two passes correct, pivots chosen consistently for third pass
- a2A1: CAO sort completed correctly
- a3A1: 'Stop' + correct name for their sort – phonetically close
- b1M1: Using their 'sorted list' + choosing middle right pivots+ discarding/retaining half the list. If their list contains one error (one error is either a missing letter, an extra letter or one letter incorrectly placed) then M1 only in part (b)
- b1A1: First pass correct i.e. 6th item from a correct list and retaining L – T (no sticky pivots)
- b2A1: Second and third passes correct i.e. 9th (S) and 8th (P) items from a correct list (no sticky pivots)
- b3A1: CSO search complete + 'found'

**Additional solutions:**

Quick sort middle left: Pivot C, then pivots (A) and K, then pivots H and P, then pivots (D, J, L) and S, sort completed and named correctly.

Bubble sort left to right: T in place consistent direction, passes 1 and 2 correct, sort correct, sort named correctly + 'stop'.

Bubble sort right to left: A in place, consistent direction, passes 1 and 2 correct, sort correct, sort named correctly + 'stop'.

Sorting into reverse alphabetical order is acceptable for full marks

**Question 5 Notes:**
- a1M1: Three distinct pairings of their four odd nodes
- a1A1: Any one row correct including pairing and total
- a2A1: Any two rows correct including pairing and total
- a3A1: All three rows correct including pairing and total
- a4A1: CAO correct arcs specified AB, BF and GH. Accept ABF or AF via B (check to see if via B appears in working) but do not accept AF for this mark
- b1B1: Any correct route (checks: 17 nodes, the route starts and ends at A, pairings AB, BF and GH appear twice in the route and every letter from A to H (inclusive) appears at least once)
- b2B1 ft: correct answer of 227 or 181 + their least out of a choice of at least two totals given in part (a)
- c1M1: Identifies need to repeat one pairing (maybe implicit) and 15 (or either AF or FH) specifically identified as the least
- c1A1: Repeat (either AF or FH) identified clearly
- c2A1: G and either A or H identified as start and finish

**Question 6 Notes:**
- a1M1: 7 activities and one dummy placed. Must be considering activity on arc (activity on node is M0)
- a1A1: One start + A, B, C, D and E dealt with correctly
- a2A1: F, G, H, I and J and 1st dummy dealt with correctly
- a3A1: K and 2nd dummy dealt with correctly
- a4A1: CSO - all arrows present and correctly placed with one finish
- b1B1: First dummy correctly described (C, D, F and G referred to)
- b2B1: Second dummy correctly described (mention of 'uniqueness' alone is not sufficient for this mark)

**Question 7 Notes:**
- a1B1: CAO
- b1M1: A larger value replaced by a smaller value at least once in the working values at either G, E, D, $C_1$ or $C_2$
- b1A1: All values in G, H, I and J correct. The working values at G must be in the correct order. Condone lack of 0 in the working value at J
- b2A1: All values in D, E and F correct and the working values in the correct order. Penalise order of labelling only once per question. (F, E and D labelled in that order with G, H, I and J labelled before F)
- b3A1 ft: All values in $C_1$ and $C_2$ ft correct and the working values in the correct order. Penalise order of labelling only once per question. ($C_2$ labelled after all other nodes (D to J) – condone lack of final value for $C_1$)
- b4A1: Route CAO
- b5A1 ft: Their final value ft (if answer is not 48 ft their final value at either $C_1$ or $C_2$ dependent on their route)

If the candidate uses either $C_1$ or $C_2$ as the starting vertex then this is not a misread. They can score a maximum of M1A0A0A0A1A1 ft. If starting at:
- $C_1$ – M1 for a larger value replaced by a smaller value at either $C_2$, F, G, H, I or J, then A0 A0 A0 then A1 for the route ($C_1$DFGIJ) and then A1 for 49 (or ft their final value at J)
- $C_2$ – M1 for a larger value replaced by a smaller value at either $C_1$, F, G, H, I or J, then A0 A0 A0 then A1 for the route ($C_2$ EFGIJ) and then A1 for 48 (or ft their final value at J)

If the candidate uses both $C_1$ and $C_2$ as the starting vertices then award M1 for a larger value replaced by a smaller value at either F, G, H, I or J, then A0 A0 then A1 for the correct route only ($C_2$EFGIJ) and A1 for 48 (no ft).