MetadataPastPaper.sampleTitle

(a) Initial list: \(14, 8, 22, 19, 15, 27, 11\). For descending order: Pass 1: Compare 14 and 8 (no swap), 8 and 22 (swap), 8 and 19 (swap), 8 and 15 (swap), 8 and 27 (swap), 8 and 11 (swap). List after Pass 1: \(14, 22, 19, 15, 27, 11, 8\). Pass 2: Compare 14 and 22 (swap), 14 and 19 (swap), 14 and 15 (swap), 14 and 27 (swap), 14 and 11 (no swap). List after Pass 2: \(22, 19, 15, 27, 14, 11, 8\). Pass 3: Compare 22 and 19 (no swap), 19 and 15 (no swap), 15 and 27 (swap), 15 and 14 (no swap). List after Pass 3: \(22, 19, 27, 15, 14, 11, 8\). (b) Continuing the passes: Pass 4: Compare 22 and 19 (no swap), 19 and 27 (swap), 19 and 15 (no swap). List: \(22, 27, 19, 15, 14, 11, 8\). Pass 5: Compare 22 and 27 (swap), 22 and 19 (no swap). List: \(27, 22, 19, 15, 14, 11, 8\). Pass 6: Compare 27 and 22 (no swap). List: \(27, 22, 19, 15, 14, 11, 8\). Comparisons in each pass: 6 + 5 + 4 + 3 + 2 + 1 = 21 comparisons. Swaps in each pass: 5 + 4 + 1 + 1 + 1 + 0 = 12 swaps. (c) First-fit decreasing packing with stock of length 45 cm: Sorted list: \(27, 22, 19, 15, 14, 11, 8\). Bin 1: 27 fits. 22 does not fit (27+22=49). 19 does not fit. 15 fits (27+15=42). Remaining space: 3. No other items fit. Bin 2: 22 fits. 19 fits (22+19=41). Remaining space: 4. No other items fit. Bin 3: 14 fits. 11 fits (14+11=25). 8 fits (25+8=33). Remaining space: 12.

(a) M1: First pass completed correctly. A1: Second pass correct. A1: Third pass correct. (b) M1: Clear attempt to count comparisons and swaps for all passes. A1: 21 comparisons. A1: 12 swaps. (c) M1: Sorting the list descending (from part b) and attempting first-fit. A1: Correctly placing 27, 15 in Bin 1 and 22, 19 in Bin 2. A1: Correctly placing 14, 11, 8 in Bin 3.

(a) Dijkstra's algorithm trace: Label 1 at A: value 0. Working values: B: 5, C: 6. Label 2 at B: value 5. Working values: C: 6, D: 5+4 = 9. Label 3 at C: value 6. Working values: D: 9 (since 6+4=10 is not smaller), E: 6+9 = 15. Label 4 at D: value 9. Working values: E: 9+3 = 12 (replaces 15), F: 9+6 = 15. Label 5 at E: value 12. Working values: G: 12+5 = 17. Label 6 at F: value 15. Working values: G: 17 (since 15+4=19 is not smaller). Label 7 at G: value 17. (b) Shortest path is A -> B -> D -> E -> G with length 17. (c) To find the shortest route passing through C and D: Path must go from A to C, then C to D, then D to G. Shortest A to C is AC of length 6. Shortest C to D is CD of length 4. Shortest D to G is D-E-G of length 3+5 = 8. Total length = 6 + 4 + 8 = 18. Route is A-C-D-E-G.

(a) M1: Start at A and correctly assign first two working values. A1: Correct order of labelling for vertices B, C, D. A1: Correct order of labelling for E, F, G. A1: All final values correct. (b) B1: Correct shortest path. B1: Correct length of 17. (c) M1: Realises the path must be partitioned into A-C, C-D, and D-G. A1: Correct path A-C-D-E-G and minimum length of 18.

