1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
makkiz [27]
3 years ago
12

Barr the Bear has started a business to sell fish to Poe and his fellow penguins. The penguin customers submit many fish orders,

but Barr can only process one order at a time. Suppose that Barr currently has orders from n penguin customers (label them as 1, 2, . . . , n). Customer i’s order takes ti time to complete. Barr is going to process each penguin’s order one by one, and the scheduling of orders can be described as a permutation of the customers. Let Ci denote the completion time of order i. For instance, if customer j’s order is the first to be completed, then we would have Cj = tj (assume Barr begins processing orders at time 0); if customer k’s order is the second to be completed after that, then Ck = Cj + tk = tj + tk, and so on. Each customer is of different importance to Barr’s business, and we denote this relative weight by wi (for customer i). Barr wishes to minimize the weighted sum of the completion times of n orders, Pn i=1 wi · Ci . Intuitively, the more important a customer is, the sooner Barr wishes to complete the customer’s order. Design an O(n log n) algorithm to solve this problem to help Barr. You are given a set of n orders with a processing time ti and a weight wi for each customer i (assume ti , wi are positive integers). You want to decide an ordering of the customer orders so as to minimize the weighted sum of the completion times. Prove correctness of your algorithm (i.e., optimality) and analyze its runtime.
Computers and Technology
1 answer:
luda_lava [24]3 years ago
5 0

Answer:

Algorithm below designed using Java

Explanation:

import java.util.SortedMap;

import java.util.TreeMap;

import java.util.Vector;

public class SchedulingProblem {

static Vector<Integer> processTime = new Vector<>();

static Vector<Integer> processWeight = new Vector<>();

static SortedMap<Integer, Double> timeWeightRatio = new TreeMap<Integer, Double>() {

};

 

static int number = 2;

public static void main(String[] args) {

processTime.add(1);

processWeight.add(10);

processTime.add(3);

processWeight.add(2);

for (int i = 0; i < number; i++) { // O(N)

timeWeightRatio.put(i, processWeight.get(i) / (processTime.get(i) * 1.0)); // O(log(n))

}

// ------------ O(nlog(n))

int sum = 0, tmpTime = 0;

while (timeWeightRatio.size() > 0) { // O(n)

tmpTime += processTime.get(timeWeightRatio.firstKey()); // O(n)

sum += processWeight.get(timeWeightRatio.firstKey()) * tmpTime; // O(n)

System.out.print(processWeight.get(timeWeightRatio.firstKey()) + " * " + tmpTime + ((timeWeightRatio.size() > 1) ? " + " : " = " + sum));

timeWeightRatio.remove(timeWeightRatio.firstKey()); // O(log(n))

}

 

// >>>> O(nlog(n))

}

}

You might be interested in
What are some limitations when it comes to testing and ensuring program quality? List at
DedPeter [7]

Answer:

the two limitation i can think about is the efficiency like if there are bugs or glitches or if it can get broken into and the second one is if it is running the correct program or not a lot of people deal with this problem.

Explanation: personally these are the two i can come up with at the moment

4 0
2 years ago
Write multiple if statements. if caryear is 1969 or earlier, print "probably has few safety features." if 1970 or higher, print
aliina [53]
If( caryear >= 2000 ):
    print "probably has air bags.\n"
elif( caryear >= 1990 ):
    print "probably has anti-lock brakes.\n"
elif( caryear >= 1970 ):
    print "probably has seat belts.\n"
else:
    print "probably has few safety features.\n"

4 0
3 years ago
In what form do the hexadecimal numbers need to be converted for a computer’s digital circuit to process them?
MrMuchimi

Hexadecimal numbers are just a convenient representation of binary data. When entered as text, they consist of ASCII characters 0-9 and a-f. The numbers will then have to be converted to binary. This is accomplished by converting to uppercase, subtracting the ASCII offset (48 for 0-9 or 55 for A-F), so that the result is a number between 0 and 15 (inclusive). This can be stored in computer memory to represent 4 bits.

Hexadecimal numbers represent binary numbers in the following way:

hex | binary

0 = 0000

1 = 0001

2 = 0010

3 = 0011

4 = 0100

5 = 0101

6 = 0110

7 = 0111

8 = 1000

9 = 1001

a = 1010

b = 1011

c = 1100

d = 1101

e = 1110

f = 1111

As you can see, no other 4 bit combination exists.



5 0
3 years ago
____________ occurs when a provider does not support data export or when a provider's service is unavailable through others.
elixir [45]

Answer:

The correct answer to the following question will be Vendor Lock-In.

Explanation:

Vendor Lock-In: It is also known as Customer Lock-In. The Vendor Lock-In makes the costumer depends on services and products on the vendor. The costumers are not able to use another vendor without changing costs as it creates barriers.

Some ways to avoid Vendor Lock-In, these are as follows:

  • Design your application portable.
  • Keep watching vendor contracts.
  • Arrange both entry and exit with your vendor.

8 0
3 years ago
The means by which an operating system or any other program interacts with the user is called th
natulia [17]
Networking capabilities of a computer
7 0
3 years ago
Other questions:
  • What type of data visual would you use to illustrate trends over time? Gantt chart Bar graph Line chart Scatter diagrams
    5·1 answer
  • _____________ is a service that provides access to hardware resources available over the Internet.
    11·1 answer
  • Upgrading only the motherboard will give some performance improvement to a computer system. Why would the improvement be limited
    14·1 answer
  • What inventor patented the first american movie projector
    15·2 answers
  • Susan has always wanted to be a veterinarian. When doing her research, she answers all self-assessments geared toward that caree
    13·1 answer
  • How much RAM memory is recommended for your computer to be used as a digital darkroom?
    9·1 answer
  • Complete the method, print Multiples(), that takes in a positive integer n, and another positive integer, max. Print out all the
    15·1 answer
  • er reports that he is having problems with his monitor. He explains that his laptop's liquid crystal display (LCD) is no longer
    13·1 answer
  • In this class, it is very common for your computer screen to look like this. What is this?​
    5·1 answer
  • Exercise 3.6.9: 24 vs. "24"5 points
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!