1. Use the branch and bound algorithm to solve the following 0/1 knapsack
problem with capacity K=8. (Maximize &#931; c<sub>j</sub> x<sub>j</sub>
subject to &#931; w<sub>j</sub> x<sub>j</sub> &#8804; 8; x<sub>j</sub> 
&#8712; {0,1}.)

<table border="1">
<tr>
<td>j</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>w<sub>j</sub></td>
<td>1</td>
<td>3</td>
<td>3</td>
<td>2</td>
<td>4</td>
</tr>
<tr>
<td>c<sub>j</sub></td>
<td>2</td>
<td>5</td>
<td>7</td>
<td>6</td>
<td>9</td>
</tr>
</table> <br>

2. Solve the previous problem with capacity K=10 using dynamic 
programming. <br> <br>

3. Rework Example 18.7 replacing the weight w of each directed edge by 
w<sup>2</sup>. <br> <br>

4. Let G be a connected graph with distinct edge weights. Prove or
disprove the assertion that the minimum spanning tree of G is unique. <br>
<br>

5. Let G be a graph on six vertices, labelled 3,5,6,7,9,10. There is an
edge between a pair of vertices in G if the labels are relatively prime
(i.e., have no common factor other than 1). The cost of an edge is the
product of the labels of the vertices it connects. Find a minimum spanning
tree in G.