Let  be four matrices with dimensions:

What is the minimum number of scalar multiplications needed to compute the matrix product using Matrix Chain Multiplication?

Consider the following dynamic

programming implementation of the Knapsack problem:

#include<stdio.h>

int find_max(int a, int b)

{

      if(a > b)

         return a;

      return b;

}

int knapsack(int W, int *wt, int

*val,int n)

{

     int ans[n + 1][W + 1];

     int itm,w;

     for(itm = 0; itm <= n; itm++)

         ans[itm][0] = 0;

     for(w = 0;w <= W; w++)

        ans[0][w] = 0;

     for(itm = 1; itm <= n; itm++)

     {

          for(w = 1; w <= W; w++)

          {

               if(wt[itm - 1] <= w)

                  ans[itm][w] = ______________;

               else

                  ans[itm][w] = ans[itm -

1][w];

          }

     }

     return ans[n][W];

}

int main()

{

     int w[] = {10,20,30}, v[] = {60, 100,

120}, W = 50;

     int ans = knapsack(W, w, v, 3);

     printf("%d",ans);

     return 0;

}

An undirected graph G has n nodes. Its adjacency matrix M is given by an n×n square matrix whose diagonal elements (M[i][i], 1 ≤ i ≤ n) are all zeroes and the rest of its elements are ones. Which one of the following is TRUE?

Given a weighted graph where weights of all edges are unique (no two edge have

same weights), there is always a unique shortest path from a source to destination in

such a graph.

In

the given graph, how many intermediate vertices are required to travel from

node a to node e at a minimum cost?