28.5 Exercises

Factual

1. Which of the following statements about reductions are true?

   • DAG-LPT reduces to DAG-SPT.

   • 3SAT reduces to Independent Set.

   • Percolation on an NxN grid reduces to Disjoint Sets on an NxN grid.

   • Disjoint Sets on an NxN grid reduces to Percolation on an NxN grid.

Problem 1

• DAG-LPT reduces to DAG-SPT.

• 3SAT reduces to Independent Set.

• Percolation on an NxN grid reduces to Disjoint Sets on an NxN grid.

• Disjoint Sets on an NxN grid reduces to Percolation on an NxN grid.

Procedural

1. What ordering of vertices do we get if we use the topological sort algorithm from lecture on the graph below? Assume that all ties are broken in numerical order. For example, if there are multiple vertices with in-degree zero, use the smallest first. For example, if a node has multiple outgoing edges, use the smallest first.

1. Now suppose we add weights to the edges. If we use Dijkstra's algorithm to find the SPT from 0, what is the second vertex we will visit? That is, after visiting vertex 0, which one comes next?

2. The graph from part 2 is a DAG (i.e. contains no cycles). If we use the DAG Shortest Paths algorithm from lecture, what vertex will be visited after vertex 0?

3. According to the DAG Shortest Paths algorithm from lecture, the first vertex we should visit is vertex 6. After relaxing the edge from 6 to 1, what is distTo[1]? Assume 0 is the start vertex.

4. How many edges are in the longest paths tree for the graph above if we start from vertex 0?

Problem 1

The DFS Post Order is 3 2 4 5 1 0 6. The reverse of this is 6 0 1 5 4 2 3. Thus, the topological sort we get is 6 0 1 5 4 2 3.

Problem 2

2, it has the shortest distance from the start vertex.

Problem 3

1, because it is the next in the topological order that we got in question 1.

Problem 4

Infinity. Recall that when relaxing the edge from 6 to 1 in a shortest paths algorithm, the new distance to be considered is distTo[6] + w(6, 1) where w(6, 1) is the weight of the edge from 6 to 1. Since distTo[6] is infinity, the sum is infinity + 9. Since this is no better than the original value of distTo[1], which is also infinity, distTo[1] does not change.

Problem 5

1. There are 6 reachable vertex from 0, so the LPT will have V - 1 = 5 edges.