Affect the running time of an algorithm

Reference no: EM1318396

To check whether the representation of input elements does not affect the running time of an algorithm.

Suppose you have n video streams that need to be sent, one after another, over a communication link. Stream I consists of a total of b_i bits that need to be sent, at a constant rate, over a period of t_i seconds. 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 you schedule starts at time 0(and therefore ends at time ∑ⁿ_i=0t_{i ,}whichever order you chose).we assume that all the values b_iand t_iare positive integers.

Now, because you are 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 time intervals that start at any other value.

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 b_iand its time durationt_{i ,}as well as the link parameter r, determine whether there exist a valid schedule.

Example: suppose we have n=3 streams, with

(b₁, t₁)=(2000,1) (b₂, t₂)=(6000,2) (b₃, t₃)=(2000,1)

and suppose the link's parameter is r=5000.then the schedule that n runs the streams in the order 1,2,3 is valid, since the constant (*) is satisfied:

t=1; the whole first stream has been sent, and 2000<5000

t=2 ; half of the second stream has also been sent.

and 2000+3000 <5000

Similar calculations hold for t=3 and t=4

Give an algorithm that takes a set of n streams, each specified by its number of bits b_iand its time duration t_i, as well as the link parameter r, and determine whether e there exists a valid schedule .the running time of you algorithm should be polynomial in n.

Reference no: EM1318396

Questions Cloud

Finding tc with confidence level and sample size : Find the t c for a 90% confidence level with a sample size of 18.

Propose three ways of mentor and new employee : Propose three ways that a mentor and a new employee orientation can assist employees with their career development.

Find the value of x at which the minimum or maximum occurs : Find the value of X at which the minimum or maximum occurs.

Estimating the mean length of time : A physician wanted to estimate the mean length of time µ that a patient had to wait to see him after arriving at the office.

Affect the running time of an algorithm : To check whether the representation of input elements does not affect the running time of an algorithm

Determine the elements of valid contract : Describe the elements of valid contract, and critically discuss how consumers and banks each have a duty of good faith and fair dealing in banking relationship.

Important results over real valued functions : Verifying some important results over real valued functions - real-valued functions

Computing critical value and null hypothesis : What is the null hypothesis? Use α =0.05. Compute critical value. Use α =0.05.

Listing the significant investigative approaches : What do you think are the most significant investigative approaches in preparation for these cyber crime cases and what could be the result of the poor investigator planning and preparation before start of the digital evidence collection, and proc..

User Account

All Pages