CS61B
Lecture 28: Decomposition and Reductions
¡ñ Topological Sorting
¡ñ Shortest Paths on DAGs
¡ñ Longest Paths
¡ñ Reductions
datastructur.es
Our Many Achievements
We¡¯ve covered a tremendous amount of material so far.
¡ñ Programming practice: Java, IntelliJ, JUnit, correctness and timing tests, designing your own data structures that compose other data structures together.
¡ñ Asymptotic analysis.
¡ñ Tons of different abstract data types and their implementations, e.g. BST to
implement a map, heaps to implement a PQ.
¡ñ Algorithms on graphs, e.g. shortest paths, minimum spanning trees, etc.
datastructur.es
What is the Point of All of This?
A question worth pondering: Why this specific body of knowledge?
¡ñ Why is everyone pursuing it?
¡ñ Why do companies want to pursue people who have it?
Any thoughts?
¡ñ Efficient algorithms can improve performance of code, solve problems that are otherwise intractable.
¡ð These problems are real world problems.
¡ñ Shows an understanding of how computers work. Shibboleth of
understanding of computing.
¡ñ For fun.
¡ñ Provides a common platform for interviewing for technical knowledge.
¡ð You now have a huge toolset you can use to solve problems.
¡ñ I really think we¡¯re changing the way you think.
datastructur.es
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.
datastructur.es
Graph Problems So Far
Problem
Problem Description
Solution
Efficiency
paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
shortest paths
Find the shortest path from s to every reachable vertex.
BreadthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
shortest weighted paths
Find the shortest path, considering weights, from s to every reachable vertex.
DijkstrasSP.java
Demo
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.
Demo
Time depends on heuristic. ¦¨(V) space
datastructur.es
Graph Problems So Far
Problem
Problem Description
Solution
Efficiency
minimum spanning tree
Find a minimum spanning tree.
LazyPrimMST.java
Demo
O(???) time ¦¨(???) space
minimum spanning tree
Find a minimum spanning tree.
PrimMST.java
Demo
O(E log V) time ¦¨(V) space
minimum spanning tree
Find a minimum spanning tree.
KruskalMST.java
Demo
O(E log E) time ¦¨(E) space
datastructur.es
Topological Sorting
datastructur.es
Topological Sort
2
03
4
7
5
6
1
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
¡ñ What algorithm do we use to find a valid ordering for these tasks?
¡ñ Valid orderings include: [0, 2, 1, 3, 5, 4, 7, 6], [2, 0, 3, 5, 1, 4, 6, 7], …
Any suggestions on where we¡¯d start?
datastructur.es
Topological Sort
2
03
4
7
Start at 2:
¡ñ
Go as far as you can get (DFS).
¡ð 2, 3, 4, 7, 5, 6
5
1
6
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
¡ñ What algorithm do we use to find a valid ordering for these tasks?
¡ñ Valid orderings include: [0, 2, 1, 3, 5, 4, 7, 6], [2, 0, 3, 5, 1, 4, 6, 7], …
Any suggestions on where we¡¯d start?
datastructur.es
Topological Sort
2
03
4
7
5
Multiple breadth first searches from vertices of in-degree 0.
¡ñ Great places to start.
[0/2, 1/3/5, 4/6, 7]
6
8
1
[0/2/8, 1/3/5/7,
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
¡ñ What algorithm do we use to find a valid ordering for these tasks?
¡ñ Valid orderings include: [0, 2, 1, 3, 5, 4, 7, 6], [2, 0, 3, 5, 1, 4, 6, 7], …
Any suggestions on where we¡¯d start?
datastructur.es
Solution (Spoiler Alert)
2
03
4
7
5
6
1
Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.
¡ñ Record DFS postorder in a list.
¡ñ Topological ordering is given by the reverse of that list (reverse postorder).
datastructur.es
Topological Sort (Demo 1/2)
*
1
2222 35353535
46*46*466 *
777
0
Postorder: [] Postorder: [] Postorder: [] Postorder: [7]
2222
55*5*5 303
3
*
6*1666
0
0
0
0
4
1
1
1
7
0
0
3
4
1
4
4
4
1
1
7
7
7
7
Postorder: [7, 4]
Postorder: [7, 4, 1] Postorder: [7, 4, 1] Postorder: [7, 4, 1, 3]
datastructur.es
Topological Sort (Demo 2/2)
2
22 *5*55
666
*
0
3
*
6
Postorder: [7, 4, 1, 3, 0] *
Postorder: [7, 4, 1, 3]
Postorder: [7, 4, 1, 3, 0] Postorder: [7, 4, 1, 3, 0]
*
2
Postorder: [7, 4, 1, 3, 0, 6]
Postorder: [7, 4, 1, 3, 0, 6, 5] Postorder: [7, 4, 1, 3, 0, 6, 5,dat2ast]ructur.es
4
*
0
3
4
2
0
2
3
4
2
3
4
5
0
1
1
1
1
7
7
7
7
5
5
5
0
3
0
3
0
3
4
6
4
6
4
6
1
1
1
7
7
7
Solution (Spoiler Alert)
2
03
4
7
5
6
1
Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.
¡ñ Record DFS postorder in a list: [7, 4, 1, 3, 0, 6, 5, 2]
¡ñ Topological ordering is given by the reverse of that list (reverse postorder):
¡ð [2, 5, 6, 0, 3, 1, 4, 7]
datastructur.es
Topological Sort
4
7
2
0
3
56
1
25603147
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]
¡ñ When nodes are sorted in diagram, arrows all point rightwards.
datastructur.es
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.
datastructur.es
Question
What is the runtime to find all vertices of indegree 0?
¡ñ Interesting thing I did not tell you: You don¡¯t have to.
Another better topological sort algorithm:
¡ñ Run DFS from an arbitrary vertex.
¡ñ If not all marked, pick an unmarked vertex and do it again.
¡ñ Repeat until done.
datastructur.es
Test Your Understanding
Give a topological ordering for the graph below (a.k.a. topological sort).
1
6
1
s
2 05
4
1
2
4
2
1
3
3
datastructur.es
Test Your Understanding
Give a topological ordering for the graph below (a.k.a. topological sort) ¡ñ 0, 3, 1, 2, 4, 5 (because DFS postorder was 542130)
2 05
1
6
1
2
s
4
1
2
1
3
3
4
Recall that we can think of topological sort as an ordering of ¡°tasks¡±.
5
3
0
2
3
4
1
6
2
1
4
1
s
2
1
datastructur.es
Directed Acyclic Graphs
A topological sort only exists if the graph is a directed acyclic graph (DAG).
¡ñ For the graph below, there is NO possible ordering where all arrows are respected.
2
03
4
7
1
5
6
DAGs appear in many real world applications, and there are many graph algorithms that only work on DAGs.
datastructur.es
Graph Problems
Problem
Problem Description
Solution
Efficiency
topological sort
Find an ordering of vertices that respects edges of our DAG.
Demo
Topological.java
O(V+E) time ¦¨(V) space
datastructur.es
Shortest Paths on DAGs
datastructur.es
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?
2 05
4
1
6
1
2
s
4
1
2
1
3
3
Graph from Algorithms, by Vazirani/Papadimitriou
datastructur.es
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?
¡ñ 0, 1, 3, 4, 5, 2
17
2 05
4
25
1
6
1
2
s
6
4
1
2
1
3
3
datastructur.es
Shortest Paths Warmup
If we allow negative edges, Dijkstra¡¯s algorithm can fail.
¡ñ For example, below we see Dijkstra¡¯s just before vertex 2 is visited.
17
2
1
1
6
1
s
3
0
25
-20
5
1
1
3
1
4
12
datastructur.es
Shortest Paths Warmup
If we allow negative edges, Dijkstra¡¯s algorithm can fail.
¡ñ For example, below we see Dijkstra¡¯s just before vertex 2 is visited.
¡ñ Relaxation on 4 succeeds, but distance to 5 will never be updated. 17
1
1
6
2
1
s
3
0
25
-20
5
1
1
3
1
4
12
-13
datastructur.es
Shortest Paths Warmup
If we allow negative edges, Dijkstra¡¯s algorithm can fail.
¡ñ For example, below we see Dijkstra¡¯s just before vertex 2 is visited.
¡ñ Relaxation on 4 succeeds, but distance to 5 will never be updated. 17
1
6
2
1
1
s
distTo is wrong!
3
0
25
-20
5
1
1
3
1
4
1 -13
datastructur.es
Challenge
Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.
¡ñ Hint: You should still use the ¡°relax¡± operation as a basic building block. ¡Þ¡Þ
2 05
4
¡Þ¡Þ
1
6
1
s
¡Þ
-20
1
25
1
1
3
1
datastructur.es
Challenge
Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.
¡ñ Hint: You should still use the ¡°relax¡± operation as a basic building block. ¡Þ¡Þ
2 05
4
¡Þ¡Þ
One simple idea: Visit vertices in topological order.
¡ñ On each visit, relax all outgoing edges.
¡ñ Each vertex is visited only when all possible info about it has been used!
1
6
1
1
s
¡Þ
25
-20
1
1
3
1
datastructur.es
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
6
2 05
1
1
s
¡Þ
25
-20
1
4
¡Þ¡Þ
3
1
1
1
0
1
3
1
1
6
2
-20
4
1
s
5
1
1
datastructur.es
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
0
1
3
1
1
6
2
-20
4
1
s
5
1
1
datastructur.es
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].
¡ñ Runtime for step 2 is also O(V + E).
Quick note: In office hours, someone asked, why isn¡¯t it O(V*E), since we¡¯re
relaxing all edges from each vertex.
¡ñ Keep in mind that E is the TOTAL number of edges in the entire graph, not the number of edges per vertex, e.g. for graph below E = 8.
1
0
1
3
1
1
6
2
-20
4
1
s
5
1
1
datastructur.es
Graph Problems
Problem
Problem Description
Solution
Efficiency
topological sort
Find an ordering of vertices that respects edges of our DAG.
Demo
Code: Topological.java
O(V+E) time ¦¨(V) space
DAG shortest paths
Find a shortest paths tree on a DAG.
Demo
Code: AcyclicSP.java
O(V+E) time ¦¨(V) space
Note: The DAG shortest paths solution uses the topological sort solution as a subroutine.
datastructur.es
Longest Paths
datastructur.es
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!).
3
2
1
11
3
2
1
6
5
5
s
4
0
1
1
4
1
2
15
5
datastructur.es
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:
¡ñ Best known algorithm is exponential (extremely bad).
¡ñ Perhaps the most important unsolved problem in
2
1
3
13
15
4
0
2
11
3
2
1
20
6
5
5
mathematics.
s
1
1
7
2 22
5
4
1
15
datastructur.es
The Longest Paths Problem on DAGs
Difficult challenge for you.
¡ñ Solve the LPT problem on a directed acyclic graph.
¡ñ Algorithm must be O(E + V) runtime. 6
12
2
1
6
1
2
s
0 14
05
4
2 13
4
1
2
1
3
3
datastructur.es
The Longest Paths Problem on DAGs
DAG LPT solution for graph G:
¡ñ Form a new copy of the graph G¡¯ with signs of all edge weights flipped.
¡ñ Run DAGSPT on G¡¯ yielding result X.
¡ñ Flip signs of all values in X.distTo. X.edgeTo is already correct.
-1
-12
2 05
4
-2 -13
1
-6
-1
-2
s
0
-14
-4
-1
-2
-1
3
-3
datastructur.es
The Longest Paths Problem on DAGs
DAG LPT solution for graph G:
¡ñ Form a new copy of the graph G¡¯ with signs of all edge weights flipped.
¡ñ Run DAGSPT on G¡¯ yielding result X.
¡ñ Flip signs of all values in X.distTo. X.edgeTo is already correct.
1
12
s
12
0 14
05
34
2 13
datastructur.es
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.
¡ñ We know DAG SPT works on graphs with negative edge weights.
¡ñ We also know that -(-a + -b + -c + -d) = a + b + c + d.
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, …
datastructur.es
Highly Recommended Exercise For Later
Play around with the longest paths problem and convince yourself that it is actually very hard.
¡ñ Try to develop an intuition for why it is hard. Even better if you try to put it into english.
¡ñ Try searching the internet for ¡°why longest paths hard¡± or similar if you¡¯re having trouble really pinning down what¡¯s so hard about it.
datastructur.es
Graph Problems
Problem
Problem Description
Solution
Efficiency
topological sort
Find an ordering of vertices that respects edges of our DAG.
Demo
Code: Topological.java
O(V+E) time ¦¨(V) space
DAG shortest paths
Find a shortest paths tree on a DAG.
Demo
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
datastructur.es
Reduction (170 Preview)
datastructur.es
DAG Longest Paths
The problem solving we just used probably felt a little different than usual:
¡ñ Given a graph G, we created a new graph G¡¯ and fed it to a related (but different) algorithm, and then interpreted the result.
DAG-LPT
G
G¡¯
Preprocess
DAG-SPT
Postprocess
SPT of G¡¯
LPT of G
datastructur.es
Reduction
This process is known as reduction.
¡ñ Since DAG-SPT can be used to solve DAG-LPT, we say that ¡°DAG-LPT reduces
to DAG-SPT¡±.
DAG-LPT
G
G¡¯
Preprocess
DAG-SPT
Postprocess
SPT of G¡¯
LPT of G
datastructur.es
Reduction Analogy
This process is known as reduction.
¡ñ Since DAG-SPT can be used to DAG-LPT, we say that ¡°DAG-LPT reduces to DAG-SPT¡±.
As a real-world analog, suppose we want to climb a hill. There are many ways to do this:
¡ñ ¡°Climbing a hill¡± reduces to ¡°riding a ski lift.¡±
¡ñ ¡°Climbing a hill¡± reduces to ¡°being shot out of a cannon.¡±
¡ñ ¡°Climbing a hill¡± reduces to ¡°riding a bike up the hill.¡±
datastructur.es
Reduction Definition (Informal)
This process is known as reduction.
¡ñ Since DAG-SPT can be used to DAG-LPT, we say that ¡°DAG-LPT reduces to DAG-SPT¡±.
Algorithms by Dasgupta, Papadimitriou, and Vazirani defines a reduction informally as follows:
¡ñ ¡°If any subroutine for task Q can be used to solve P, we say P reduces to Q.¡±
Can also define the idea formally, but way beyond the scope of our class. ¡ñ If you¡¯re curious, you can read more about Karp and Cook reductions.
datastructur.es
Reduction is More Than Sign Flipping
Let¡¯s see a richer example of a reduction.
datastructur.es
The Independent Set Problem
An independent set is a set of vertices in which no two vertices are adjacent. The Independent-set Problem:
¡ñ Does there exist an independent set of size k?
¡ñ i.e. color k vertices red, such that none touch.
Example for the graph on the right and k = 9
¡ñ For this particular graph, N=24.
datastructur.es
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) ¡ñ Solution: x1 = true, x2 = true, x3 = true, x4 = false
datastructur.es
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:
¡ñ For each clause in ¦Õ, create 3 vertices in a triangle.
¡ñ Add an edge between each literal and its negation (can¡¯t both be true in
3SAT means can¡¯t be in same set in Independent-set)
k = number of variables = 4
! x1 x1
x3 x4 x3 x4
x1
! x1
x2
! x2
! x4
x3
¦µ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
datastructur.es
3SAT Reduces to Independent Set
Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.
¡ñ Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.
k = number of variables = 4
! x1 x1
x3 x4 x3 x4
¦µ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
x1
! x1
x2
! x2
! x4
x3
datastructur.es
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.
¡ñ Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.
k = number of variables = 4
x1
! x1
! x1
x1
x2
x3 x3x4
! x2
x4
! x4
x3
¦µ =
(x1 or x2 or x3) and
X3: True
X2: False
X4: True
X1: Doesn¡¯t matter
(! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)
datastructur.es
Reduction
Since IND-SET can be used to solve 3SAT, we say that ¡°3SAT reduces to IND-SET¡±. ¡ñ Note: 3SAT is not a graph problem!
¡ñ Note: Reductions don¡¯t always involve creating graphs. 3SAT
¦µG
Preprocess
IND-SET
Postprocess
Assignment so that ¦µ gives true.
x1: true x2: false x3: false x4: true
IND-SET for G
datastructur.es
Reductions and Decomposition
Arguably, we¡¯ve been doing something like a reduction all throughout the course.
¡ñ Abstract lists reduce to arrays (or linked lists).
¡ñ Synthesizing guitar string sound reduces to ArrayRingBuffer.
¡ñ The percolation problem reduces to DisjointSets.
¡ñ ExtrinsicMinPQ reduces to (operations on whatever instance variables you
used).
These examples aren¡¯t reductions exactly.
¡ñ We aren¡¯t just calling a subroutine.
¡ñ A better term would be decomposition: Taking a complex task and breaking it
into smaller parts. This is the heart of computer science.
¡ð Using appropriate abstractions makes problem solving vastly easier.
datastructur.es
Generational Changes in the Human Mind
datastructur.es