Greedy Method
1.For an interval [a,b] the coverage of the interval is all points between a and b. That is, the coverage consists of all x such that a ≤ x ≤ b. For a set of intervals, the coverage of the set is union of the coverage of all intervals in the set.
The input to this problem is a set S of closed intervals given by their end-points. Devise a greedy algorithm to output a subset T of these intervals of minimum size such that the coverage of T equals the coverage of S. The size of T is the number of intervals in T.
2. The input to this problem is an undirected graph with weights on the edges. For a cycle in the grap, the score of the cycle is the weight of the maximum weight edge in the cycle. Devise a greedy algorithm to output a cycle in the graph of minimum score.
3. The input to this problem is an undirected, unweighted graph, and a special vertex v. As output we want a cycle with minimum number of edges that passes through v. In other words, we want a cycle which contains v as one o the vertices, with minimum number of edges.
Your algorithm for the above problem must run in O(m + n), where m is number of edges and n is number of nodes in the graph.
4. Each of n jobs have to be processed on two type of processors. First on a type-P processor and then on a type-Q processor. There is only one type-P processor available so the jobs will have to be processed sequentially on it. However there are n type-Q processors and the jobs can be processed in parallel on them.
Your input is a sequence of n pairs (pi,qi) where pi is the processing time of the ith job on the type-P processor and qi the time on a type-Q processor. Your output is the order in which schedule them so that the finishing time of the last job is minimised. Design a greedy algorithm for this purpose.
Example: If jobs are scheduled in the order (10,5) (5,7) then the finishing time is 22 while the reverse order has finishing time 20. So you should schedule the second job first.
5. Each of n jobs have to be scheduled on one processor. Preemption is not allowed. Each job has a deadline di and a processing time pi. Given a schedule let f(i) denote the finishing time of job i. The lateness of a job f(i) - di if this quantity is greater than zero. Otherwise the lateness is defined to be zero.
The objective of this problem is to find a schedule such that no job is too late. More precisely, design a greedy algorithm that minimises the maximum lateness of a job.
| << Back to Tech Archives |