An undirected graph G(V, E) contains n ( n > 2 ) nodes named v₁ , v₂ ,….v_n. Two nodes v_i , v_j are connected if and only if 0 < |i – j| <= 2. Each edge (v_i, v_j ) is assigned a weight i + j. A sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

An undirected graph G(V, E) contains n ( n > 2 ) nodes named v₁ , v₂ ,….v_n. Two nodes v_i , v_j are connected if and only if 0 < |i – j| <= 2. Each edge (v_i, v_j ) is assigned a weight i + j. A sample graph with n = 4 is shown below. The length of the path from v5 to v6 in the MST of previous question with n = 10 is

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below.

Let L_i, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize L_n−1=1.

For all i such that $$0 \leq i \leq n-2$$

$$L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$$

Finally, the length of the longest monotonically increasing sequence is max(L₀, L₁,…,L_n−1)
Which of the following statements is TRUE?

Four matrices M₁, M₂, M₃ and M₄ of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M₁ $$\times$$ M₂) $$\times$$ (M₃ $$\times$$ M₄)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M₁ $$\times$$ M₂) $$\times$$ M₃) $$\times$$ M₄), the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is: