COMP3121/9101 22T3 — Assignment 4

Question 1 Bridge Support

[20 marks] The NSW government has decided to build a new bridge. The bridge is to be n meters long, where A[i] is the maximum load on the bridge between (i − 1) meters and i meters.

The government have contracted you to complete this project, and you’ve decided to build the bridge in spans of integer length.  The cost of building a span is given by the length of the span squared, plus the maximum load that the span needs to withstand. The total cost of building the bridge is the sum of the cost of all spans. More explicitly:

total cost = 工 (sR − sL )2 + max(A[(sL + 1)..sR ])

s∈spans

where sL  and sR  are the left and right endpoints respectively of the span s.

Your  goal  is  to  determine  the minimum cost  required  to  build  a  bridge  that  supports  the load.

1.1 [14 marks] Design an O(n3 ) algorithm which achieves your goal.

1.2 [6 marks] With an election looming, the NSW government has asked you to hurry up. Design an algorithm that achieves the goal in O(n2 ).

Question 2 Mountain Radios

[30 marks] Alice and Bob are bored of the park, and have decided to go mountaineering!  They will each be traversing the mountain and moving through a sequence of n camps. Both Alice and Bob will always spend the night at one of their camps.  Alice’s camps are given by a sequence of coordinates pairs A1 , ...,An , where Ai  = (Ai北 ,Aiy ), and Bob’s camps are given as B1 , ...,Bn , where Bj  = (Bj北 ,Bjy ).  On the first night, Alice will spend the night at camp A1  and Bob will spend the night at camp B1 .  Each day, both Alice and Bob have the choice of staying at their current camp or moving to the next camp in their sequence. They can never move back to a camp they have previously visited. At least one of them must move each day, meaning that both Alice and Bob will have reached their final camps no later than the (2n − 1)th night.

Alice and Bob would like to be able to talk to each other at night via a radio, but all of the wireless radios available for purchase have a fixed range.   Alice has noticed that if they care- fully plan who moves to the next camp on each day, it will affect how far apart they get dur- ing their journey. The distance between two coordinates  (x1 ,y1 ) and  (x2 ,y2 ) is calculated as d = ^(x2 − x1 )2 + (y2 − y1 )2 .

Figure 1: The simple example described above. The blue line represents the path Alice will walk and the green line represents the path Bob will walk. The red line shows the furthest apart Alice and Bob must get during their journey.

2.1 [15 marks] Design an O(n2 ) algorithm to determine whether a radio with a range of D will allow them to communicate every night.

In the provided example, your method should determine that it is impossible for any value of D < 3, and possible otherwise.

2.2 [15 marks] Design an O(n2 ) algorithm that calculates the minimum range required for Alice and Bob to be able to communicate every night.

In the provided example, your method should calculate a minimum required range of 3.

Question 3 KFC Now!

[20 marks] There are n ≥ 0 people queuing for KFC. The ith  person has an hunger of hi , and everyone in line has a distinct hunger. A person’s ‘annoyance’ is defined as the number of people in front of them who are less hungry, and the annoyance of the entire queue is the sum of every person’s annoyance.

Given the hunger of every person, your goal is to determine how many arrangements of the queue will result in a total annoyance of exactly k .

3.1 [12 marks] Design an O(n2 k) algorithm that achieves the goal.

3.2 [8 marks] Design an O(nk) algorithm which achieves the goal.