Computers and Technology, 11.12.2019 22:31 Chrien222

Consider the problem of storing n books on shelves in a library. the order of the books is fixed by the cataloging system and so cannot be rearraged. therefore, we can speak of a book bi , where 1 ≤ i ≤ n, that has a thickness ti and height hi . the length of each bookshelf at this library is l. (1) suppose all the books have the same height h (i. e. h = hi = hj for all i, j) and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. the greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that bi does not fit, and then repeat with subsequent shelves. show that the greedy algorithm always finds the optimal shelf placement, and analyze the time complexity. (2) this is a generalization of the previous problem. now consider the case where the height of the books is not constant, but we have the freedom to adjust the height of each shelf to that of the tallest book on the shelf. thus the cost of a particular layout is the sum of the heights of the largest book on each shelf. (a) give an example to show that the greedy algorithm of stuffing each shelf as full as possible does not always give the minimum overall height. (b) what technique should we use to solve this problem? (c) what are the subproblems? (d) how many subproblems are there? (e) give an algorithm for this problem, and analyze its time complexity

Answers: 3

Show answers

Another question on Computers and Technology

Computers and Technology, 22.06.2019 07:30

By refraining from constructing a building until they are certain that it will not cause harm to the environment, an organization is adhering to the

Answers: 2

Answer

Computers and Technology, 22.06.2019 16:50

Consider a slotted aloha system, where the time slot equals the fixed duration of each packet. assume that there are 4 stations a,b,c,d sharing the medium. (a) stations a,b,c,d receive one packet each from higher layers at times 1.3, 1.5, 2.6,5.7 respectively. show which transmissions take place when, according to the slottedaloha protocol; describe all transmissions until all four packets have been successful.when needed, each station has access to the following sequence of random number, provided by a random number generator and drawn uniformly between 0 and 1: (1) station a draws numbers: 0.31, 0.27, 0.78, 0.9, 0.9, 0.11, 0. (2) station b draws numbers: 0.45, 0.28, 0.11, 0.83, 0.37, 0.22, 0. (3)station c draws numbers: 0.1, 0.2, 0.3, 0.4, 0. (4) station d draws numbers: 0.36, 0.77, 0.9, 0.1, 0.1, 0.1, 0.1, 0. (b) in slotted aloha, a station transmits in each time slot with a given probability. what probabilities would you assign to each of the four stations so as to: (i) maximize the efficiency of the protocol? (ii) maximize fairness among the four stations? (c) will the efficiency increase or decrease if we modify slotted aloha as follows: (i) get rid of slots and allow stations to transmit immediately? (ii) implement carrier sensing? (iii) implement collision detection? (iv) implement collision avoidance?

Answers: 3

Answer

Computers and Technology, 22.06.2019 19:30

Avariable definition defines the name of a variable that will be used in a program, as well as

Answers: 3

Answer

Computers and Technology, 22.06.2019 22:40

Least square fit to polynomial write a function leastsquarefit3pol that solves a linear system of equations to find a least squares fit of a third order polynomial to an experimental data set given as two row arrays. the function leastsquarefit3pol must explicitly solve a set of linear equations and cannot use polyfit. there should be no restriction on the size of the problem that can be solved.

Answers: 1

Answer

You know the right answer?

Consider the problem of storing n books on shelves in a library. the order of the books is fixed by...

Questions