Due: Monday, Apr 8th in class Late assignments will be penalized 20% per day.

Book Questions from Introduction to Algorithms - 3rd ed.

22.1-1, 22.2-7, 22.4-3, 22.5-2

Give a short 1-2 sentence description of your final project topic along with at least one reference.

Hints:

22.2-7 - Consider the number of edges between a source and all reachable vertices, and use this to separate the vertices into “babyfaces” and “heels”. Note: This is the problem of determining whether or not a graph is bipartite.

22.4-3 - By Lemma 22.11 we know that a DAG is acyclic if and only if a DFS produces no back edges. However DFS runs in O(V+E) but the question wants an O(V) run time. Again note the graphs for this problem are undirected and that for undirected acyclic graphs |E| = |V| - 1 (by Theorem B.2.5 on page 1174).