he maximum value of 𝑥 such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________ 

Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 

11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by 𝑉𝑜𝑝𝑡. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by 𝑉𝑔𝑟𝑒𝑒𝑑𝑦.

The value of 𝑉𝑜𝑝𝑡−𝑉𝑔𝑟𝑒𝑒𝑑𝑦 is ____

If a problem can be broken into subproblems

which are reused several times, the problem possesses ____________ property.

A company has a number of offices and wants to design a communications network linking them. For certain pairs (v,w) of offices, it is feasible to build a direct link joining v and w, and there is a known (positive) cost cv w incurred if link vw is built. The company wants to construct enough direct links so that every pair of offices can communicate (perhaps indirectly). Subject to this condition, the company would like to minimize the total construction cost. An appropriate problem similar to this one whose algorithm can be used to solve this problem is (mention the name of the algorithm for the problem-if one exists, in the justification):

You

are given a knapsack that can carry a maximum weight of 60. There are 4 items

with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum

value of the items you can carry using the knapsack?

 Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

In a weighted graph, assume that the shortest path from a source A to a destination D is correctly calculated using a shortest path algorithm. Is the following statement true or false? 

Statement: If we increase the weight of every edge by 1, the shortest path always remains the same.