# Homework to 22 Jun

Year 12 Further Maths homework for 22/6/18

Finish these past-paper questions on the Travelling Salesman Problem

The booklet has mark schemes and examiners’ reports. Please use them to mark your work. Just bring the work to next Friday’s lesson, 22 June: you don’t have to hand it in earlier, on Wednesday.

For your End-of-Year Decision Maths exam on Wed 27 June, please also make sure you’re good on more general issues about the algorithms.

Year 12 Further Maths homework for 12 June 2018

Ex 5A Q.1(d)

Ex.5B Q.1-3

Ex.5C Q.1-2

The travelling salesman problem (TSP) is: find the shortest tour, returning to your start, which visits each vertex at least once.

CLASSICAL AND PRACTICAL

Anyway, that’s what the book calls the “practical travelling salesman problem”. The book calls the problem of finding a shortest tour visiting each vertex exactly once the “classical travelling salesman problem”.

All you need to know for now about the “classical travelling salesman problem” is how to answer the question: what is the difference between the “classical travelling salesman problem” and the “practical travelling salesman problem”. All our algorithms deal with the practical TSP.

CLTD

Because we’re dealing with the practical TSP, we’re interested only in the shortest route between any two vertices, and we aren’t bothered if that route means going through a vertex we may already have visited.

