/Discuss this assignment. /Solutions are available.

1. Space Station Cleanup

The Orbitex company operates a ring-shaped space station that is divided into n cargo bays, numbered 1 through n in order around the ring. Tragically, the space station has been occupied by Leptons: each bay i contains m_i of these repulsive creatures. So repulsive are the Leptons that the space station will tear itself apart unless enough Leptons can be cleaned out that no two adjacent bays (i.e., bays with numbers i and i+1 or n and 1) both contain Leptons. But removing Leptons is very expensive---each Lepton requires a crack team of Imperial Space Marines to capture and expel it.

Give an efficient algorithm for computing the minimum number of Leptons that must be removed so that no two adjacent bays both contain Leptons.

2. Rocket to Russia

A side-line of Orbitex's business is second-day package delivery from the United States to Russia using disarmed intercontinental ballistic missiles. Because of the difficult of scheduling missile launches, Orbitex requires its customers to submit their shipping schedules at the start of each n-day period and to organize their shipments into standard 1-pound, 2-pound, and 5-pound packages. Orbitex launches one rocket per day, and each package must either be sent on the day it is shipped or on the next day. It costs (w+r)² units of fuel to ship packages whose total weight is w, where r is the (constant) weight of a rocket.

Suppose that you are given for each day 1..n a list of packages to be sent on that day (and their weights). Give an efficient algorithm for computing the lowest total fuel cost of shipping all packages as described above. Compute the running time of your algorithm as a function of n and the total number of packages m. You should assume that all remaining packages must be shipped on the last day (the company runs out of rockets after it uses up n).