CSE347T Practice Problems代写
Some Practice Problems for the last Exam
Practice Problems代写 Problem P3-1. Ivan is Director of Air Traffic Control for the nation of Borogravia, which has a network of increasingly…
Problem P3-1. Ivan is Director of Air Traffic Control for the nation of Borogravia, which has a network of increasingly busy airports. Every so often, Borogravia’s Ministry of Transportation announces a new daily direct flight between some pair of airports. For each new flight, say between airports A and B , Ivan must assign a fixed cruising altitude of k kilometers for some integer k > 0. For safety, no two flights that touch the same airport can use the same altitude; for example, if there is one flight connecting A and B and another connecting A and C, these two flights must use different altitudes k = kl Practice Problems代写
Ivan wants to minimize the maximum assigned altitude over all flights, since there is a limit to how high Borogravia’s planes can fly! He uses the following simple online algorithm: if a new flight connects airports A and B, assign it the lowest altitude not already in use by some flight touching either A or B.
Let Ft be the set of flights established at or before time t. Show that Ivan’s algorithm assigns the flights of Ft a maximum altitude strictly less than twice than the optimum. Practice Problems代写
Hint: your argument should make use of the value m, the largest number of flights that touch any single airport at time t. Practice Problems代写
Problem P3-2. You have a quality control job where you get n items and you want to choose exactly k items for testing. The items must be chosen uniformly at random. In particular, if n < k, you must test all of them. If k > n, then you should test each with probabiity exactly k/n.
However, you do not have all items in advance. Items pass by your station and you can either take them off the assembly line for testing. Or you can leave them on the assembly line. Once an item passes you by, you can’t get it back. You have space to store only k items — so at any time, you can not keep more than k items at your station. In addition, you do not know n in advance. In particular, here is the problem — when an item passes by you can choose to take it off the line. If you already have k previous items, you have to put one of the items you had previously chosen back on the line. At the end of the day, if you saw n items, your pile of k items should have each with probability exactly k/n.
Design an online algorithm which keeps exactly k items (as long as you see at least k items) such that every item you have seen has exactly k/n probability of the items you have. Practice Problems代写
Hint: The algorithm and analysis is similar to Rand MRU for the pessimal cache problem. Practice Problems代写
Problem P3-3. You are a broker assigning graphic design work to a group of m freelance artists. Clients submit jobs in an online fashion, with job j paying a value of cj dollars. As each job comes in, you must immediately assign it to an artist. A job cannot be split between artists and cannot be moved once assigned. Practice Problems代写
Your goal at the end of the day is a fair division of work — each artist should earn about the same total value from their jobs. In other words, if Ci is the total value of all jobs assigned to artist i, you want to minimize maxim=1 Ci .
Consider the following greedy algorithm for this problem. When job j arrives, assign it to the artist whose total value for all work assigned so far is minimum. Practice Problems代写
Show that this algorithm achieves a competitive ratio better than 2 for any number of artists m.
To get started, ponder the following question. Let i be the artist whose assigned work has the greatest total value, and let v be this value. Suppose the last job assigned to this artist had value c. How can you bound the total value of work assigned to each other artist in terms of c and v? How does the total value of work assigned to all artists relate to the value of an optimal solution?
