OCR (not MEI) D1 24th May 2013

I've got the paper, don't know when I'm allowed to upload it though, dont you have to wait a day or something?

I've got the paper, don't know when I'm allowed to upload it though, dont you have to wait a day or something?

I've got the paper, don't know when I'm allowed to upload it though, dont you have to wait a day or something?

I've got the paper, don't know when I'm allowed to upload it though, dont you have to wait a day or something?

I've got the paper, don't know when I'm allowed to upload it though, dont you have to wait a day or something?

Work so far, will be continued if paper re-uploaded:

Unofficial Mark Scheme

1i) $24 \ 57 \ 9 \ 31 \ 16 \ 4$

$24 \ 9 \ 57 \ 31 \ 16 \ 4$

$24 \ 9 \ 31 \ 57 \ 15 \ 4$

$24 \ 9 \ 31 \ 15 \ 57 \ 4$

$24 \ 9 \ 31 \ 15 \ 4 \ 57$

Circles where necessary to indicate comparisons. (2 marks)

ii) $Pass \ 2 \ : \ 9 \ 24 \ 15 \ 4 \ 31 \ 57$

$Pass \ 3 \ : \ 9 \ 15 \ 4 \ 24 \ 31 \ 57$

(2 marks)

iii) Pass 1 - 4 swaps, Pass 2 - 3 swaps, Pass 3 - 2 swaps , Pass 4 - 1 swap, Pass 5 -1 swap (2 marks)

2i)a) Square plus a loop at one vertex for example (1 mark)

b) Max vertex order for simple graph with 4 vertices is 3, but is Eulerian so order has to be 2 (as 0 means one vertex is not connected). Hence total order = 4x2 = 8. 8/2 = 4, so 4 arcs, not 5 arcs. (2 marks)

ii)a) Total order = 2 x no. of arcs = 2 x 10 = 20 (1 mark)

b) Max - 6, min - 2, and correct graph drawn (3 marks)

c) Two vertices of order 4, six of order 2. (1 mark)

3i) Correct trace through the algorithm, yielding outputs 6 and 90. (6 marks)

Can you please upload it again at least for around half an hour so I can finish the mark scheme. Thanks.

How did you manage to get the paper btw, did you ask a teacher or just strolled out with it.

Just put it in my pocket and walked out

LOL but at the end don't the invigilators collect them in? they do at my college they collect everything off the desks that's not ours then tell us to leave.

They come round and get all of the papers and formulae books, I just handed the invigilator the formula book and he didn't care. Loads of people at my college always take maths papers out

Oh, well it's easier when they do that. At my college one invigilator collects collects formula books, one question papers and the other answer booklets! I asked if I could take it once but he said no.

What I can remember:

Bubble sort:
1i) First pass correct with correct comparisons and swaps.
ii) Second and third pass correct.
iii) Pass 1 - 4 swaps
Pass 2 - 3 swaps
Pass 3 - 2 swaps
Pass 4 - 1 swap
Pass 5 - 1 swap

Eulerian Graphs:

2

i) Maximum = 6 arcs
Minimum = 2 arcs

ii) Correct drawing with one vertex order 6.

iii) Order = no. of arcs = 10 x 2 = 20

iv) Correct drawing, two vertices with order 4 and other order 2.


3.i) Trace the algorithm, outputs 6 and 90.
ii) Fill in table, values the same as in part i) until it comes to dividing by A. Nevertheless outputs are still 6 and 90.
iii) 4 and 24

4i) Kruskal's's
ii) Algorithm cannot return to A.
Start from B to get a cycle of weight of
Alteration to obtain a length of 69 km.

5i) Dijkstra's
ii) Chinese Postman on reduced network.

6i) Correct drawing.
ii) x = 4, y= 4.5 , P= 56
iii) Try all integer values of x with their respective y-values. Obtain P = 54.
iv) To get constraint in the form ax+by <= c, as algorithm can not be used for greater than constraints.
v) Initial Simplex tableau
ii) Can't remember the first values, but you will then verify for non-integer values that P = 56, when x = 4 and y =4.5

