Quiz on Exan Home Insert Design Layout References Mailings Review View Paste 2.
ID: 3906801 • Letter: Q
Question
Quiz on Exan Home Insert Design Layout References Mailings Review View Paste 2. Answer the three questions about the activity selection Algorithm selectActivityl a ls. fl i1,2,..,m) # si start time, and f: finish time of the ith activity 1. Sort a, in increasing order of f, and put them in the ordered set $ # "ordered set" is a set with the placement order. The first one is ai 2. calc 3, while S Find the first activity a E S, or the one with a. b. calc+calcu (a) c. Delete from S all the activities with time conflict with a (1) 4. return calc (a) (Spts) What does the algorithm compute? write answer here (b) (8pts) Fill in the blank (1) with justification in 1-7 lines answer: justification (7pts) Find its asymptotic running time of its best implementation. Justify your answer in 1-7 lines answer: justification write answer here ? (c) write answer here Page 1 of 1 455 Words English (US)Explanation / Answer
1 - Or one with the lowest duration (fi-si)
a) It computes the order of selctiing the activities
b) It computes the selection order so that maximum number of activities get
cobered in a given amount of time.
c) The runing time will be only for the sorting activities after that the selction
of activities will be in that order. So the compexity of the alogorithm will be
sorting complexity (may be O(log(n) with good sorting method).After that it
is O(1).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.