For each of the following, design an algorithm using a greedy heuristic. Justify

Question

For each of the following, design an algorithm using a greedy heuristic. Justify your "value" function for making decisions (Why is it reasonable or natural?) If your algorithm will produce an optimal answer, give a reason (need not be rigorous) and if not, explain why with a counterexample. What is the time complexity for each cases?

A) Design an algorithm which accepts as input a list of n men and n women (all single) and, for every pair, a man and woman, a compatibility score (between 0 and 100; the higher the score, the more compatible the pair). Match women to men so as to maximize the total sum of compatibility scores.

B) In a graph, a clique is a subset of the vertices such that for any two vertices in the clique there is an edge between them. Given a graph, find a largest clique.

C) A ski shop in a resort has n pairs of skis for n skiers. No two pairs of skis are the same length and no two skiers are the same height. The disparity in assigning skis to skiers is defined to be the sum of the absolute value of the difference between the height of the skier and the length of the pair of assigned skis. An optimal assignment is when the disparity is as small as possible. Design an algorithm to assign skis to skiers, minimizing disparity.

D) You have an unlimited number of knapsacks, all of capacity 1, and a collection of objects of various weights, all weights being less than 1. You want an algorithm to put objects into knapsacks so as to minimize the total number of knapsacks used.

Explanation / Answer

D)

Suppose the items are 1, 2,... ,n.
Weight of item i is wi.

CapLeft = S.
For i = 1 to n do {
2. Pick min(CapLeft,wi) of item i.
3. TotalV aluePicked = TotalValuePicked + min(CapLeft,wi).
4. CapLeft = CapLeft min(CapLeft,wi).
}

Complexity: O(n)

A)

Let womesLeft = ListWomen(1 to 100)
for Mi in ListMen(1 to 100)
{
for Wi in (womensLeft)
{
1. Pick Wi which results in max score max( computeComptabiltyScore(Mi,Wi), ...,computeComptabiltyScore(Mi,Wi) )
2. Remove the Wi value for the above M1,Wi pair which returns max(compatibiltyScore) from ListWomen. womensLeft = womensLeft - Wi

}
}

Best and Worst Complexity will be: O(n^2)

Since for any pair we will have to scan all the members in both the list.

B)

Let the Clique be = C
Let Vn be the new Vertex from the vertex List allVertexList

for (Vn in allVertexList)
{
flag = 0;
for all Vi in C
{
if (Exists Ei between Vn and Vi){
flag++;
}else{
flag = 0;
exit;
}
}

if (flag > 0){
add Vn to C
}
}
return C.size

Complexity O(n^2)

C) To select the minimal disparity pair

we will pair the max of both the sets

max Hi in (H1 to Hn)
pair with
max Li in (L1 to Ln)

Complexity O(2n)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.