For 6(iii). wasn't (0,7) in the feasible region so therefore that gives 56 (P=5x+8y)

Yeah I got 88 too after the second iteration I think. Yep got 69km for that! yeah all 3 pairs for me were 32k each as well ;]

Work so far, will be continued if paper re-uploaded:

Unofficial Mark Scheme

1i) $24 \ 57 \ 9 \ 31 \ 16 \ 4$

$24 \ 9 \ 57 \ 31 \ 16 \ 4$

$24 \ 9 \ 31 \ 57 \ 15 \ 4$

$24 \ 9 \ 31 \ 15 \ 57 \ 4$

$24 \ 9 \ 31 \ 15 \ 4 \ 57$

Circles where necessary to indicate comparisons. (2 marks)

ii) $Pass \ 2 \ : \ 9 \ 24 \ 15 \ 4 \ 31 \ 57$

$Pass \ 3 \ : \ 9 \ 15 \ 4 \ 24 \ 31 \ 57$

(2 marks)

iii) Pass 1 - 4 swaps, Pass 2 - 3 swaps, Pass 3 - 2 swaps , Pass 4 - 1 swap, Pass 5 -1 swap (2 marks)

2i)a) Square plus a loop at one vertex for example (1 mark)

b) Max vertex order for simple graph with 4 vertices is 3, but is Eulerian so order has to be 2 (as 0 means one vertex is not connected). Hence total order = 4x2 = 8. 8/2 = 4, so 4 arcs, not 5 arcs. (2 marks)

ii)a) Total order = 2 x no. of arcs = 2 x 10 = 20 (1 mark)

b) Max - 6, min - 2, and correct graph drawn (3 marks)

c) Two vertices of order 4, six of order 2. (1 mark)

3i) Correct trace through the algorithm, yielding outputs 6 and 90. (6 marks)

ii) After you fill in the space in the answer booklet, you will get F D and E the same as in part i). From this it follows that G = 18 /6 = 3 and M = 3 x 30 = 90. The same as in part i). (2 marks)

iii) F = 4 and M = 24. (2 marks)

4i) $A - B -C-D-E-F-G$
Weight = 51 km
82km - 51km = 31km

so: $A-B-C-D-E-F-G-F-B-A$

with weight 82km. (4 marks)

ii) 51 - 5 - 7 + 8 = 47km.
Go back through D so:

$A-B-C-E-F-G-D-A$ (2 marks)

iii) NN starts $A - B-C-D-E-F-G$

Stalls as can't return to A.

$B - A - C - D - E -F-G-B$

Weight = 76km.

$B - A - C - D - E - G - F - B$

Weight = 69km. (6 marks)

5i) $A - B - F - G$

Weight = 31km. (5 marks)

ii) 25 hours (2 marks).

iii) $11 + 15 + CE \leq 31$

$CE \leq 5$

8 - 5 = 3km (2 marks)

iv) Odd nodes A,B,C and F.
All repeated arc lengths are 32km.
32 + 224 - 11 - 8 = 237km. (6 marks)

6i) Attached using Wolfram (4 marks)

ii) $(6,3) , \ (4,0), \ (3,0) \ and \ (4,4.5)$

At (6,3) P = 54
At (4,0) P = 20
At (0,3) P = 24
At (4,4.5) P = 56.

So at optimal point x = 4, y = 4.5, P = 56. (4 marks)

iii) When x = 0, max y = 3, P = 24.
When x = 1, max y = 3, P = 29
When x = 2, max y = 3, P =34
When x = 3, max y = 4, P = 47
When x = 4, max y = 4, P = 52
When x = 5, max y = 3, P = 49
When x = 6, max y = 3, P = 54.

So optimal point is when x = 6, y = 3 and P = 54. (4 marks)

iv) Simplex is designed for inequalities with a less than or equals sign. (1 mark)

v) Correct Simplex Tableau (2 marks)

vi) First pivot 8 in y-column.
Show how rows calculated.
P = 24, x = 0, y = 3.
Pivot is 4.5 in x-column.
Verify that optimum point is when x =4, y = 4.5 and P = 56.