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.