Consider the following two problems of circulation with demands, in which the demands are indicated in each vertex, and the capacity in each edge.

Problem 1:

Problem 2:

Which of those problems have feasible solutions?

Consider the following flow network with source node s, sink node t, and in which the capacities are indicated in each edge.

A cut partitions the vertices into two disjoint sets, S and T, where S contains all the vertices on the source side of the cut, and T contains all the vertices on the sink side of the cut. Consider the minimum cut of the above flow network and select the option that corresponds to the set S in that cut.

Consider the following variant of the Bellman-Ford algorithm

and the following weighted directed graph

Let S be the source node for the execution of the Bellman-Ford algorithm. If the edges are relaxed in the following order (S, A), (B, C), (S, C), (S, B), (D, C), (E, D), (A, B), (S, E), what is the distance estimate of node C after two iterations of the outer loop of the algorithm are finished? Just type the numerical answer.

Recall the unbounded knapsack dynamic programming problem you have learnt from your lecture, with the following recurrence relation:

You have run the algorithm on the following items:

Using the optimal substructure stated below for a Dynamic Programming solution to the Coins Change Problem:

Complete the MinCoins array given the following values:

• c = [2,4,8,5]
• v = 8

Consider the following variant of the Bellman-Ford algorithm

and the following weighted directed graph

Let S be the source node for the execution of the Bellman-Ford algorithm. If the edges are relaxed in the following order (S, A), (B, C), (S, C), (S, B), (D, C), (E, D), (A, B), (S, E), what is the distance estimate of node C after two iterations of the outer loop of the algorithm are finished? Just type the numerical answer.

Recall the unbounded knapsack dynamic programming problem you have learnt from your lecture, with the following recurrence relation:

You have run the algorithm on the following items:

Using the optimal substructure stated below for a Dynamic Programming solution to the Coins Change Problem:

Complete the MinCoins array given the following values:

• c = [7,2,5,6]
• v = 8

Recall the unbounded knapsack dynamic programming problem you have learnt from your lecture, with the following recurrence relation:

You have run the algorithm on the following items:

Using the optimal substructure stated below for a Dynamic Programming solution to the Coins Change Problem:

Complete the MinCoins array given the following values:

• c = [3,5,8,7]
• v = 8