Eric Shook, a PhD student at the University of Illinois at Urbana-Champaign, has graciously suggested the kernel of a problem loosely based on his dissertation work. You will be given a simplified execution model of a linear boundary problem. An integer value is associated with each processing node representing computational workload. The value on the line connecting nodes represents the additional communication cost from using message passing instead of shared memory exchange of boundary values. For instance, in the example below, if we have three processors, we are then looking to make two cuts in the linear chain, which accomplishes the load balancing of the two pieces to the two processors.


Suppose we made a cut at 6 and 496, which might seem perfect at first glance. However the compute time for the first piece is 19+(6), for the second is (6)+42+28+7+496, and 496+2 for the third, i.e. 25, 579, and 498. Since we have to wait till all are done, the overall time is max(25, 579, 498) or 579. This is actually not the best place to do the two cuts. The best is the min(of the cost of all possible combinations of two cuts)

It turns out a better cut is at 17 and 13, max(19+42+(17), (17)+28+(13), (13)+7+2), which is max(78, 58, 22), which is 78.

The best cut is at 6 and 17, max(19+(6), (6)+42+(17), (17)+28+7+2), which is max(25, 65, 54), which is 65.

You are given three files (see below), which you must run against the same code. In all three cases you are looking for the best solution. A less desirable, but possibly more practical solution is to write a code that yields a pretty good solution. You will of course need to describe your algorithm and why it is either the best solution or a pretty good solution.

The first line of the file gives the number of processors.

Subsequent lines contain two numbers:

1. The execution time of the task
2. The cost to add to the task group on the left and the right, if a cut is made at this spot

The last line corresponds to the last task and thus does not have a second number.