Invite the largest set of friends possible

Assignment Help Computer Engineering

Reference no: EM132142062

Question :

Suppose you are organizing a party for a large group of your friends. Your friends are pretty opinionated, though, and you don't want to invite two friends if they don't like each other.

So you have asked each of your friends to give you an "enemies" list, which identifies all the other people among your friends that they dislike and for whom they know the feeling is mutual.

Your goal is to invite the largest set of friends possible such that no pair of invited friends dislike each other.

To solve this problem quickly, one of your relatives (who is not one of your friends) has offered a simple greedy strategy, where you would repeatedly invite the person with the fewest number of enemies from among your friends who is not an enemy of someone you have already invited, until there is no one left who can be invited.

Show that your relative's greedy algorithm may not always result in the maximum number of friends being invited to your party.

Reference no: EM132142062

Questions Cloud

Is this a good design choice and why : Suppose that new, more powerful arithmetic instruction are added to the instruction set.

Describe the effects of employment discrimination on wages : Describe the effects of employment discrimination on wages. How could this impact ones business decisions in relation to labor costs?

Create a preliminary design for a possible two-table : Create a preliminary design for a possible two-table database for this scenario locating the fields in the most appropriate tables.

Describe both law of demand and law of supply : Describe both "Law of Demand" & "Law of Supply" regarding price changes relative to the substitution and income effect? In your response.

Invite the largest set of friends possible : Your goal is to invite the largest set of friends possible such that no pair of invited friends dislike each other.

Why were not you motivated : Describe a situation where you were no motivated at all... What was missing? Why weren't you motivated? (again use a work situation if you can).

Describe the three forms of price discrimination : Describe the three forms of price discrimination and give examples of where each kind is applied. What would prevent a firm attempting to price discriminate.

How many inputs could we process on the new machine : Given a new machine that is 64 times as fast, how many inputs could we process on the new machine in t seconds?

Describe three key inputs and variable costs : Describe three key inputs (or factors of production) and fixed and variable costs involved in the production of your chosen product or service.

User Account

All Pages