Consider the Fractional Knapsack Problem.

$1.(25$ pts$)$ Design a greedy algorithm for Fractional Knapsack Problem that finds an

optimum solution in O$($n log n$).$ Report the pseudocode of your algorithm.

$2.(25$ pts$)$ Implement your algorithm in Python. Randomly generate the inputs and

report the console outputs. Report your Python code scripts.

Question $2$: $(50$ pts$)$ Consider the Vertex Coloring Problem in which we assign different

colors to the adjacent vertices on a given graph G $=($V$,$ E$).$ The objective is to color the

vertices of the graph using minimum number of colors.

Input: A graph G $=($V$,$ E$),$ where V is the set of vertices and E is the set of edges of the

graph G$.$

Output: Color assignments of the vertices using minimum number of colors.

Ex: For the graph G in Figure $1,$ a vertex is a node in the graph and the set of vertices

is V $=\{$v$1,$ v$2,...,$ v$10\}.$ An edge is the line between two vertices and the set of edges is

E $=\{($v$1,$ v$2),($v$1,$ v$5),($v$1,$ v$6),($v$2,$ v$3),($v$2,$ v$7),...,($v$7,$ v$10)\}.$

The vertices v$1$ and v$2$ are adjacent since there is an edge $($v$1,$ v$2)$ between them. On the

other hand, v$1$ and v$7$ are not adjacent since there is no edge $($v$1,$ v$7)$ in the graph. Notice

that the adjacent vertices v$1$ and v$2$ have different colors $($red and green, respectively$),$

whereas non$-$adjacent vertices v$1$ and v$7$ can have the same color $($red$).$ We observe that we

can color the vertices of the graph G in Figure $1$ with $3$ different colors, i$.$e$.,$ red, green, blue.