Completion time for multiprocessor

Assignment Help Basic Computer Science

Reference no: EM13968326

1. Show that the greedy algorithm to minimize the mean completion time for multiprocessor job scheduling works.

2. The input is a set of jobs j1, j2, ... , jN, each of which takes one time unit to complete. Each job jiearns di dollars if it is completed by the time limit ti, but no money if completed after the time limit.

a. Give an O(N2) greedy algorithm to solve the problem.

b. Modify your algorithm to obtain an O(N log N) time bound. (Hint: The time bound is due entirely to sorting the jobs by money. The rest of the algorithm can be implemented, using the disjoint set data structure, in o(N log N).)

Reference no: EM13968326

Questions Cloud

What fact or piece of information did you learn that was new : Take the "Find Your Fit" assessment under "The profession" menu along the left hand side. What does it suggest as "you early career" type, if you were to go into the accounting field?

Method for constructing the header of size : Part of the encoded ?le must be a header indicating the Huffman code. Give a method for constructing the header of size at most O(N) (in addition to the symbols), where N is the number of symbols. Complete the proof that Huffman's algorithm generates..

What are benefit of federal and state social welfare program : What are the benefits of federal and state social welfare programs today? What are the drawbacks? What experiences have you, or someone you know, had with a social welfare program?

Consider an oil-wildcatting problem : Consider an oil-wildcatting problem. A decision maker has mineral rights on a piece of land that he believes may have oil underground. There is a 30% chance that the decision maker will strike oil if he drills. If he drills and strikes oil, then the ..

Completion time for multiprocessor : 1. Show that the greedy algorithm to minimize the mean completion time for multiprocessor job scheduling works. 2. The input is a set of jobs j1, j2, ... , jN, each of which takes one time unit to complete. Each job jiearns di dollars if it is comple..

Determine the electric potential energy of the initial state : There is the information and then the questions: A stationary block has a charge of +6.0×10-4 C. A 0.80-kg cart with a charge of +4.0×10-4 C is initially at rand separated by 4.0 m from the block. The cart is released and moves along a frictionles..

Identify a domestic and an international terrorist incident : Identify a domestic and an international terrorist incident. Discuss the differences and similarities between the groups involved and the tactics that are employ in these incidents.

Find L-W-Lq-wq and the probabilities : Goofy owns and manages a hot dog stand near Walt Disney World. Although Goofy can serve 30 customers per hour on average (μ), he only gets 20 customers per hour (λ). Because Goofy could wait on 50% more customers than actually visit his stand, it doe..

Subset of the year baseball cards : The baseball card collector problem is as follows: Given packets P1, P2, ... , PM, each of which contains a subset of the year's baseball cards, and an integer, K, is it possible to collect all the baseball cards by choosing ≤ K packets?

User Account

All Pages