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?

For a sequence of n integers in range [-2 … n-2], and considering worst-case time complexity, which sorting algorithm(s) can be optimally implemented to guarantee a linear time to sort this sequence? 

Solve, in big-θ, the following recurrence relation

T(n) = 4 * T(n/4) + c, where n >= 4
T(n) = b, where n = 1

for constants b and c.