CS 1510 Midterm 1

Fall 2001

1.

(40 points) Consider the following real-world budget problem that challenges your instructor, and many other government/academic bureaucrats. The input consists of a collection of accounts $A_1, \ldots, A_n$, and a collection of events $E_1, \ldots, E_m$. Each account A_i has a start date r_i and an end date d_i. Further each account A_i contains an amount a_i of money. Each event E_j happens on a date e_j and has a cost of c_j dollars. The cost c_j for event E_j, or some portion thereof, can be charged to any account A_i that is open during the date e_j, that is, any account A_i where $r_i \le e_j \le d_i$. Note that an event can be paid for by more one account; For example an event of cost $3 can be paid by $1 from one account and $2 from another account. Obviously, the account A_i can not contribute more than a_i dollars towards paying for events. The problem is to determine which costs should be charged to which accounts. The goal is to find an algorithm that will find a feasible method of paying for the costs of the events, if it is possible to do so.

We consider greedy algorithms for this problem that pay for the events by non-decreasing order of date. For simplicity assume that the events are ordered by date, that is, $e_1 \le e_2 \le \ldots \le e_m$. So our greedy algorithms first determine how to pay for event E₁, then determine how to pay for event E₂, then determine how to pay for event E₃, etc. Note that we are often forced to use such a greedy algorithm in practice because we are not aware of events until they happen. The algorithms differ in how they pick the accounts to pay for the current event. Consider the following two algorithms, Early and Level:

Early

Assume that events $E_1, \ldots, E_{j-1}$ have been paid for, and we now wish to pay for event E_j.

• While E_j has not been fully paid for:
  • Among the accounts that are open at time e_j and that have not yet been fully depleted, let A_i be an account with the earliest end date.
  • Deduct from A_i the smaller of the remaining unpaid portion of the event, and the amount of money left in the account.

The intuition of Early is that you should pay from the account that will expire soonest.

Level

Assume that events $E_1, \ldots, E_{j-1}$ have been paid for, and we now wish to pay for event E_j. Partition the cost of E_j among the open accounts in such a way that the amount of money remaining, in the open account with the most money remaining, is as small as possible.

• If you need to know, this can be accomplished in the following manner (although how this is accomplish is not really germane to the correctness issue at hand): The open account with the largest balance pays for part of E_j until the balance in this biggest open account is equal to the balance in the second biggest open account; Then these two open accounts pay for the remaining portion of cost equally until their balances equals the balance in the third biggest open account; Then these three open accounts pay for the remaining portion of cost equally until $\ldots$.

The intuition of Level is that you should not deplete any account unless it is necessary to do so.

As an example of the algorithms assume that we have two events E₁ and E₂, with e₁ = 5 and e₂=7, and with c₁=60 and c₂=50. So event E₁ can only charged to accounts A_i satisfying $r_i \le 5 \le d_i$, and event E₂ can only charged to accounts A_i satisfying $r_i \le 7 \le d_i$. Assume that accounts A₇ and A₉ have the property that r₇ < r₉ < e₁ = 5 < e₂ = 7 < d₇ < d₉, so accounts A₇ and A₉ can pay for events E₁ and E₂. Assume all other accounts A_i either have d_i < 5 or r_i>7, so they are not eligible to pay for either event E₁ or event E₂. Assume that the initial balance in A₇ is a₇=$100, and that the initial balance in A₉ is a₉=$80.

First Early will charge all of the cost of $60 for E₁ to A₇ since d₇ < d₉. Then Early will charge the first $40 for E₂ to A₇ since d₇ < d₉. But at that time A₇ will be depleted, and then Early will charge the last $10 of the cost of E₂ to A₉.

First Level will charge $40 of the cost of E₁ to A₇ and $20 of the cost of E₁ to A₉, leaving both account balances at $60. The $50 cost of E₂ will be split evenly by A₇ and A₉, that is, each of these account pays $25, leaving the account balance of each account at $35.

For each of the algorithms Early and Level, prove or disprove that the algorithm correctly solves this problem

2.

(20 points) Consider the following problem. You have a collection of food items $F_1, \ldots, F_n$. Each food item F_i has a positive integer nutritional value v_i and a positive integer caloric value c_i. You have a caloric limit of C. The goal is to find a subset S of the food items (note that you only have 1 item of each food) that maximizes the total nutritional value of the foods. That is, you want

$$\sum_{F_i \in S} c_i \le L$$

and the sum

$$\sum_{F_i \in S} v_i$$

to be as large as possible. Give an O(nL) algorithm to find S.

Note that for full credit you need to actually find S in time O(nL). You can get significant partial credit for finding the maximal value of the sum

$$\sum_{F_i \in S} v_i$$

in time bounded by a polynomial in n+L.

3.

(20 points) Give a polynomial time algorithm for the following problem. The input to this problem consists of an ordered list of n words. The length of the ith word is w_i, that is the ith word takes up w_i spaces. (For simplicity assume that there are no spaces between words.) The goal is to break this ordered list of words into lines, this is called a layout. Note that you can not reorder the words. The length of a line is the sum of the lengths of the words on that line. The ideal line length is L. No line may be longer than L, although it may be shorter. The penalty for having a line of length K is L-K. The total penalty is the maximum of the line penalties. The problem is to find a layout that minimizes the total penalty.

4.

(20 points) Give a polynomial time algorithm for the following problem. The input consists of a sequence $R = R_0, \ldots, R_n$ of non-negative integers, and an integer k. The number R_i represents the number of users requesting some particular piece of information at time i ( say from a www server. If the server broadcasts this information at some time t, the the requests of all the users who requested the information strictly before time t are satisfied. The server can broadcast this information at most k times. The goal is to pick the k times to broadcast in order to minimize the total time (over all requests) that requests/users have to wait in order to have their requests satisfied.

As an example, assume that the input was R = 3, 4, 0, 5, 2, 7 (so n=6) and k=3. Then one possible solution (there is no claim that this is the optimal solution) would be to broadcast at times 2, 4, and 7 (note that it is obvious that in every optimal schedule that there is a broadcast at time n+1 if $R_n \ne 0$). The 3 requests at time 1 would then have to wait 1 time unit. The 4 requests at time 2 would then have to wait 2 time units. The 5 requests at time 4 would then have to wait 3 time units. The 2 requests at time 5 would then have to wait 2 time units. The 7 requests at time 6 would then have to wait 1 time units. Thus the total waiting time for this solution would be

3 * 1 + 4 * 2 + 5*3 +2*2 + 7*1