Algorithm problem

1. Consider the following problem for n jobs, each one of which takes exactly one minute to complete. At any time T = 1, 2, 3, • • •, we can execute exactly one job. Each job i earns a profit of pi dollars if and only if it is executed no later than time di, where di is given as an input. Assume that di is an integer value. The problem is to schedule the jobs to maximize the profit.

Consider the following greedy strategy: For all the jobs with deadline at 1 minute, schedule the job with the maximum profit. Next, for all the jobs with deadline at 2 minutes or less, pick the job with maximum profit from the remaining unscheduled jobs. And so on. For example, consider n = 4, profits P = (50, 10, 15, 300) and deadlines D = (2, 1, 2, 1). The greedy strategy will yield the following solution: job 4 and job 1 to be scheduled for a total of profit of 80 dollars.,CLICK HERE TO GET MORE.........
Give a counter example to establish that this greedy strategy does not always work. No credit will be given for theoretical answers. You must give a concrete counterexample with integers. Clearly state what is the optimal and the greedy strategy solution for your counterexample.
2- A k-coloring og a graph G =(V,E) is a mapping f: V ? {1,2,….,k} such that adjacent vertices and mapped out different colors, i.e, no two neighbors in G receive the same color (i.e., same integer), prove that the following greedy algorithm colors the graph G with most ?(G)+1 colors where ?(G) denote the maximum degree (number of adjacent vertices) of any node v ? V
For I = 1, ……, n do
Color vertex vi using the smallest available color in {1,2,……, ?(G) +1}

3- The prim’s algorithm works correctly when an arbitrary vertex is chosen as a start vertex. Now, prove that the smallest weighted edge (assuming there is only one smallest edge) is always in the tree generated by the Prim’s algorithm.,CLICK HERE TO GET MORE.........
4- Assume that edge weights are distinct in a given graph. Let TK and TP denote minimum spanning trees generated by the Kruskal’s and the Prim’s algorithm. Let k1 < k2 < • • • < kn-1 and p1 < p2 < • • • < pn-1, respectively, denote the weights in TK and TP . Prove that ki = pi
for each 1 <= i <= n – 1.

5- Suppose that in a 0-1 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing profit. Give an algorithm to find an optimal solution to this variant of the knapsack problem, and prove that your algorithm is correct.,CLICK HERE TO GET MORE.........