CS61B
Lecture 28: Decomposition and Reductions
Our Many Achievements
We’ve covered a tremendous amount of material so far.
What is the Point of All of This?
A question worth pondering: Why this specific body of knowledge?
Any thoughts?
Goals of Today
Today, to practice our problem solving skills, we’ll work through some very challenging A-level problems using the tools we’ve already learned about.
Will focus on graphs, but the ideas today are more general.
Graph Problems So Far
Problem | Problem Description | Solution | Efficiency |
paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java | O(V+E) time Θ(V) space |
shortest paths | Find the shortest path from s to every reachable vertex. | BreadthFirstPaths.java | O(V+E) time Θ(V) space |
shortest weighted paths | Find the shortest path, considering weights, from s to every reachable vertex. | DijkstrasSP.java | O(E log V) time Θ(V) space |
shortest weighted path | Find the shortest path, consider weights, from s to some target vertex | A*: Same as Dijkstra’s but with h(v, goal) added to priority of each vertex. | Time depends on heuristic. Θ(V) space |
Graph Problems So Far
Problem | Problem Description | Solution | Efficiency |
minimum spanning tree | Find a minimum spanning tree. | LazyPrimMST.java | O(???) time Θ(???) space |
minimum spanning tree | Find a minimum spanning tree. | PrimMST.java | O(E log V) time Θ(V) space |
minimum spanning tree | Find a minimum spanning tree. | KruskalMST.java | O(E log E) time Θ(E) space |
Topological Sorting
Topological Sort
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
Any suggestions on where we’d start?
1
2
3
4
5
6
7
0
Topological Sort
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
Any suggestions on where we’d start?
1
2
3
4
5
6
7
0
Start at 2:
Topological Sort
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
Any suggestions on where we’d start?
1
2
3
4
5
6
7
0
Multiple breadth first searches from vertices of in-degree 0.
[0/2, 1/3/5, 4/6, 7]
[0/2/8, 1/3/5/7,
8
Solution (Spoiler Alert)
Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.
0
1
2
3
4
5
6
7
Topological Sort (Demo 1/2)
0
1
2
3
4
5
6
7
Postorder: []
*
0
1
2
3
4
5
6
7
Postorder: []
*
0
1
2
3
4
5
6
7
Postorder: []
*
0
1
2
3
4
5
6
7
Postorder: [7]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1]
*
0
1
2
3
4
5
6
7
*
Postorder: [7, 4, 1]
0
1
2
3
4
5
6
7
*
Postorder: [7, 4, 1, 3]
Topological Sort (Demo 2/2)
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0]
*
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0, 6]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0, 6, 5]
*
0
1
2
3
4
5
6
7
Postorder: [7, 4, 1, 3, 0, 6, 5, 2]
Solution (Spoiler Alert)
Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.
0
1
2
3
4
5
6
7
Topological Sort
The reason it’s called topological sort: Can think of this process as sorting our nodes so they appear in an order consistent with edges, e.g. [2, 5, 6, 0, 3, 1, 4, 7]
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Depth First Search
Be aware, that when people say “Depth First Search”, they sometimes mean with restarts, and they sometimes mean without.
For example, when we did DepthFirstPaths for reachability, we did not restart.
For Topological Sort, we restarted from every vertex with indegree 0.
Question
What is the runtime to find all vertices of indegree 0?
Another better topological sort algorithm:
Test Your Understanding
Give a topological ordering for the graph below (a.k.a. topological sort).
1
3
2
4
5
0
s
4
1
2
2
6
1
1
3
Test Your Understanding
Give a topological ordering for the graph below (a.k.a. topological sort)
1
3
2
4
5
0
s
4
1
2
2
6
1
1
3
1
3
2
4
5
0
s
4
2
6
1
1
2
3
1
Recall that we can think of topological sort as an ordering of “tasks”.
Directed Acyclic Graphs
A topological sort only exists if the graph is a directed acyclic graph (DAG).
DAGs appear in many real world applications, and there are many graph algorithms that only work on DAGs.
0
1
2
3
4
5
6
7
Graph Problems
Problem | Problem Description | Solution | Efficiency |
topological sort | Find an ordering of vertices that respects edges of our DAG. | Topological.java | O(V+E) time Θ(V) space |
Shortest Paths on DAGs
Shortest Paths Warmup
What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?
1
3
2
4
5
0
s
4
1
2
2
1
1
3
Graph from Algorithms, by Vazirani/Papadimitriou
6
Shortest Paths Warmup
What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?
1
3
2
4
5
0
s
4
1
2
2
1
1
3
1
2
5
7
6
6
Shortest Paths Warmup
If we allow negative edges, Dijkstra’s algorithm can fail.
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
1
1
2
7
3
Shortest Paths Warmup
If we allow negative edges, Dijkstra’s algorithm can fail.
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
1
1
2
7
3
-13
Shortest Paths Warmup
If we allow negative edges, Dijkstra’s algorithm can fail.
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
1
1
7
3
-13
distTo is wrong!
Challenge
Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
∞
∞
∞
∞
∞
Challenge
Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.
One simple idea: Visit vertices in topological order.
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
∞
∞
∞
∞
∞
The DAG SPT Algorithm: Relax in Topological Order
First: We have to find a topological order, e.g. 031245. Runtime is O(V + E).
1
3
2
4
5
0
s
25
1
1
1
6
1
-20
1
∞
∞
∞
∞
∞
1
3
2
4
5
0
s
1
1
6
1
-20
1
1
1
The DAG SPT Algorithm: Relax in Topological Order
Second: We have to visit all the vertices in topological order, relaxing all edges as we go. Let’s see a demo [Link].
1
3
2
4
5
0
s
1
1
6
1
-20
1
1
1
The DAG SPT Algorithm: Relax in Topological Order
Second: We have to visit all the vertices in topological order, relaxing all edges as we go. Let’s see a demo [Link].
Quick note: In office hours, someone asked, why isn’t it O(V*E), since we’re relaxing all edges from each vertex.
1
3
2
4
5
0
s
1
1
6
1
-20
1
1
1
Graph Problems
Note: The DAG shortest paths solution uses the topological sort solution as a subroutine.
Problem | Problem Description | Solution | Efficiency |
topological sort | Find an ordering of vertices that respects edges of our DAG. | Code: Topological.java | O(V+E) time Θ(V) space |
DAG shortest paths | Find a shortest paths tree on a DAG. | Code: AcyclicSP.java | O(V+E) time Θ(V) space |
Longest Paths
The Longest Paths Problem
Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).
1
2
3
4
5
6
0
s
5
2
1
15
3
2
11
5
1
1
4
1
The Longest Paths Problem
Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).
Some surprising facts:
1
2
3
4
5
6
0
s
5
2
1
15
3
2
11
5
1
1
4
1
2
13
7
15
22
20
The Longest Paths Problem on DAGs
Difficult challenge for you.
1
3
2
4
5
0
s
4
1
2
2
6
1
1
3
6
2
12
14
13
0
The Longest Paths Problem on DAGs
DAG LPT solution for graph G:
1
3
2
4
5
0
s
-4
-1
-2
-2
-6
-1
-1
-3
-1
-2
-12
-14
-13
0
The Longest Paths Problem on DAGs
DAG LPT solution for graph G:
1
3
2
4
5
0
s
1
2
12
14
13
0
A Note on “Mathematical Maturity”
If you have a very high degree of so-called “mathematical maturity”, this algorithm should seem plainly correct.
There’s no real need to prove anything or show demos.
Part of what you’re learning in your intense technical education here at Berkeley is mathematical maturity. Hasn’t been a major focus in 61B, but will be in other courses like 16A, 16B, 70, 170, ...
Highly Recommended Exercise For Later
Play around with the longest paths problem and convince yourself that it is actually very hard.
Graph Problems
Problem | Problem Description | Solution | Efficiency |
topological sort | Find an ordering of vertices that respects edges of our DAG. | Code: Topological.java | O(V+E) time Θ(V) space |
DAG shortest paths | Find a shortest paths tree on a DAG. | Code: AcyclicSP.java | O(V+E) time Θ(V) space |
longest paths | Find a longest paths tree on a graph. | No known efficient solution. | O(???) time O(???) space |
DAG longest paths | Find a longest paths tree on a DAG. | Flip signs, run DAG SPT, flip signs again. | O(V+E) time Θ(V) space |
Reduction (170 Preview)
DAG Longest Paths
The problem solving we just used probably felt a little different than usual:
G
DAG-LPT
Preprocess
DAG-SPT
G’
SPT of G’
Postprocess
LPT of G
Reduction
This process is known as reduction.
G
DAG-LPT
Preprocess
DAG-SPT
G’
SPT of G’
Postprocess
LPT of G
Reduction Analogy
This process is known as reduction.
As a real-world analog, suppose we want to climb a hill. There are many ways to do this:
Reduction Definition (Informal)
This process is known as reduction.
Algorithms by Dasgupta, Papadimitriou, and Vazirani defines a reduction informally as follows:
Can also define the idea formally, but way beyond the scope of our class.
Reduction is More Than Sign Flipping
Let’s see a richer example of a reduction.
The Independent Set Problem
An independent set is a set of vertices in which no two vertices are adjacent.
The Independent-set Problem:
Example for the graph on the right and k = 9
The 3SAT Problem
3SAT: Given a boolean formula, does there exist a truth value for boolean variables that obeys a set of 3-variable disjunctive constraints?
3 variable disjunctive constraint�
Example: (x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)
3SAT Reduces to Independent Set
Proposition: 3SAT reduces to Independent-set.
Proof. Given an instance ϕ of 3-SAT, create an instance G of Independent-set:
Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
x2
x1
x3
! x2
x4
! x1
! x4
x3
! x1
x3
x1
x4
k = number of variables = 4
3SAT Reduces to Independent Set
Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.
Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
x2
x1
x3
! x2
x4
! x1
! x4
x3
! x1
x3
x1
x4
k = number of variables = 4
3SAT Reduces to Independent Set (Your Answer)
Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.
Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
x2
x1
x3
! x2
x4
! x1
! x4
x3
! x1
x3
x1
x4
k = number of variables = 4
X3: True
X2: False
X4: True
X1: Doesn’t matter
Reduction
Since IND-SET can be used to solve 3SAT, we say that “3SAT reduces to IND-SET”.
3SAT
Preprocess
IND-SET
G
IND-SET for G
Postprocess
Assignment so
that Φ gives true.
Φ
x1: true
x2: false
x3: false
x4: true
Reductions and Decomposition
Arguably, we’ve been doing something like a reduction all throughout the course.
These examples aren’t reductions exactly.
Generational Changes in the Human Mind