*Due Wednesday, January 29 at 5:00 PM. Please refer to the homework policy here.*

- A graph is bipartite if the vertices can be partitioned into two subsets and , such that every edge has one vertex in and the other in . Describe and analyze an efficient algorithm that determines whether a given unidrected graph is bipartite.
- Suppose we are given a directed acyclic graph with a unique source and a unique sink . A vertex is called an
*-cut vertex*if every path from to passes through , or equivalently, if deleting makes unreachable from . Describe and analyze an algorithm to find every -cut vertex in .