a) we are given a DAG G = (V, E) and two vertices u, v V . We want to figure out the length of the longest u-v-path in G (the length of a path v1, . . . , vk is k 1). Give an O(m + n) algorithm for the problem. Write pseudocode for the algorithm

b)we are given a DAG G = (V, E), two vertices u, v V and a subset S V . We want to figure out whether there exists a u-v-path in G that contains a vertex in S (that is, does there exists a path v1, . . . , vk such that v1 = u, vk = v and {v1, . . . , vk} S 6= ). Give an O(m + n) algorithm for the problem.

c)we are given a directed graph G = (V, E), two vertices u, v V and a positive integer `. We want to figure out whether there exists a u-v-walk of length at least ` (remember, in a walk we allow repeated vertices; the length of a walk v1, . . . , vk is k 1). Give an O(m + n) algorithm for the problem. Clearly describe your algorithm