Directions
For problems that say "give an algorithm", give both a high-level description and an explanation of why your algorithm is correct.
1. Chapter 3, Page 107, Problem 1 [10 points]
2. Chapter 3, Page 107, Problem 3 [25 points]
3. Chapter 3, Page 107, Problem 4 [25 points]
4. Chapter 3, Page 108, Problem 6 (G is undirected) [20 points]
5. Chapter 3, Page 108, Problem 7 [20 points]
1. Concrete Application (2 points)
Give a real world example for one of the graph algorithms discussed in class. This can include use of BFS to find shortest paths, testing bipartiteness, testing for a DAG, etc. Again, you may not use examples discussed in class. Your solution must give a description of the real world problem, an explanation of how the real world objects can be represented in a graph, and finally how the graph solution (eg., shortest path, topological order, etc.) relate to the real world problem.