CSI 3108-02代写、代做java设计、java编程语言调试、programming代做

日期：2019-11-29 12:54

Algorithm Analysis Problem Set 4

CSI 3108-02, Fall 2019 Due at 5:00pm, Wednesday, December 4

This is a programming assignment. You are not allowed to collaborate with

anyone on this assignment.

Submit your source code(s), zipped as yourStudentID.zip. For example, if your

student ID is 2019000000, then you must zip all your source code(s) into

2019000000.zip and submit this file. Each class should have its own .java file,

of which the filename is the same as the class name. Do not include your

student ID as part of the class names.

Your program must not assume one particular newline convention, i.e., your

program must be ready for both CR+LF and LF as the newline markers in the

input file. One easy way to achieve this is using BufferedReader.readLine().

(1) Power optimization. (70 points)

There are n jobs, numbered 1 to n, that you want to execute on two computers. One of the

two computers is equipped with a high-performance CPU but no GPGPU, while the other

has a powerful GPGPU with an outdated CPU. Since some jobs can effectively utilize

GPGPU, when a job is executed on one of the two computers, its power consumption will

differ depending on where it is executed. For 1 ≤ i ≤ n, let ai and bi denote the power

consumption of Job i when it is executed on the first computer (called Computer A) and

the second computer (called Computer B), respectively. Each job must run either on

Computer A or on Computer B: it cannot run on both computers.

Some pairs of these jobs need to perform inter-process communication (IPC). If two jobs

needing IPC are executed on the same computer, IPC does not consume any additional

power. However, if the two jobs are run on different computers, a nonnegligible amount

of power will be additionally consumed by the communication link. Let cij denote this

added power consumption when Job i and Job j are executed on different computers.

Note that not all pairs of jobs require IPC.

Our objective is to assign every job to one of the two computers so that the total power

consumption is minimized.

Write a Java program that, given n, a, b, and c, along with the list of pairs of jobs that

need IPC, determines the minimum total power consumption and an assignment that

achieves this minimum. If there is more than one such assignment, your program can

output any one of them.

Your program must read the input from input.txt in the current working directory, and

output the results to output.txt in the current working directory. The first line of input.txt

contains the number of jobs n. Then the (i + 1)-st line (1 ≤ i ≤ n) contains ai and bi

, in

that order, separated by a space. The (n+ 2)-nd line contains the number of pairs of jobs

that need IPC; let m denote this number. Each of the following m lines contain i, j (the

IDs of two jobs that need IPC) and cij (the added amount of power consumption when

Job i and Job j are executed on different computers). These three items i, j, and cij are

given in that order, separated by a space. In total, the input file consists of n + m + 2

lines.

The first line of output.txt shows the minimum total power consumption. For 1 ≤ i ≤ n,

the (i + 1)-st line shows which computer Job i is assigned to: the line contains a single

character A if it is run on Computer A and B otherwise (all in uppercase). The output

consists of n + 1 lines in total.

You can assume that 1 ≤ n ≤ 100, 0 ≤ m ≤ 1, 000, and 1 ≤ ai

, bi

, cij ≤ 1, 500, 000 for all

i and j. You can also assume that all a, b, and c’s are positive integers. Your program

must terminate within 30 seconds on the TA’s computer.

The entry point of your program must be CSI3108.main(). Do not make any typos.