Flashcards · YMA01 · Topic 9

Unit D1: Decision Mathematics 1 flashcards

30 cards on Topic 9, subtopics D1.1 to D1.5. Pick a subtopic or study them all.

Study mode needs JavaScript. Every card is listed below, so you can still cover the answers and test yourself.

All 30 cards

For a quick read-through or printing. Cover the right-hand side to test yourself.

Middle item of a list of N items (D1 convention): Position (N + 1)/2 if N is odd; (N + 2)/2 if N is even. Example: N = 12 gives the 7th item.
Bubble sort: Compare neighbours from the left and swap any pair in the wrong order. Each pass sends the largest remaining item to the end. Stop after a pass with no swaps.
Quick sort: Choose the middle item as the pivot. Put smaller items to its left and larger to its right, keeping their order. The pivot is fixed; repeat on each sublist until every sublist has one item or none.
Binary search: The list must be ordered. Test the middle item: if the target is larger keep the items after it, if smaller keep those before it; discard the middle item. If the list empties, the target is absent.
First-fit and first-fit decreasing bin packing: First-fit: take items in the order given; each goes in the first bin with room. First-fit decreasing: sort into decreasing order first, then use first-fit.
Lower bound for the number of bins: Total size of all items ÷ bin capacity, rounded up. If a packing uses that many bins, it is optimal.

Spanning tree and minimum spanning tree: A spanning tree connects all n vertices with n − 1 edges and no cycles. A minimum spanning tree (minimum connector) is the one of least total weight.
Kruskal's algorithm: Sort all edges by weight. Repeatedly take the cheapest edge that does not form a cycle. Stop when n − 1 edges are chosen. The tree may grow in separate pieces that join up.
Prim's algorithm: Start from one vertex. Repeatedly add the cheapest edge joining a vertex in the tree to a vertex not yet in it. Stop when all vertices are in. It grows as one tree.
Prim's algorithm in matrix form: 1. Number the start column 1 and cross out its row. 2. In the numbered columns, circle the smallest entry in an uncrossed row. 3. Number that row's vertex column next and cross out its row. 4. Repeat until all rows are crossed out.
Dijkstra's algorithm: Give the start label 0 and order 1. From the latest final vertex, update working values (final label + edge) if smaller. Make the smallest working value final with the next order number. Stop when the target is final.
How do you find the route after Dijkstra's algorithm?: Work back from the target: an edge is on the route if (final label at its end) − (edge weight) = (final label at its start).

Route inspection (Chinese postman) algorithm: 1. List the odd nodes. 2. List all pairings of them. 3. Find the shortest path for each pair; add for each pairing. 4. Route length = total edge weight + smallest pairing total.
Rectangle ABCD: AB = 6, BC = 4, CD = 6, DA = 4, diagonal AC = 8. Find the route inspection length.: Odd nodes A and C (degree 3). Shortest A to C is 8. Total weight 28, so the route length is 28 + 8 = 36, repeating AC.
Classical compared with practical travelling salesman problem: Classical: visit every vertex exactly once and return, minimum length. Practical: visit every vertex and return, revisits allowed.
Nearest neighbour algorithm for the TSP: Start at the given vertex, move to the nearest unvisited vertex each time, then return to the start. The tour length is an upper bound. Use it on a complete network.
Lower bound for the TSP by deleting a vertex: Remove one vertex and its edges, find the minimum spanning tree of what is left, then add the two shortest edges at the removed vertex. Keep the largest such value as the best lower bound.
Upper bound by doubling a minimum spanning tree: Double the MST to get a walk visiting every vertex, then replace revisits by direct short cuts. The result is a tour, so it is an upper bound. Keep the smallest upper bound.

Activity, event and dummy in an activity network: Activity: a job with a duration, drawn as an arc. Event: a node where activities finish and others start. Dummy: a dashed arc of duration 0, used to show dependence or keep arcs unique.
Forward and backward passes: Forward pass: earliest event time = largest (eᵢ + duration) over the arriving arcs. Backward pass: latest event time = smallest (lⱼ − duration) over the leaving arcs.
Critical activity and critical path: A critical activity has total float 0. A critical path is a path of critical activities from start to end; its length is the minimum project time.
Total float of activity (i, j): Total float = lⱼ − eᵢ − duration, where i is the start event and j the end event.
Lower bound for the number of workers: Total of all durations ÷ minimum project time, rounded up. It is only a minimum: a valid schedule must still be shown.
What goes in a precedence table?: Each activity with its immediate predecessors only, not every earlier activity.

Formulating a linear programming problem: 1. Define the decision variables, with units. 2. Write the objective function to maximise or minimise. 3. Write one linear inequality per constraint. 4. State x ≥ 0, y ≥ 0, and integers if required.
Vertex method for a linear programme: The feasible region is the set of points satisfying every constraint. List its vertices (where boundary lines meet), work out the objective at each, and choose the largest to maximise or the smallest to minimise.
Objective line (ruler) method: Draw ax + by = k for a convenient k and slide a ruler parallel to it. To maximise, the last point of the region touched is optimal; to minimise, the first point touched.
Write "at least twice as many shelves (y) as tables (x)" as an inequality: y ≥ 2x. The larger quantity goes on the greater side.
How do you find an integer solution?: Solve without the integer condition to get a bound, then test integer points near the optimal vertex against every constraint and choose the best feasible one. Rounding the vertex is not a method.
Maximise P = 3x + 4y with vertices (1, 0), (1, 7.5), (4, 6), (6, 0): P values: 3, 33, 36, 18. Maximum P = 36 at (4, 6).