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, D), (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

Consider the undirected graph below and Kruskal's algorithm for computing a minimum spanning tree. In which order are the edges added to the solution?

Consider the undirected graph below and Prim's algorithm for computing a minimum spanning tree using node S as the source node. In which order are the edges added to the solution?

Consider the undirected, unweighted graph below. Assuming that node S is the starting point (i.e., first node to be visited) and that whenever a node has multiple neighbours that need to be processed by the algorithm the neighbours would be processed in lexicographical order, answer the following questions regarding the order in which the nodes are visited in a Depth-First Search (DFS) run.

Consider the undirected, unweighted graph below. Assuming that node S is the starting point (i.e., first node to be visited) and that whenever a node has multiple neighbours that need to be processed by the algorithm the neighbours would be processed in lexicographical order, answer the following questions regarding the order in which the nodes are visited in a Breadth-First Search (BFS) run.

What is the worst-case auxiliary space complexity for quick sort when it uses in-place partitioning and selects pivot randomly and without considering any stack tail-recursive optimisation?