Find the largest number of these intervals so

Reference no: EM13874361

Could somebody help with these two exercises please

Exercise 1:

Compatible intervals Given n open intervals (a1, b1), (a2, b2), . . . , (an, bn) on the real line, each representing start and end times of some activity requiring the same resource, the task is to find the largest number of these intervals so that no two of them overlap.

Investigate the three greedy algorithms based on

a- Earliest start first.
b- Shortest duration first.
c- Earliest finish first.

For each of the three algorithms, either prove that the algorithm always yields an optimal solution or give a counterexample showing this not to be the case.

Exercise 2:

Rumor spreading problem: There are n people, each in possession of a different rumor. They want to share all the rumors with each other by sending electronic messages. Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee.

a- Design a greedy algorithm that always yields the minimum number of messages they need to send to guarantee that every one of them gets all the rumors
b- Give the efficiency of your proposed algorithm as a function of n.

Reference no: EM13874361

Questions Cloud

What are universal wastes? : What are universal wastes?

Company has calculated its pretax income : At the beginning of 2010, the retained earnings of the Cameron Company were $212,000. For 2010, the company has calculated its pretax income from continuing operations to be $120,000. During 2010, the following events also occurred:

How would presence of second technology that had higher cost : How would the presence of a second technology that had higher operating costs but lower capacity costs affect peak-load pricing and investment in the capital-intensive technology?

Inverse distance weighted interpolation : The following is a Python implementation of IDW. This function takes two input variables. Z is a list of lists where each element list contains four values: X, Y, Value, and Distance to target point. Z can also be a NumPy 2-D array. Variable b is the..

Find the largest number of these intervals so : Compatible intervals Given n open intervals (a1, b1), (a2, b2), . . . , (an, bn) on the real line, each representing start and end times of some activity requiring the same resource, the task is to find the largest number of these intervals so that n..

Explain why it is possible to interpret a two-part tariff : Explain why it is possible to interpret a two-part tariff as a two-block-rate tariff. Explain the circumstances under which this equivalency might not hold. Why might a consumer choose to have access and still consume zero units?

Practice of public health or community health nursing : Identify a new law or regulation that affects the practice of public health or community health nursing.

Show the number of students whose zip is 07070 : Show the number of students whose zip is 07070. List all students (display student_id, first name, last name, and employer) who live in Columbus, OH. Show the zip, state and city that have > 5 students as residents.

How was dr. snow able to test his proposed explanation : According to the "Answering the Three Questions" video, in what way was the "miasmas" (bad smells) explanation inconsistent and How was Dr. Snow able to test his proposed explanation?

User Account

All Pages