A QUESTION BASED ON ALGORITHM ANALYSIS AND DESIGN 8) (1, 2, ., n; the ith reques
ID: 3713165 • Letter: A
Question
A QUESTION BASED ON ALGORITHM ANALYSIS AND DESIGN
8) (1, 2, ., n; the ith request corresponds to an interval of time starting at s@) and finish subset of the requests is said to two of them overlap in time. Compatible requests of maximum size will be called optimal. The resource is to be allocated to the requests in non-preemptive way i.e. once a resorce is allocated to a request that 16. (a) Given a single resource and a set of req ing at f(i). A be compatible, if no recource cannot be taken away from that request unless it finishes. Now, design an algorithm to obtain an schedule of the requests so that the resource can be utilized by the maximum number of requests. You must prove the optimality of your algorithm. 5 (b) There are following two problems L and L : Input : A graph G (V, E). Output : Maximum size of Matching. : Input : A graph G (V, E). Output : Does G have a Perfect Matching? Prove that ?1Spn, and ?2SpL.Explanation / Answer
Solution:
Note: The first question is done as per Chegg guidelines, please repost others.
The algorithm is given below:
Algorithm:
Optimality:
The jobs which have the smallest finishing time will take minimum time to finish the task and just after that we can assign the next job which requires smallest finishing time, this will increase the number of jobs to be finished in the given time.
running time:
We are sorting the array for the finishing time that will take O(n log n) time and schedule the job will take O(n) time
so effective complexity will be
T(n)= O(n log n)
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)