Question 1

In solving a shortest route problem using dynamic programming the stages represent how many arcs you are from the terminal node.

Accepted Answer

In dynamic programming, the stages represent the decision points, i.e., the nodes of the graph being traversed. The number of arcs taken to reach these nodes is not relevant.

Question 2

Dynamic programming is a general approach with stage decision problems differing substantially from application to application.

Accepted Answer

This statement is true. Dynamic programming is a problem-solving technique that involves breaking down complex problems into smaller subproblems and solving them in a recursive manner, with the optimal solution at each stage leading to the optimal solution of the overall problem. This technique is used in a wide range of applications, including optimization, scheduling, resource allocation, and more. The specific details of the stage decision problems will differ depending on the application.

Question 3

If x₃ = t₄(x₄,d₄) = x₄ ? 2d₄ and r₄(x₄,d₄) = 16d₄, the stage transformation function is A)t B)x C)r D)d

Accepted Answer

A

Question 4

The solution of stage k of a dynamic programming problem is dependent upon the solution of stage k?1.

Accepted Answer

In dynamic programming, the solution of a certain stage depends upon the solution of the previous stage. Therefore, the statement is true.

Question 5

A return function is a value such as profit or loss associated with making decision d_n at: A)stage n for specific value of output variable x_n. B)stage n for a specific value of input variable x_n. C)stage n for a specific value of stage m. D)input n for a specific value of output variable x_n.

Accepted Answer

The answer of A return function is a value such...

Question 6

State variables in a shortest route problem represent&#10;A)decisions.&#10;B)locations in the network.&#10;C)the minimum distance between nodes.&#10;D)None of the alternatives is true.

Accepted Answer

State variables represent the locations in the network in a shortest route problem. They are used to keep track of the nodes visited and the distances between them in order to determine the shortest path. Decisions refer to the choices made by the algorithm at each step, and the minimum distance between nodes is a result of the algorithm's calculations.

Question 7

Dynamic programming is a general approach rather than a specific technique.

Accepted Answer

Dynamic programming is a general approach that involves breaking down complex problems into smaller subproblems and solving them recursively. It is not a specific technique or algorithm. Different techniques, such as memoization or tabulation, can be used within the framework of dynamic programming to solve specific problems efficiently.

Question 8

The output of stage k is the input for stage k?1.

Accepted Answer

This is true for a pipeline where the output of each stage feeds into the subsequent stage as input.

Question 9

Stages of a dynamic programming solution procedure&#10;A)represent parts of a large mathematical model.&#10;B)often represent a sequence of decisions made over time.&#10;C)are usually not independent of each other.&#10;D)All of the alternatives are true.

Accepted Answer

All of the alternatives are true. Dynamic programming involves breaking a large mathematical model into smaller, more manageable parts (A). These smaller parts often represent a sequence of decisions made over time (B). The smaller parts are usually not independent of each other, as the solution to one stage can affect the solution to subsequent stages (C).

Question 10

Dynamic programming requires that its subproblems be independent of one another.

Accepted Answer

Dynamic programming often involves solving overlapping subproblems, where the solution to one subproblem depends on the solution to another subproblem. However, the key requirement is that the subproblems can be solved independently of each other once their solutions are known. This allows for the efficient reuse of computed solutions, which is what makes dynamic programming so powerful.

Question 11

State variables are a function of a state variable and a decision.

Accepted Answer

The answer of State variables are a function of a...

Question 12

The stage transformation function&#10;A)transforms the input into the output.&#10;B)transforms a stage into a state.&#10;C)is a different function for each stage.&#10;D)None of the alternatives is true.

Accepted Answer

The answer of The stage transformation function&#10;A)transforms the input into...

Question 13

Stage transformation functions&#10;A)are linear.&#10;B)calculate the return.&#10;C)determine the output of the stage.&#10;D)All of the alternatives are true.

Accepted Answer

The answer of Stage transformation functions&#10;A)are linear.&#10;B)calculate the return.&#10;C)determine the...

Question 14

Dynamic programming, when used for the shortest route problem, requires complete enumeration of paths from the beginning to ending node.

Accepted Answer

The answer of Dynamic programming, when used for the shortest...

Question 15

Dynamic programming must only involve a finite number of decision alternatives and a finite number of stages.

Accepted Answer

The answer of Dynamic programming must only involve a finite...

Question 16

The return function for a shortest route problem refers to two directional arcs between nodes.

Accepted Answer

The answer of The return function for a shortest route...

Question 17

The knapsack problem is to determine how many units of each item to place in the knapsack to:&#10;A)minimize total value.&#10;B)maximize total value.&#10;C)minimize the number of items in the knapsack.&#10;D)maximize the number of items in the knapsack.

Accepted Answer

The answer of The knapsack problem is to determine how...

Question 18

If x₃ = t₄(x₄,d₄) = x₄ ? 2d₄ and r₄(x₄,d₄) = 16d₄, the subscripts refer to A)state. B)stage. C)transformation. D)return.

Accepted Answer

The answer of If x₃ = t₄(x₄,d₄) = x₄ ?...

Question 19

If x₃ = t₄(x₄,d₄) = x₄ ? 2d₄ and r₄(x₄,d₄) = 16d₄ the state variable is A)t B)x C)r D)d

Accepted Answer

The answer of If x₃ = t₄(x₄,d₄) = x₄...

Deck 21: Dynamic Programming