2. A system is computing results for a set of different requests. Each request is answered...

   

Transcribed Image Text:

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 per 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 qi + Pi, with the shortest q + pi first. Give and demonstrate a counterexample to show that this approach does not always find the minimum total time elapsed. (b) Prove that answering the requests in nonincreasing order of p; (largest processing time first) always produces an optimum result. 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 per 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 qi + Pi, with the shortest q + pi first. Give and demonstrate a counterexample to show that this approach does not always find the minimum total time elapsed. (b) Prove that answering the requests in nonincreasing order of p; (largest processing time first) always produces an optimum result.

Answer rating: 100% (QA)

a Counterexample for Greedy Approach Consider three requests with the following parameters Request A ... View the full answer