4D.4.1 Principles of dynamic programming Quiz: Pearson Edexcel Further Maths, Unit 43

The 20 questions

1. What does Bellman's principle of optimality state?

   • Every path from source to sink is optimal.
   • Any part of an optimal path is itself optimal.
   • The optimal path always uses the cheapest arc from the source.
   • Only the final stage of an optimal path must be optimal.

2. In a dynamic programming network, what is a stage?

   • The total length of a complete route.
   • A vertex with no outgoing arcs.
   • A set of vertices that all lie the same number of decisions from the start.
   • A single arc with the largest weight.

3. In dynamic programming, what is a state?

   • A possible position or condition at a stage, such as a vertex that can be reached.
   • The overall optimal value of the whole problem.
   • The number of stages in the network.
   • The arc chosen to leave the source.

4. What is the minimax route in a network?

   • The route in which the total length is as small as possible.
   • The route that uses the fewest arcs.
   • The route in which the maximum length of the arcs used is as small as possible.
   • The route in which the minimum length of the arcs used is as large as possible.

5. What is the maximin route in a network?

   • The route that uses the most arcs.
   • The route in which the maximum length of the arcs used is as small as possible.
   • The route in which the minimum length of the arcs used is as large as possible.
   • The route in which the total length is as large as possible.

6. What is a table formulation used for in dynamic programming?

   • Showing the network with all its arcs removed.
   • Listing every possible route in full before comparing them.
   • Recording the best value and decision at each stage, working through the stages in order.
   • Storing the cost of the arcs only.

7. Which property lets dynamic programming ignore the rest of a route once the best route to a state is known?

   • The handshake lemma, which fixes vertex degrees.
   • The triangle inequality, which fixes route lengths.
   • The principle of optimality, since only the best route to each state is needed.
   • The max-flow min-cut theorem, which bounds route lengths.

8. In the network with arcs A-B (2), A-C (4), B-C (1), B-D (5), C-D (2), C-E (6), D-F (3) and E-F (1), all directed from A towards F, what is the length of the shortest route from A to F?

   • 10
   • 8
   • 9
   • 11

9. Which route from A to F is the shortest in that network?

   • A, C, E, F
   • A, C, D, F
   • A, B, C, D, F
   • A, B, D, F

10. In the same network, what is the length of the longest route from A to F?

    • 10
    • 9
    • 12
    • 11

11. Which route from A to F is the longest in that network?

    • A, B, D, F
    • A, C, E, F
    • A, C, D, F
    • A, B, C, E, F

12. In that network, what is the value of the minimax route from A to F, measured as the largest arc on the route?

    • 5
    • 6
    • 3
    • 2

13. Which route is the minimax route from A to F in that network?

    • A, B, C, D, F
    • A, B, D, F
    • A, C, D, F
    • A, C, E, F

14. In that network, what is the shortest route length from B to F?

    • 8
    • 9
    • 6
    • 7

15. In that network, what is the shortest route length from A to E?

    • 9
    • 12
    • 7
    • 10

16. Does the minimax route from A to F also have the smallest total length?

    • Yes, A-B-C-D-F has total length 8, which is the smallest of all routes.
    • No, the minimax route is A-C-D-F with total length 9.
    • No, the minimax route is the longest route with total length 11.
    • No, the minimax route has total length 10.

17. Why does dynamic programming work for this shortest route problem?

    • D lies on every route, so only D needs checking.
    • Each arc is used exactly once in any route.
    • The best route to D is fixed once found, so any best route to F through D must use it.
    • The longest route is always found first.

18. In the same network, if the best route to E is extended, what is the shortest route from A to F that passes through E?

    • 12
    • 11
    • 9
    • 10

19. In the same network, if the arc C to D is changed from 2 to 9, what is the new shortest route length from A to F?

    • 10
    • 16
    • 11
    • 15

20. Which feature makes a problem suitable for dynamic programming?

    • It requires every variable to be an integer between zero and one.
    • It splits into stages where the best decision depends only on the current state.
    • It has only two decision variables and no stages.
    • It has an unbounded number of stages with no states.

Related quizzes

• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions
• Definition and derivation of probability generating functions Quiz · 3B.7.1 · 20 questions