(a) A route inspection is needed to find a trail of minimum weight that traverses every edge at least once, which is useful for tasks like road-sweeping or security patrols. Degrees of vertices: P: 2, Q: 3, R: 3, S: 5, T: 4, U: 3, V: 2. Odd vertices are Q, R, S, U. In the optimal solution, the repeated edges are QR and SU. The degree of S increases by 1 to become 6. Thus, S is visited 6 / 2 = 3 times. (b) Sum of all edges = 12 + 15 + 10 + 8 + 13 + 14 + 9 + 11 + 7 + 13 + 16 = 128. Pairings of odd vertices (Q, R, S, U): 1) QR and SU: QR (10) + SU (11) = 21. 2) QS and RU: QS (8) + RU via R-T-U (14+7=21) = 29. 3) QU and RS: QU via Q-S-U (8+11=19) + RS (13) = 32. The minimum pairing is QR and SU with sum 21. The edges to repeat are QR and SU. Total length = 128 + 21 = 149. (c) Yes, it is possible. To have a semi-Eulerian path from P to V, P and V must be the only odd vertices in the resulting network. We can pair up the 6 vertices (P, Q, R, S, U, V) so that only P and V have odd degrees in the final graph (e.g. by pairing P with an odd vertex, V with another odd vertex, and pairing the remaining two odd vertices).

(a) B1: Explanation of route inspection. M1: Finding degrees of vertices and identifying S's degree increases from 5 to 6. A1: Deduces 3 visits. (b) M1: Formulates the three pairings of the four odd vertices. A1: Correct pairings and sums (21, 29, 32). A1: Identifies QR and SU as repeated. A1: Total length 149. (c) M1: Deduces condition for starting at P and ending at V. A1: Explains that pairing all 6 vertices makes only P and V odd, hence possible.

(a) Maximize \(P = 15x + 25y\) subject to: \(3x + 4y \le 180\), \(3x + 2y \le 120\), \(x + 2y \le 70\), \(x \ge 10\), \(y \ge 0\). (b) Draw boundary lines: Line 1: \(3x + 4y = 180\) passes through (0, 45), (60, 0). Line 2: \(3x + 2y = 120\) passes through (0, 60), (40, 0). Line 3: \(x + 2y = 70\) passes through (0, 35), (70, 0). Line 4: \(x = 10\). Feasible region \(R\) is bounded by vertices: (10, 0), (10, 30) [intersection of \(x=10\) and \(x+2y=70\)], (25, 22.5) [intersection of \(x+2y=70\) and \(3x+2y=120\)], (40, 0) [intersection of \(3x+2y=120\) and \(y=0\)]. (c) Objective function: \(P = 15x + 25y\). At non-integer vertex (25, 22.5), \(P = 937.5\). Test nearby integer points: (24, 23): \(3(24)+2(23)=118 \le 120\), \(24+2(23)=70 \le 70\), \(3(24)+4(23)=164 \le 180\) (Feasible). Profit = \(15(24) + 25(23) = 935\). (25, 22): \(3(25)+2(22)=119 \le 120\), \(25+2(22)=69 \le 70\). Profit = \(15(25) + 25(22) = 925\). (22, 24): \(22+48=70 \le 70\). Profit = \(15(22) + 25(24) = 930\). Thus, the maximum profit is £935 when producing 24 Standard and 23 Deluxe boxes.

(a) B1: Correct objective function. B1: All constraints written correctly. (b) M1: Plotting at least two boundary lines correctly. A1: Correctly shading region for \(x \ge 10\) and \(y \ge 0\). A1: Identifying the boundaries of \(R\) correctly. (c) M1: Attempting to test vertices or using objective line method. A1: Testing nearby integer coordinates around (25, 22.5). A1: Correct optimal values (24, 23). A1: Correct maximum profit £935.

(a) Initial Simplex tableau equations: Row 1 (s1): \(2x + y + 3z + s_1 = 150\). Row 2 (s2): \(x + 2y + z + s_2 = 120\). Row 3 (s3): \(3x + y + 2z + s_3 = 180\). Row 4 (P): \(-40x - 30y - 35z + P = 0\). (b) Pivot column is \(x\) (most negative value is -40). Ratios: Row 1: 150/2 = 75; Row 2: 120/1 = 120; Row 3: 180/3 = 60. Row 3 has the smallest positive ratio, so the pivot is 3 in Row 3. Divide Row 3 by 3 to get New Row 3: \(x + \frac{1}{3}y + \frac{2}{3}z + \frac{1}{3}s_3 = 60\). Row operations to update other rows: New Row 1 = Old Row 1 - 2*(New Row 3) \(\implies \frac{1}{3}y + \frac{5}{3}z + s_1 - \frac{2}{3}s_3 = 30\). New Row 2 = Old Row 2 - (New Row 3) \(\implies \frac{5}{3}y + \frac{1}{3}z + s_2 - \frac{1}{3}s_3 = 60\). New Row 4 = Old Row 4 + 40*(New Row 3) \(\implies -\frac{50}{3}y - \frac{25}{3}z + \frac{40}{3}s_3 + P = 2400\). (c) The basic variables are \(x, s_1, s_2, P\). Non-basic variables are \(y, z, s_3\), which are set to 0. Therefore: \(x = 60\), \(y = 0\), \(z = 0\), \(s_1 = 30\), \(s_2 = 60\), \(s_3 = 0\), \(P = 2400\).

