2. A system is computing results for a set of different requests. Each request i
ID: 3589924 • Letter: 2
Question
2. A system is computing results for a set of different requests. Each request is answered by first querying a database, and then processing the query results to produce an answer. The system can process the query results in parallel (with one processor request), but querying the database itself must be done sequentially (one request at a time Consider that we have an entire set of requests, and we can respond to them in any order we wish. We also have, for each request i, the time q, that will be needed to query the database and the time p; that will be needed to process the query results into the answer Processing this set of requests is monopolizing our system, so we would like to complete the entire process as soon as possible (a) Consider a greedy approach that answers the requests in nondecreasing order of total time q pi, with the shortest g + pi first. Give and demonstrate a counterexample to show that this approach does not always find the minimum total time elapsed (b) Design and write a greedy algorithm that, given the times qi and pi needed for each of n requests, will find the minimum time elapsed from the start of the first query until all requests have been answered. (c) Prove that your algorithm always finds an optimum resultExplanation / Answer
a.
Consider the situation where there are two jobs J1 & J2 whose QUery times are 100,20 and process times are 15,180. So according to the algorithm, we need to process Job J1 and then J2(as 115 < 200). So total time here is 115 + 200 = 315.Suppose if we had let J2 run first, then time it will take is 20 , then query is free so we can start J1 to query while J2 will be processing. Essential query time is 20 + 180+15 = 215 which is minimum of time elaspsed.
b.
1. Reorder jobs so that they are in increasing order of finish time.
2. Store starting time of jobs in an array S.
3. Always select first interval. Let finish time be f .
4. Iterate over S to find the first index i such that S[i] f .
c.
Running time is O(n log n), dominated by sorting.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.