60 points] Let U be a set of tasks and E a set of pairs (u,...

Transcribed Image Text:

60 points] Let U be a set of tasks and E a set of pairs (u, v) where u,v E U. An ezecution is any sequence of elements of U without repetitions. An execution need not contain all tasks An execution u,,u is valid if for every i, 1 <isk, at least one of the following two conditions holds: the set U contains no task r such that (r, u) E E, or there is a task uj such that j<i and (uj, u) E E (a) Suppose U{a, b, c and E {(a, b), (c, b). Which of the following sequences are valid executions? i. а; ii. а, b; ii. а, b, с; iv. a, c, b (b) The length of an execution u,..,u is the number k; we have k < jU. Give a polynomial-time algorithm for the following problem: given sets U, E, and a task uE U, what is the minimum length of a valid execution that contains u? Justify the correctness of your algorithm and analyze its worst-case running time. As always, your algorithm should be as efficient (asymptotically) as possible. 60 points] Let U be a set of tasks and E a set of pairs (u, v) where u,v E U. An ezecution is any sequence of elements of U without repetitions. An execution need not contain all tasks An execution u,,u is valid if for every i, 1 <isk, at least one of the following two conditions holds: the set U contains no task r such that (r, u) E E, or there is a task uj such that j<i and (uj, u) E E (a) Suppose U{a, b, c and E {(a, b), (c, b). Which of the following sequences are valid executions? i. а; ii. а, b; ii. а, b, с; iv. a, c, b (b) The length of an execution u,..,u is the number k; we have k < jU. Give a polynomial-time algorithm for the following problem: given sets U, E, and a task uE U, what is the minimum length of a valid execution that contains u? Justify the correctness of your algorithm and analyze its worst-case running time. As always, your algorithm should be as efficient (asymptotically) as possible.

Answer rating: 100% (QA)

a i This is a valid sequence since there ... View the full answer