(a) M1: Introducing three slack variables and formulating the objective row. A1: Correct initial tableau representation. (b) M1: Identifying column x as the pivot column and calculating ratios. A1: Identifying the pivot element 3 in Row 3. A1: Correct row operations specified. A1: Correctly updated values in all rows. (c) M1: Knowing how to read basic and non-basic variable values. A1: Correct values for all variables including P.

(a) An activity-on-arc network is drawn. We need dummy activities because D depends on both A and B, while C depends only on A and E depends only on B. Let Event 1 be Start, Event 2 be End of A, Event 3 be End of B. Dummy 1 goes from 2 to 4 and Dummy 2 goes from 3 to 4. D starts at 4. Also, F depends on C and D, while G depends on D and E. D goes from 4 to 5. We use dummies from 5 to 6 (start of F, where C also ends) and from 5 to 7 (start of G, where E also ends). (b) Earliest Event Times (EST): Event 1 = 0; Event 2 = 5; Event 3 = 4; Event 4 = max(5,4) = 5; Event 5 = 5+3 = 8; Event 6 = max(5+6, 8) = 11; Event 7 = max(4+7, 8) = 11; Event 8 (start of H) = max(11+4, 11+8) = 19; Event 9 (Finish) = 19+5 = 24. Latest Event Times (LFT): Event 9 = 24; Event 8 = 19; Event 6 = 15; Event 7 = 11; Event 5 = min(15, 11) = 11; Event 4 = 11-3 = 8; Event 3 = min(11-7, 8) = 4; Event 2 = min(15-6, 8) = 8; Event 1 = min(8-5, 4-4) = 0. (c) The critical activities have zero float. B: float = 4 - 0 - 4 = 0 (critical). E: float = 11 - 4 - 7 = 0 (critical). G: float = 19 - 11 - 8 = 0 (critical). H: float = 24 - 19 - 5 = 0 (critical). Critical path: B -> E -> G -> H. Minimum completion time is 24.

(a) M1: Attempting to draw activity-on-arc with at least one dummy. A1: Correctly representing dependencies for C and E. A1: Correctly representing dependencies for D, F, G using dummies. (b) M1: Forward pass completed with at least five correct ESTs. A1: Backward pass completed with at least five correct LFTs. A1: All EST and LFT values correct. (c) M1: Calculation of floats to identify critical activities. A1: Correct critical path B-E-G-H. A1: Correct duration of 24.

(a) Gantt chart layout: Row 1: A (0-4), C (4-9), E (9-13) are critical. Row 2: B (0-3) with float shaded for (3-5). Row 3: D (4-6) with float shaded for (6-9). Row 4: F (9-12) with float shaded for (12-13). (b) The minimum project completion time is 13 hours. Sum of all activity durations = 4 + 3 + 5 + 2 + 4 + 3 = 21 worker-hours. A single worker can only work a maximum of 13 hours, so 1 worker is insufficient. With 2 workers, we can schedule: Worker 1: A (0-4), C (4-9), E (9-13); Worker 2: B (0-3), D (4-6), F (9-12). All activities are completed within their intervals. Thus, 2 workers are necessary and sufficient. (c) The total labor hours required is the sum of durations of all activities: 21 hours. Labor Cost = 21 hours * £15/hour = £315.

(a) M1: Drawing a Gantt chart layout. A1: Correctly showing critical activities A, C, E. A1: Correctly showing B, D, F with correct floats. (b) M1: Explaining why 1 worker is not enough using total activity time vs completion time. A1: Explaining how 2 workers can handle the schedule. A1: Concluding 2 workers are required. (c) M1: Multiplying total activity duration by the hourly rate. A1: Correct minimum cost £315.