# 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 * [x] DAG-LPT reduces to DAG-SPT. * [x] 3SAT reduces to Independent Set. * [x] 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. ![](/files/wNEAEV9Nc1eLpoiVE2EH) 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\[1]? 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?
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 5. There are 6 reachable vertex from 0, so the LPT will have V - 1 = 5 edges.
--- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook/28.-reductions-and-decomposition/28.5-exercises.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.