1 show that the greedy algorithm to minimize the mean, Ask an Expert

Engineering

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).)

View complete question

Computer Engineering, Engineering

Category:- Computer Engineering
Reference No.:- M91643272

Have any Question?Write your Review or question?

Related Questions in Computer Engineering

Part 1whats the importance of a documentation plan please

Part 1: What's the importance of a Documentation Plan? Please provide an example of a Documentation Plan that you would use. Part 2: How do you calculate how long a project will take? These questions are for my Introduct ...

Question suppose that pa b c qa c rb are relations such

Question : Suppose that P(A, B, C), Q(A, C), R(B) are relations such that P contains 6 tuples, Q contains 2 tuples and R contains 3 tuples. Find the maximum possible number of tuples in the relation (P * Q) R, where '* ' ...

Question a file is to be shared among different processes

Question : A file is to be shared among different processes, each of which has a unique id number and a priority level number. The file can be accessed simultaneously by several processes, subject to the following constr ...

Question suppose we have a disk with capacity 98304 gb if

Question : Suppose we have a disk with capacity 98.304 GB, if number of platters 16, an average of 300 sectors per track and 20,000 tracks per surface. Then calculate the number of bytes per sector.

Given the following three months of data what is the

Given the following three months of data what is the coefficient of variation? t, R_t 1, 21.01% 2, -13.83% 3, 15.67% 4, 0.88% 5, -1.32% Express your answer in total return decimal format.

Question in relational algebra is the set difference

Question : In relational algebra: is the set difference commutative or not and Why? What is the difference between multivalued and composite attribute? Explain with Example.

What are some topics that must be covered in a business

What are some topics that must be covered in a business case presented to management?

Carbonated drinks like cola tonic water and club soda are

Carbonated drinks like cola, tonic water and club soda are pleasantly bubbly due to the following decomposition of carbonic acid: H2CO3(aq) → H2O(l) + CO2(g) If a sample of H2CO3 decomposes over water at 50°C, 0.23 L of ...

What are the minimum and maximum values in decimal if an

What are the minimum and maximum values (in decimal) if an 8-bit binary number is given unsigned and two's complement formats?

Quality management plan it should includea short statement

Quality Management Plan. It should include: A short statement that reflects your team's philosophy or objective for ensuring that you deliver a quality system to your client. Develop and describe the following that your ...

4,153,160 Questions Asked
13,132 Experts
2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Recent Questions

Ask Computer Engineering Expert