## Description

Computer Science 320SC

Programming Assignment 4

Requirements

This fourth assignment lets you get familiar with successive improvements with algorithm design for

a concrete “real-world” problem. There are three programs required using cleaver brute-force, divideand-conquer and dynamic programming. It is worth 5% of your total course marks. Please try and test

with your own generated input cases before submitting to the automated marker.

Problem: Fibre Cabling

A big internet infrastructure company in New Zealand has been tasked with wiring up homes with

fibre optic broadband cables. However, since this is a business for profit, not all homes will need to

be hooked up. The company Circus has asked you to help them determine which homes they should

connect cables, ready for sale. The main constraint of this problem is that if two homes on a street is

cabled then all intermediate homes on the path between them must also be, irrespective if they signup for an internet plan or not. The company makes a certain amount of profit based on which plan

customers purchase; it also losses money if a complicated connection is done without any plan purchase.

An input scenario is a sequence a1, a2, . . . , an of n ≤ 100000 integers on one line, denoting the profit/loss

for connecting each house on a street of length n. The entry at position i, 1 ≤ i ≤ n, is positive for

profit and negative for loss. We have many streets of data to process and a single line containing only

one integer denotes the end of input (this scenario is not processed). We can assume each scenario has

at least one positive house value ai

, since otherwise Circus would not even consider cabling that street.

The output of your program, one line per each scenario, is the maximum profit obtainable for that

street.

Sample Input:

10 -4 5

3 -4 5

3 -10 4 41 -1

10 0 20 -4 -3 8 -7 4

4 4 -3 1 0 0 -4 1 3 -4 7 -2 -2 3

1

Sample Output

11

5

45

31

9

1

Submission 1: fibreBrute.ext

There is a natural simple brute-force algorithm that tries and sums every subsequence ai + ai+1 +

ai+2 + · · · + aj−1 + aj for 1 ≤ i ≤ j ≤ n. Then return the maximum of all combinations of starting

positions i and ending positions j This algorithm has running time O(n

3

). With a simple observation

that, one can compute both the sums ai + · · · + aj+1 and ai+1 + · · · + aj from ai + · · · + aj with one

addition/subtraction, we can get a O(n

2

) algorithm. An implementation of this algorithm is required

for a program named fibreBrute.ext, where ext is an extension of the programming language of your

choice.

Submission 2: fibreDC.ext

For this part of the assignment we want to develop an even higher performance algorithm based on the

divide-and-conquer design approach. An O(n lg n) algorithm is possible by using an algorithm similar

to the ‘counting inversions’ algorithm given in lectures. Consider the following sequence:

a1, a2, . . . , a n

2 −1, an/2, a n

2 +1, . . . , an−1, an

An optimal solution either uses the element an/2 or not. So we can take the maximum of three cases:

recursively solve subproblem a1, . . . , a n

2 −1, recursively solve subproblem a n

2 +1, . . . , an, or the “conquer”

case that includes an/2. Submit a program named fibreDC.ext.

Submission 3: fibreDP.ext

Finally we want to improve to an O(n) time algorithm. You should use dynamic programming to solve

this case. Submit a problem named fibreDP.ext.

Comments

The markers will quickly look at the last of each of your submissions to make sure that you implement

all three algorithms and not just submit the fastest one, say fibreDP.ext, to the automarker for all

problems. The first implementation fibreBrute.ext is worth one mark and the other two improvements

are worth two marks each. There will be easy and hard test cases loaded on the automarker for the

two problems worth two marks. The number of submissions per problem is limited to 8 before a 20%

deduction is applied (assuming you solve a particular problem eventually). Note that for the hard test

cases the sums may require arbitrary precision integers (e.g. use Python 3 ints, Java BigInteger data

type, or C/C++ GMP library).

2