Answer a and b:

Problem 2. Suppose you have n video streams that need to be sent, one after another, over a communi cation link. Stream i consists of a total of bi bits that need to be sent, at a constant rate, over a period of ti seconds. (Thus, the rate for sending stream i is bi/ti) You cannot send two streams at the same time, so you need to determine a schedule for the streams: an order in which to send them. Whichever order you choose, there cannot be any delays between the end of one stream and the start of the next. Suppose your schedule starts at time 0 (and therefore ends at time _ti, whichever order you choose). We assume that all the values bi and ti are positive integers. Now, because you're just one user, the link does not want you taking up too much bandwidth, so it imposes the following constraint, using a fixed parameter r: (*) For each natural number t >0, the total number of bits you send over the time interval from 0 to t cannot exceed rt Note that this constraint is only imposed for time intervals that start at 0, not for ime intervals that start at any other value. This scheme is a variation of the so-called leaky bucket algorithm for rate limiting or traffic shaping in networking.) We say that a schedule is valid if it satisfies the constraint (*) imposed by the link. The problem. Given a set of n streams, each specified by its number of bits bi and its time duration ti, as well as the link parameter r, determine whether there exists a valid schedule Example. Suppose we have n = 3 streams, with (by,t1)= (2000, 1), (b2,t2)=(6000. 2), (b3,ts)= (2000, 1). and suppose the link's parameter is r = 5000, Then the schedule that runs the streams in the order 1, 2, 3 is valid, since the constraint) is satisfied: . at t = 1: the whole first stream has been sent, and 2000