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.

Given the following pseudocode, derive the recurrence relation that represents its time complexity. 

def fibonacci(n):
    if (n==0 or n==1):
        return n 
    return fibonacci(n - 1) + fibonacci(n - 2)

Let b and c represent constant values. What is the base case and recurrence step?