1.)Given the following items, their weights and values, compute the maximum value of the items that could be accumulated in a knapsack of weight W = 6 lb (also listed in the table). Compute your solutions as:

(i) Fractional Knapsack problem

(ii) Integer Knapsack problem (W = 6 lb)

(iii) Using the result of (ii), determine the total maximum value and the corresponding items that can be picked if the Knapsack weight is reduced to 5 lb.

Show all the work (including the value and history tables for the Integer Knapsack problem)

*I = Item, V= Value, W= Weight

I V($) W(lb)

1 19 1

2 80 4

3 25 2

4 45 3

5 15 1

2.)Run a Breadth First Search (BFS) on the graph and find the level numbers of the vertices as well as identify the tree edges and cross edges.

Use the results to determine whether the graph is bipartite (2-colorable) or not. If the graph is bipartite, identify the two partitions of the graph. If the graph is not bipartite, identify the edges that prevent the graph from being bipartite.

8 4 2 7 5 3