Let G be a directed acyclic graph with a unique source s and a unique sink t$.$

$($a$)$ Describe and analyze an algorithm to compute the number of directed paths from

s to t in G$.$

$($b$)$ A Hamiltonian path in G is a directed path in G that contains every vertex in G$.$

Describe and analyze an algorithm to determine whether G has a Hamiltonian path.

$($c$)$ Describe and analyze an efficient algorithm to find the maximum$-$weight directed

path from s to t that contains at most $$ edges if exists for a positive integer $$ given

as an input.

$($d$)$ Suppose that some of the vertices of G are marked as important. Describe and

analyze an efficient algorithm to find the maximum$-$weight directed path from s to

t that contains at most k important vertices if exists for a positive integer k given

as an input.