Description
1. Solve Q1 from the chapter on Greedy Algorithms from the book by Jeff Erikson (listed as one
of the reference books for this course in my course outline). (10 marks)
2. Recall the following problem from the second tutorial sheet.
Suppose you are helping out a university to design their exam correction schedule. The exam
has two parts: objective type questions, to be corrected by a computer and subjective type
questions to be corrected by the teachers. The university has as many teachers as the number
of answer sheets (say n), but only one computer. It has been decided that each teacher i will
correct the second part of the ith answer sheet. The second part is to be corrected only after
the first part has been corrected.
For each answer sheet i ∈ [n], you are given two durations ti,1 and ti,2, where
• ti,1 indicates the time taken by the computer to correct the first part of the ith answer
sheet and
• ti,2 indicates the time taken by the ith teacher to correct the second part of the ith answer
sheet.
The computer can correct only one answer sheet at a time. The teacher i (for any i ∈ [n])
can correct the second part of the ith answer sheets immediately after the computer finishes the
first part and she can do so independently of any other teacher.
Consider the following greedy strategies for handling the above problem.
(a) Sort the jobs in non-increasing order of the duration required to correct the first part (i.e.
ti,1) and schedule as per this ordering.
(b) Sort the jobs in non-increasing order of the duration required to correct the second part
(i.e. ti,2) and schedule as per this ordering.
(c) Sort the jobs in non-increasing order of the total time taken to finish correcting both the
parts (i.e. ti,1 + ti,2) and schedule as per this ordering.
(d) Sort the jobs in non-decreasing order of the duration required to correct the first part
(i.e. ti,1) and schedule as per this ordering.
(e) Sort the jobs in non-decreasing order of the duration required to correct the second part
(i.e. ti,2) and schedule as per this ordering.
1
A subset of these give the optimal solution. Identify the correct subset. In particular, for each
strategy do the following: (10 marks)
• Prove that it is optimal.
• Or show that it is not optimal by giving a counter example of size at most n = 2.
3. There are n tasks where i-th task has an execution time ti and deadline di
. There are also
precedence constraints amongst the tasks, specified by a directed acyclic graph having the
tasks as vertices. If there is an edge from task i to task j, then task j cannot start before
task i has been completed. Describe a polynomial-time algorithm to determine whether all
tasks can be completed before their respective deadlines, on a single machine. Argue about
the correctness of your algorithm in detail. (10 marks)
4. Consider an arbitrary undirected connected graph G with arbitrary positive weights assigned
to the edges of G. Describe greedy algorithms for the following problems. In each case perform
the time analysis and give a correctness proof. (10 marks)
(a) Find a minimum weight subset of edges to be removed so that there are no cycles in G.
(b) Suppose R is a specified subset of the vertices of G. It is required to connect every vertex
not in R to some vertex in R by a path. Determine the minimum weight subset of edges
required to achieve this.
(c) Find the second minimum weight spanning tree in G. Assume the weights are distinct.
2
