Reading Assignment: Kleinberg and Tardos, chapters 2 and 3.

Problems

1. Kleinberg and Tardos, page 52, problem 2.
2. Consider depth-first-search on a directed graph G=(V,E), starting from node s. Let T = (V_T, E_T) be the resulting depth-first-search tree.

   1. Characterize the set of nodes in V_T.
   2. The edges visited during the depth-first search can be categorized into four categories:

      • tree edges: edges in E_T;
      • forward edges: edges from a node in V_T to a descendent (that is not a child) in V_T;
      • back edges: edges from a node in V_T to an ancestor in V_T;
      • cross edges: edges between nodes in V_T that are unrelated in T.
      Write pseudo-code for DFS(s) that prints out for each edge visited whether or not it is a tree edge, a forward edge, a back edge or a cross edge.
3. Find a necessary and sufficient condition for a directed acyclic graph to have a unique topological order.
4. Extra Credit: Kleinberg and Tardos, page 52, problem 3
5. Extra Credit: Feedback on chapter 2 in book. Please submit this by email to both Erik and Anna.