Instead of working with the original graph, we work with a complete table of least distances, which shows the shortest distances between vertices (even if they’re indirect, and even if that means ignoring direct routes which are longer.

Upper bounds and lower bounds

As with Bin-Packing, no algorithm (except which is impossibly long-winded for even a moderate number of vertices, e.g. checking 1.2×1018 possibilities, several years’ computing time on a fast modern computer, for just 20 vertices) guarantees you an exact answer for the TSP.

The algorithms give you upper bounds and lower bounds. The best upper bound is the smallest one. The best lower bound is the biggest one.

Nearest neighbour

Nearest neighbour says: 1. Pick a vertex to start. (For A level, the question will tell you which one to pick). 2. Work from there, step by step, at each step adding the “nearest neighbour” vertex to your last vertex. 3. Finally, connect back to start.

It’s like Prim, except that at each stage you choose the “nearest neighbour” route from your last vertex, rather than from any vertex you’ve reached so far.

Problem with nearest neighbour is that it may give you a really long distance to connect back from the last vertex to the start. Still, it gives you an upper bound.

MST×2

MST×2 gives you, not a better upper bound necessarily, but a quicker-to-calculate upper bound.

Find a minimum spanning tree (MST), using Kruskal or Prim. Then going out along that MST, and getting back to the start by retracing your steps from each “branch”, is a tour and reaches all vertices.

So MST×2 gives an upper bound.

MST×2 with shortcuts

MST×2 gives an upper bound, but maybe a rubbish one. Often you can improve on it just by a bit of human intelligence. For example, choose a start point on your MST and look at the most distant branches. There may be “shortcuts”, routes back to the start from the ends of those most distant branches, which are quicker than retracing your step through the whole MST.

MST and RMST

Just MST gives you a lower bound, because the MST tells you the shortest total distance to visit all vertices. Pretty much always the MST won’t be a tour, but any tour visiting all vertices must be at least as long.

That is a lower bound. But it is so rubbish that the textbook doesn’t even mention it.

Instead it mentions RMST, Residual Minimum Spanning Tree, which is the MST method improved by a bit of human intelligence.

Choose any vertex. (For A level, the question will tell you which one to pick). Find an MST for all the remaining vertices. Then find the shortest way to connect that first chosen vertex in with the MST for those remaining vertices.

That is a lower bound.

If the route you get by doing RMST is a Hamiltonian cycle (meaning: it’s a tour which goes through each vertex exactly once), then that route is not just a lower bound. It’s an exact answer. But usually the route you get by doing RMST is not a Hamiltonian cycle. It gives you not an exact answer but a lower bound.

Year 12 Further Maths homework for 5/6/18

If you missed the lesson on 25 May, then please first, just by trial and improvement without any theory from the book, find the shortest tours (ways to visit all nodes and get back wherever you started) for these two graphs.

I think the shortest for the smaller graph is 66. David was the first to find it in class, and that’s the best the book can do, too.

Howard and Lara both got 960 for the bigger graph. The best the book can do is 990.

Howard and Lara can do better than the book not just because they’re clever, but because they looked ahead when doing their trial-and-improvement to find the shortest route.

Computer algorithms don’t look ahead beyond the very next step. Reason why: with a large number of nodes (and you wouldn’t bother with an algorithm if it was only a small number of nodes), the number of possibilities when looking ahead becomes just too big to manage.

The first computer algorithm for the travelling salesman problem I want you to learn is the nearest-neighbour algorithm. It is similar to Prim’s algorithm, except that at each stage you choose the shortest edge which reaches a new node and starts from the node you last reached, rather than from any of the nodes you’ve reached so far.

Read the textbook section 5.4 and work through the examples there.

Then – travelling salesman problem: finish Ex. 5D Q.1-5, and Mixed Exercise (p.123) Q.2

Year 12 Further Maths homework for 16/5/18

Made-up Decision maths practice paper 7 (50 minutes, 50 marks): Question paper; Mark scheme; Answer book

Optional extra (if you want more Decision Maths practice before the exam on 17 May)

Decision maths practice paper from p.271-2 of textbook (50 minutes, 40 marks): Question paper (with diagrams for Dijkstra and CPA); Answer sheet

Year 13 homework from now until the exams is past papers, as indicated at https://mathsmartinthomas.wordpress.com/2018/04/19/y13-further-maths-schedule-for-past-papers-between-now-and-exams/, plus individual items for some individual students each week.

Year 12 Further Maths homework for 9/5/18

Made-up Decision maths practice paper 6 (50 minutes, 50 marks): Question paper; Mark scheme; Answer book

plus worded problems 1, 3, 7 on volumes of revolution (at the end of your volumes of revolution workbook, or on p.87 of the textbook).

Year 12 Further Maths homework for 2/5/18

Made-up Decision maths practice paper 5 (50 minutes, 50 marks): Question paper; Mark scheme; Answer book

plus questions 17 and 19 on Argand diagrams from page 41 of the Core Pure textbook.

Use these worked answers to questions 14, 16, 18, and 20 from page 41.

Year 12 Further Maths homework for 25/4/18

Questions 14, 16, 18, 20 on page 41 of the Core Pure textbook. The key with all these questions is to do (good, clear, big) diagrams, and to do all your calculations from the diagrams, using geometry and trig. If you’re going well, try the “challenge” question too: if you can do that, you can do anything Edexcel will throw at you.

Year 13 Further Maths homework for 18/4/18

Do these past papers

S2 January 2012 (from your booklet https://mathsmartinthomas.files.wordpress.com/2015/03/s2-pp-2010-2017.pdf)

FP2 June 2013 (this is the “ordinary” FP2 June 2013, not the
“withdrawn” one you did for the mock, and not the 2013R one) (from your booklet https://mathsmartinthomas.files.wordpress.com/2016/02/fp2_frost.pdf)

FP3 June 2009
FP3 June 2010

(the first two papers in the booklet https://mathsmartinthomas.files.wordpress.com/2016/02/fp3_frost.pdf).

I would suggest at this stage that you do them open-book (i.e. feel
free to look up the textbook, or the web, or the mark scheme, when you get stuck) *but* in the 90 minute time-frame.

Please mark your own work, and try to puzzle out what went wrong where you made mistakes or blanked.

And, of course, email me for help at any stage.

Scan and send those papers to me (preferably), or hand them in to me at the start of next term?

Year 12 Further Maths homework for 18/4/18

These are the practice papers to do over the holiday:

You will also complete and check the Decision Maths practice paper we started in class on 23/3/18, though you do not have to hand in that work.

Question paper here: https://mathsmartinthomas.files.wordpress.com/2017/12/180321d1-practice.pdf

Year 12 Further Maths homework for 21/3/18

Complete the new linear programming workbook we started today

https://mathsmartinthomas.files.wordpress.com/2014/08/180311linearprogramming.pdf

(not the old linear programming workbook: you’ll still have some questions not yet done from that, which we will use for practice later).

Year 13 Further Maths homework for 21/3/18

Further maths homework is to go through the FP3 paper you did for the
mocks, correcting mistakes you made, filling in bits you blanked on.

The paper is here:

If you’re puzzled even after reading the mark scheme and worked

Year 13 Further Maths homework for 14/3/18

Between now and Wed 14 March you should all do at least one FP2 past paper, at least one S2 past paper, and at least one FP3 past paper.

I suggest do FP2 first, then S2, then FP3, because that’s the order of the mock exams.

For FP2: June 2012

For S2: summer 2011

For FP3 I suggest the official Edexcel FP3 Mock Paper. You should be able to attempt all questions except question 8 (which is about chapter 2, which you won’t cover until after the mocks).

Do each paper in as near to exam conditions as you can manage

then mark it against the mark scheme

scan your work and email me the scan for feedback

try to fix the bits where you made slips or blanked

if you still can’t see how to fix it after reading the mark scheme and puzzling over it, email me

Each of you will probably do well also to work on collections of past-paper questions on topics which you, individually, find more difficult. For example, here is a collection of past-paper questions on Mobius transformations:

https://mathsmartinthomas.files.wordpress.com/2016/02/fp2-loci-q1.pdf

For every topic in FP2, S2, or FP3, there is a collection of past-paper questions on that topic at

https://mathsmartinthomas.wordpress.com/2017/12/12/s2-statistics-materials/

https://mathsmartinthomas.wordpress.com/2016/02/19/fp2-past-papers/

or

https://mathsmartinthomas.wordpress.com/2016/02/19/fp2-past-papers/

For FP3, ignore for now the past-paper questions on conics, and on vectors try only the shorter question sheet I circulated in class.

Email me scans of this work, too?

I will send feedback on scanned work as fast as I can.

Year 12 Further Maths homework for 14/3/18

Homework for Wed 14th:

at least four more problems from the linear programming workbook

so everyone who was in school on Friday 2nd should get up to Q.8 at least (and that includes finding whole-number solutions when they’re asked for)

and everyone who missed school on Friday 2nd should get up to Q.4 at least (and that includes finding whole-number solutions when they’re asked for).

if you like, instead of drawing the parallel objective lines. Whichever you prefer.

I’ll do a marking marathon on your linear programming workbooks between Wednesday and Friday.

Make sure also you’ve done the Part A homework for Wednesday 7th (below).

Year 12 Further Maths homework for Wednesday 7/3/18

Abass: Redo Q.7(d) and Q.9(b) from the test (we discussed them). Try creating a new equation with roots 2α+1, 2β+1, 2γ+1 from the equation x3 – x = 0. Insert K into Gantt chart in Q.2(c) of Critical Path Analysis workbook. Do Q.8 of Critical Path Analysis workbook.

Aniqa: bring me your Critical Path Analysis and Dijkstra booklets next Wednesday, with Dijkstra questions done up to Q.5 inclusive, and CPA up to Q.8 plus also Q.14, 17, 18. Skip Q.5(e), 6(f), 7(d) in Critical Path Analysis workbook.

Callum: none

David: Try Q.3 from test paper (create new equation from x3+3x2+5x-1=0 with roots 2α+1, 2β+1, 2γ+1) by method of writing y=2x+1, deducing x=(y-1)/2, plugging (y-1)/2 in place of x in the original equation, and expanding, collecting terms, and simplifying to get an equation in y. Do more examples from your Critical Path Analysis workbook and give it to me next Wednesday.

Enoch: Dijkstra – try Q.6. Critical Path Analysis – expand your answer to Q.3(a) [why dummies?]. Do Q.4(e) [which activities on days 16 and 31]. Do Q. 6(c), 6(d), 7, 8. Try Q.3 from test paper (create new equation from x3+3x2+5x-1=0 with roots 2α+1, 2β+1, 2γ+1) by method of writing y=2x+1, deducing x=(y-1)/2, plugging (y-1)/2 in place of x in the original equation, and expanding, collecting terms, and simplifying to get an equation in y.

Helen: Look at my comment on Q.18(b) of Critical Path Analysis to check if you understand. Look at my comment on Q.2(b) in Dijkstra booklet to check if you understand.

Howard: to follow

Iris: Critical Path Analysis – complete Q.4(c) [floats]. Try again on Q.4(d) [which activities on day 31]. Complete 5(c) [floats], and 6(c) [can project still be completed on time]. Complete Q.14.

Jeffrey: Redo Q.8 of the test paper. Try Q.4(e) of the Critical Path Analysis workbook again, looking carefully at the floats on all the activities.

Lara: Do the Gantt chart bits of all the questions you’ve done in the Critical Path Analysis booklet.

Mya: to follow

Obi: Dijkstra workbook – redo your answer to Q.1(b) after looking at the answer given to the (similar) Q.7c in the back of the workbook. Critical Path Analysis workbook: do Q.1(e), 3(d). Redo Q.3(e) Gantt chart showing the floats on A and on F. Complete the Gantt chart in Q.4(d). Complete Q.5 (b), (c), (d), and Q.8.

Reece: Critical Path Analysis – try again on Q.16(a). Try again on Q.4(e) and Q.6(e), looking carefully at the floats. Do Q.14.

Part B, for those who were in class on 2/3/18

From linear programming workbook

https://mathsmartinthomas.files.wordpress.com/2018/03/linearp_q1.pdf

Complete Q.1 to 3. Where the answer has to be whole numbers, and your calculation gives you not-whole numbers, leave it with the not-whole number answers. That’s ok: we’ll find out next week how to get the best whole-number answers.

If you’re stuck, use the answers in the back of the workbook.

Part C: none for those who were in class on 2/3/18, but those who weren’t in class on 2/3/18 should do up to Q.9 inclusive in the Dijkstra workbook https://mathsmartinthomas.files.wordpress.com/2014/12/dijkstra.pdf

Year 13 Further Maths homework between now and after mocks (14/3/18)

Between now and Wed 14 March you should all do at least one FP2 past paper, at least one S2 past paper, and at least one FP3 past paper.

I suggest do FP2 first, then S2, then FP3, because that’s the order of the mock exams.

For FP2: June 2012

For S2: summer 2011

For FP3 I suggest the official Edexcel FP3 Mock Paper. You should be able to attempt all questions except question 8 (which is about chapter 2, which you won’t cover until after the mocks).

Do each paper in as near to exam conditions as you can manage

then mark it against the mark scheme

scan your work and email me the scan for feedback

try to fix the bits where you made slips or blanked

if you still can’t see how to fix it after reading the mark scheme and puzzling over it, email me

Each of you will probably do well also to work on collections of past-paper questions on topics which you, individually, find more difficult. For example, here is a collection of past-paper questions on Mobius transformations:

https://mathsmartinthomas.files.wordpress.com/2016/02/fp2-loci-q1.pdf

For every topic in FP2, S2, or FP3, there is a collection of past-paper questions on that topic at

https://mathsmartinthomas.wordpress.com/2017/12/12/s2-statistics-materials/

https://mathsmartinthomas.wordpress.com/2016/02/19/fp2-past-papers/

or

https://mathsmartinthomas.wordpress.com/2016/02/19/fp2-past-papers/

For FP3, ignore for now the past-paper questions on conics, and on vectors try only the shorter question sheet I circulated in class.

Email me scans of this work, too?

I will send feedback on scanned work as fast as I can.

Year 12 Further Maths homework for 28/2/18

Please hand in, next Wednesday 28th:

• Your critical path analysis workbook, with questions 1-8, 13, 14, 17, 18 done. I’ve selected 13, 14, 17, 18 because they include drawing graphs from precedence tables, which is the trickiest part. Skip the
bits about “scheduling” – Q.5e, 6f, 7d, 9d,f,g, and 10e,f. (Those bits were in the old syllabus, but now are in Year 13).
• Your Dijkstra workbook. (I’m not asking you to do any more from that this week. I just want to double-check where you’re all up to on that).
• Your test paper from 9 February, with your corrections and fixing, unless I’ve seen it this week and written feedback which indicates you’ve fixed it near enough completely.

Year 13 Further Maths homework for 21/2/18

First calculate a mark for yourself on the paper you did last Thursday, and let me know.

Second, do a past paper in 90 minutes. Open book or closed book, that’s up to you, but in a single session of 90 minutes without distractions.

Do either FP2 June 2011 or S2 January 2011, as you prefer.

Send me a scan of your work. I will send feedback.

See if you can fix all the bits where you made slips, or blanked. If you can’t work it out even with help from the mark scheme, email me for help.

Do the following exercises to get used to dot-product and cross-product.

Ex.5A Q.1, 2, 3
Ex.5D Q.1, 3, 5
Ex.5E Q.1 to 4
Review Exercise 2 Q.5
and Example 18 from p.158 of the textbook

Since you have half-term, I’d suggest you also try the same process with an FP3 paper – attempt the paper in 90 minutes (open book or closed book, as you prefer), send me a scan, mark it yourself, try to fix where you’ve made slips or blanked, email me where you can’t fix it.

I suggest the official Edexcel FP3 Mock Paper

You should be able to attempt all questions except question 8 (which is about chapter 2, which you won’t cover until after the mocks).

Year 12 Further Maths homework for 21/2/18

First: I will send you a scan of your test paper from 09/02/18. Please work through to see if you can fix all the slips you made and any points where you blanked.

Then: two more questions from the Critical Path Analysis workbook.

Critical Path workbook: https://mathsmartinthomas.files.wordpress.com/2014/12/cpa_q.pdf

Read the notes about dummies, and be careful to get them right.

https://mathsmartinthomas.wordpress.com/2018/02/04/dummy-edges-in-critical-path-analysis-graphs/

And two more questions from the Dijkstra workbook, taking care not to miss any connections (even apparently “backwards” ones); to label all the little boxes; to put the order of labelling (not the order on the shortest path) in the middle little box; and to explain well how you find which vertices are on the shortest path.

This is how the mark schemes say you must explain finding those vertices:

“General explanation – trace back from J [end node]. Include arc XY if Y is already on path and if difference in trial labels equals length of arc”.

Dijkstra workbook: https://mathsmartinthomas.files.wordpress.com/2014/12/dijkstra.pdf

Year 12 Further Maths homework for 7/2/18

Review the Core Pure paper you did over Xmas:

https://mathsmartinthomas.files.wordpress.com/2017/12/y12-pure.pdf

There’s a typo in Q.5. It should be +78z2, not −78z2

I’m not asking you to re-do the whole paper, but to check which questions you can see how to do easily, and which puzzle you or which you’ve forgotten how to do, and to work through what you’re not confident with.

Also: one more question from the Critical Path Analysis workbook.

Critical Path workbook: https://mathsmartinthomas.files.wordpress.com/2014/12/cpa_q.pdf

And one more question from the Dijkstra workbook, taking care not to miss any connections (even apparently “backwards” ones); to label all the little boxes; to put the order of labelling (not the order on the shortest path) in the middle little box; and to explain well how you find which vertices are on the shortest path.

This is how the mark schemes say you must explain finding those vertices:

“General explanation – trace back from J [end node]. Include arc XY if Y is already on path and if difference in trial labels equals length of arc”.

Dijkstra workbook: https://mathsmartinthomas.files.wordpress.com/2014/12/dijkstra.pdf

Year 13 Further Maths homework for 7/2/18

First mark your own work on the paper you did after class on Thursday. See if you can fix all your mistakes or the bits you blanked on. Email me if you get stuck.

On Saturday I will send you feedback on your paper, to help.

That’s – Umut and Bolaji, S2 January 2010; Mohaned and Tegan, F2 IAL June 2016; Onesimus and Michelle, FP2 June 2016

Then do exercise 6G up to at least Q.6 (Q.8 for Mohaned).

Year 13 Further Maths homework for 31/1/18

Transforming points, lines, and planes by 3×3 matrices: do at
least two more of these questions from the FP3 book in addition to
those you did in class.

Ex.6E Q.1
Ex.6D Q.2
Ex.6D Q.3
Ex.6D Q.5
Ex.6D Q.8

If you didn’t complete the FP2 June 2009 past paper after class today,
please complete it and send a scan (preferably) or photos from your
phone (failing that) to me by end of school on Friday 26/1/18. I’ll
email you feedback quickly.

Year 13 Further Maths homework for 31/1/18

Transforming points, lines, and planes by 3×3 matrices: do at
least two more of these questions from the FP3 book in addition to
those you did in class.

Ex.6E Q.1
Ex.6D Q.2
Ex.6D Q.3
Ex.6D Q.5
Ex.6D Q.8

If you didn’t complete the FP2 June 2009 past paper after class today,
please complete it and send a scan (preferably) or photos from your
phone (failing that) to me by end of school on Friday 26/1/18. I’ll
email you feedback quickly.

Year 12 Further Maths homework for 31/1/18

Finish the Chinese postman (route inspection) exercises

https://mathsmartinthomas.files.wordpress.com/2014/08/chinesepostman-newbook1.pdf

Do the first two questions (only) of the big Dijkstra booklet, taking to fill in all the little boxes (Edexcel insists) and not to miss shorter connections which look like they involve going “backwards”.

https://mathsmartinthomas.files.wordpress.com/2014/12/dijkstra.pdf

Year 12 Further Maths homework for 24/1/18

Finish the Dijkstra exercises for which you have printed templates.

Dijkstra exercises with printed templates

You got copies of the first two in the lesson, and copies of the third exercise will be available at reception at the 6th Form Building.

Don’t do the Dijkstra exercises for which you don’t have printed templates:

New-syllabus Dijkstra examples

but read through them to notice the extra things you may be asked in the new syllabus, e.g. things about the order of the algorithm and calculation time.

Year 13 Further Maths homework for 24/1/18

Basic homework for everyone but Genie and Tegan: rework the questions from the S2 January 2013 paper which you got wrong or blanked on.

Mohaned and Bolaji, in particular, have very little work of that sort to do, because they got very little wrong. They would do well to do another FP2 paper – I recommend F2 IAL June 2016.

Genie and Tegan: do as much as you can of the FP2 paper you were working on in class.

We’re starting FP3 matrices next Wednesday, so everyone should take a moment to refresh their memory of FP1 matrices a bit.

Year 13 Further Maths homework for 17/1/18

All but Genie and Tegan: finish S2 June 2017 paper https://mathsmartinthomas.files.wordpress.com/2015/03/s2-pp-2010-2017.pdf and mark your own work.
Complete Ex.3E Q.1, 2, 3, 4, 10.

Genie: exercises (of Genie’s choosing) on polar coordinates and first order differential equations (up to and including integrating factor).

Tegan: do at least one of the two FP2 practice papers compiled from Review Exercise questions in the book. (I’m proposing these because answers can be found in the back of the textbook, and further help on Solution Bank). Bring to next Wednesday’s lesson a list of FP2 “issues”.

https://mathsmartinthomas.wordpress.com/2016/11/16/fp2-practice-papers-for-november-and-december-2016-tests/

Year 12 Further Maths homework for 17/1/18

Rework the questions you got wrong or failed to complete in the two holiday worksheets:

and

Hints and part-solutions to the core pure paper

Question 4 of the Decision Maths homework says: “Bubble sort is an algorithm of quadratic order”. It means it is of order n^2.

(Like a quadratic equation is one which has x^2 in it but not higher powers).

Year 12 Further Maths homework for 10/1/18

As above.

Year 13 Further Maths homework for 10/1/18

Sampling and hypothesis testing: Exercise 7D Q.1-10 and Exercise 6C Q.6, 7, 8.

Exercise 7D Q.1-10 and Exercise 6C Q.6, 7, 8

And the “Examination practice paper” at the end of the S2 book, p.131-132, questions 1 to 6.

S2 practice paper

You may find these two summary sheets useful:

Revision sheet

“Do and don’t” for S2 statistics

and these notes:
How many marks does Edexcel take off for bad writing in S2?

Then please do these more demanding tasks: two FP2 practice papers compiled from Review Exercise questions in the book. (I’m proposing these because answers can be found in the back of the textbook, and further help on Solution Bank).

https://mathsmartinthomas.wordpress.com/2016/11/16/fp2-practice-papers-for-november-and-december-2016-tests/

And the June 2016 FP2 paper (which was a harder-than-usual paper). You can find the paper, plus worked answers and a mark scheme, at: https://mathsmartinthomas.wordpress.com/2016/12/07/june-2016-fp2-notes/

Archive of older homework at:

https://mathsmartinthomas.wordpress.com/2017/12/21/homework-archive-2014-2017/

This site uses Akismet to reduce spam. Learn how your comment data is processed.