Decision Mathematics 1

What decision mathematics 1 covers

One of the eight optional papers of 9FM0, sat as Paper 3D, so take it only if your centre teaches it. It is also the gateway to Decision Mathematics 2, which may be taken only as a matching pair with it. Little of A level Mathematics is assumed: the work is algorithms run by hand on networks and tables, and the marks go to the working rather than to the final number.

The main ideas

• Following an algorithm from text or a flow chart, the order of an algorithm, and the bubble and quick sorts shown pass by pass.
• Bin packing by first fit, first fit decreasing and full bins, compared against a lower bound.
• Graph vocabulary: node orders, Eulerian and semi-Eulerian graphs, complete, planar and isomorphic graphs, and the planarity algorithm.
• Minimum spanning trees by Prim, from a network and from a distance matrix, and by Kruskal from a sorted edge list.
• Shortest paths by Dijkstra, with the route backtracked from the destination, and Floyd on a distance matrix and a route matrix together.
• Route inspection by pairing the odd nodes, and the travelling salesman problem bracketed between an upper and a lower bound.
• Critical path analysis, float, Gantt charts and scheduling, then linear programming graphically and by Simplex.

The results it turns on

lower bound on bins = total size ÷ bin size, rounded up

the check every bin packing answer is compared against

the sum of the node orders = 2 × the number of edges

which forces the number of odd nodes to be even

a spanning tree on n nodes has n − 1 edges

the count that checks a Prim or Kruskal answer

route inspection total = network weight + the cheapest pairing of odd nodes

the shortest closed route covering every edge

total float = latest finish − earliest start − duration

the slack available on one activity

lower bound on workers = total work ÷ project duration, rounded up

the target a levelled schedule aims at

Where it usually goes wrong

• Dijkstra makes permanent the smallest temporary label anywhere in the network, which is not the same as the cheapest edge leaving the vertex you are standing on.
• Backtracking is done by testing each edge at the vertex you are on. Matching label differences alone also flags edges on shortest routes to other vertices, so it does not by itself produce a route.
• The three bin packing algorithms are quick, and none of them reliably finds the fewest bins, which is why the lower bound is quoted alongside the answer.
• In Simplex the pivot row comes from the smallest non-negative ratio, with negative and zero entries skipped, and the algorithm stops once the objective row has no negative entries.

Where to start

Algorithms and sorting first, then graph vocabulary, which every network algorithm after it assumes. Spanning trees before route inspection and the travelling salesman problem, since both call on them. Critical path analysis and scheduling make one block. Linear programming and Simplex close the paper and can be revised on their own.