1. Let G = (V,E) be a weighted acyclic directed graph with possibly negative edge weights. Design a linear-time algorithm to solve the single-source shortest-path problem from a given source v
2. A matching in a graph is a set of disjoint edges-i.e., edges that do not share any vertices in common. Give a linear-time algorithm to find a maximum matching in a tree.