CSE 551 Assignment 4 Solution

Furthermore, please note that the graders will grade 2 out of the 4 questions randomly. Therefore, if the grader decides to check questions 1 and 4, and you haven’t answered question 4, you’ll lose points for question 4. Hence, please answer all the questions.
1. In the algorithm for the Activity Selection Problem discussed in class, we order the intervals in increasing order of theirfinish times and consider them in this order as we schedule non-conflicting intervals. Consider the following variations of the Activity Selection greedy algorithm: [25]
• Sort the intervals in decreasing order of their start times and consider them in this order in the algorithm, as we select non-overlapping intervals to include in an optimal solution to the problem.
• Sort the intervals in decreasing order of their lengths and consider them in this order in the algorithm, as we select non-overlapping intervals to include in an optimal solution to the problem.
• Sort the intervals in increasing order of the reciprocal values of their lengths and consider them in this order in the algorithm, as we select non-overlapping intervals to include in an optimal solution to the problem.
For each of the variations, identify if the strategy will ensure finding the optimal solution for ASP (that is maximum size of mutually compatible activities). If you think that the answer is yes, then please provide your arguments. If your answer is no, then please provide a counter-example.
2. Consider a single server that has n jobs to be done. The time taken to run each job Ji is ti which is known in advance. The jobs should be finished in the order that minimizes the average waiting time for the jobs. [25]
• Give a greedy algorithm that will find this order and prove its correctness.
• Can there be multiple schedules which give minimum average waiting time if the time taken for each of the job is distinct, that is no two jobs have same running time? Explain.
3. Let G = (V,E) be an undirected graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover is one with the fewest number of vertices. Consider the following greedy algorithm for this problem:
(a) Procedure COVER(V, E)
(b) U ← ϕ
(c) loop
(d) Let v ∈ V be a vertex of maximum degree
(e) U ← U ∪{v};V ← V −{v}
(f) E ← E −{(u,w)} such that u = v or w = v
(g) until E = ϕ go to (c)
(h) return (U)
(i) end COVER
Does this algorithm always generate a minimum node cover? If yes, provide some arguments as to why you think so. Else, then provide a counter example where this algorithm fails. [25]
1

Figure 1: Network for Q3
4. For the network shown in Figure 1 above, compute the maximum flow from Vancouver to Winnipeg using the FordFulkerson algorithm discussed in class. Show all your work. [25]
2