Greedy Algorithms: Counter Examples

This assignment consists of two parts. 

You should prepare your answers electronically, in a Word document or pdf file. Where mathematical formulas, diagrams etc are needed you can use handwriting and insert them into the document as pictures, but any substantial amount of text should be typeset and not handwritten. 

In line with university policy, marking will be done anonymously. Please do not include your name or other personally identifiable information in your submission.

In each of the following, a greedy algorithm is proposed for the given problem. Give a simple counter example for each of them to show that the proposed greedy algorithm does not always return the optimal solution. You should (1) give an example input, (2) state the solution returned by the greedy algorithm on that input, and (3) state the optimal solution (or indeed any better solution than the greedy one) for that input.

A. Input:An undirected graph G(V, E).

Problem: Find a minimum spanning tree T of G.

Choose an arbitrary vertex s in G

Initialise S := {s}, T := {} (empty set), and u := s

while S /= V do

Find the minimum-weight edge e among all edges (u, v) where v is not in S

Add v to S, add e to T , and set u := v

(Note:  this is not Prim’s algorithm.) [10 marks]

B. Input:A set A of animals, and a set of pairs (a_i, a_j) indicating animal a_i cannot be put together with animal a_j (because for example a_i attacks or eats a_j).

Problem: Choose a subset A^j of animals from A so that the animals in A^j can be safely put together, and that the number of animals in A^j is as large as possible.

Algorithm: Initialise A^j to be empty. For each animal in A, count the number of other animals it can be safely put together. In decreasing order of this count, consider each animal in turn and add it to A^j  if it can be put safely together with all other animals already in A^j. [10 marks]

C. Input:A set of n tasks,  each with a required “amount” of “work”;  a set of  m workers all of whom can work on any of the tasks.

Problem:  Assign the  tasks  to  the  workers  so  that  the  work is  “distributed as  evenly as possible among the workers”, or more precisely, the amount of work assigned to the busiest worker (the one with the largest amount of work) is as small as possible.

Algorithm: Sort the tasks in decreasing order of amount of work. For each task in this sorted order, assign it to the worker who currently (i.e., based on the assignment made so far) has the least amount of work assigned. [10 marks]