Comment on page
- 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.
- 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.
- 2.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?
- 3.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?
- 4.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? Assume 0 is the start vertex.
- 5.How many edges are in the longest paths tree for the graph above if we start from vertex 0?
Infinity. Recall that when relaxing the edge from
1in a shortest paths algorithm, the new distance to be considered is
distTo + w(6, 1)where
w(6, 1)is the weight of the edge from
distTois infinity, the sum is
infinity + 9. Since this is no better than the original value of
distTo, which is also infinity,
distTodoes not change.