Reductions and Decomposition
Software engineering as one facet of problem decomposition; complexity theory and reductions as another facet.
1
Kevin Lin, with thanks to many others.
Feedback from the Reading Quiz
Reduction. Using an algorithm for Problem Q to solve Problem P.
P ≤ Q in terms of difficulty since we can use the algorithm for Q.
Informally*…
2-d nearest neighbor search (NNS) problem. Given an (x, y) pair, find the nearest point.
NNS “reduces” to linear search, so NNS ≤ linear search in terms of difficulty.
But we can improve algorithm efficiency.
KdTreePointSet. Randomized k-d tree is logarithmic height.
* Confusing algorithms and their problems, not actually a “reduction.”
How to solve hard problems we have not seen before?
2
Arbitrary Challenging Problem of the Day
Suppose we have a 2 dimensional space from 0 to MAX_X and 0 to MAX_Y.
e.g. MAX_X = 100, MAX_Y = 100.
3
100
100
Arbitrary Challenging Problem of the Day
Find all labels that overlap the query.
findAnswer(20, 90, 40, 60)
[“AA”, “AB”, “BA”, “BB”]
4
AA | AB | AC | AD |
BA | BB | BC | BD |
CA | CB | CC | CD |
DA | DB | DC | DD |
100
100
(20, 90)
(40, 60)
Goal: Fill in the findAnswer Method
What are some potentially useful helper methods?
5
public class Rasterer {
private static final double MAX_X = 100;
private static final double MAX_Y = 100;
public static List<String> findAnswer(double x1, double y1,
double x2, double y2) {
// TODO
return null;
}
}
Arbitrary Challenging Problem of the Day
Find all labels that overlap the query.
findAnswer(20, 90, 40, 60)
[“AA”, “AB”, “BA”, “BB”]
6
AA | AB | AC | AD |
BA | BB | BC | BD |
CA | CB | CC | CD |
DA | DB | DC | DD |
100
100
(20, 90)
(40, 60)
Q
findAnswer Problem Decompositions
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.
7
Problem Decomposition in Software Engineering
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.
Perspective 1: Software engineering.
Eliminating special cases in k-d tree nearest made code simpler and more obvious.
Modularization is decomposition for managing software complexity at a project level.
8
Problem Decomposition in CS Theory
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.
Perspective 2: Computational complexity theory.
Reduction. Using an algorithm for Problem Q to solve Problem P.
“If any subroutine for task Q can be used to solve P, we say P reduces to Q.”
9
Algorithms (Dasgupta, Papadimitriou, Vazirani)
Graph Problems and Their Solutions
Paths. Find a path from s to every reachable vertex.�Depth-first search. O(V + E) runtime with adjacency list.
Unweighted Single-Source Shortest Paths.�Find a shortest path from s to every reachable vertex.�Breadth-first search. O(V + E) runtime with adjacency list.
Weighted Single-Source Shortest Paths.�Find a shortest path from s to every reachable vertex.�Dijkstra’s algorithm. O(E log V + V log V) runtime with adjacency list.
Weighted Single-Pair Shortest Paths.�Find a shortest path from s to a single goal vertex.�A* search. Dijkstra’s algorithm with h(v, goal) as priority. Runtime depends on heuristic.
10
Algorithm for Finding a Shortest Paths Tree
Given a weighted, directed graph with integer edge weights between 1 and 5, find the single-source shortest paths tree from s to every other vertex in the graph.
Your algorithm should be faster than Dijkstra’s algorithm.
11
B
C
A
s
5
5
D
1
2
1
0
1
2
4
Q
Dijkstra’s Runtime Analysis
PQ.add(s, 0)
For all other vertices v, PQ.add(v, infinity)
While PQ is not empty:
p = PQ.removeSmallest()�Relax all edges from p
Relaxing an edge (v, w) with weight:
If distTo[w] > distTo[v] + weight:
distTo[w] = distTo[v] + weight�edgeTo[w] = v�PQ.changePriority(w, distTo[w])
ArrayHeapMinPQ implementation.
Overall: O(V log V + V log V + E log V).
Simple: O(V log V + E log V).
Assuming E > V, this is just O(E log V) for connected graphs.
12
Optimized Priority Queue
Implement priority queue with constant time operations for Dijkstra’s algorithm.
When we visit v, each neighbor must be one of either:
13
A
B
C
A
s
5
5
D
1
2
1
0
1
2
4
A
0
1
2
3
4
5
C
B
B
A
C
D
B
D
D
A
C
B
D
Fringe
Reduction to BFS
For every edge e with weight w, replace e with a chain of w - 1 dummy vertices.
Then, run BFS on the result.
Return the shortest paths to real vertices.
14
A
B
C
A
s
5
5
D
1
2
1
0
1
2
4
B
C
A
s
D
Reductions
Given a graph G, we created a new graph G’, then fed it to a related (but different) algorithm, and finally interpreted the result.
15
G
B
C
A
5
5
D
1
2
1
Preprocess
G’
B
C
A
D
Postprocess
BreadthFirstPaths
BFS
SPT(G, A)
Topological Ordering
16
Topological Ordering
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w.
Which graph algorithm could 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], …
17
1
2
3
4
5
6
7
0
Q
Describe observations or ideas that you noticed about the valid orderings.
18
19
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]
20
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]
Topological Ordering
Perform a DFS traversal from every vertex with indegree 0, remembering marked vertices in between traversals. Record DFS postorder in a list.
Topological ordering is given by the reverse of that list (reverse postorder).
21
1
2
3
4
5
6
7
0
A
Topological “Sorting”
22
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
Seam Carving
23
Content-Aware Image Resizing
Seam carving. Resize an image without distortion for display on phones and internet.
24
Seam carving for content-aware image resizing (Avidan, Shamir/ACM); Broadway Tower (Newton2, Yummifruitbat/Wikimedia)
Original Photo
Horizontally-Scaled
Seam-Carved
25
Reduction to Dijkstra’s
To find a vertical seam…
Vertex. Pixel in image.
Edge. Cost to go from a pixel to its 3 downward neighbors.
Weight. Energy function of 8 neighboring pixels.
Seam. Shortest path (sum of weights) from top to bottom.
26
Shortest Paths (Robert Sedgewick, Kevin Wayne/Princeton)
Formal Problem Statement
Using AStarSolver, find the seam from any top vertex to any bottom vertex.
Given a digraph with positive edge weights, and two distinguished subsets of vertices S and T, find a shortest path from any vertex in S to any vertex in T.
Your algorithm should run in time proportional to E log V in the worst case.
27
Shortest Paths (Robert Sedgewick, Kevin Wayne/Princeton)
Q
S
T
What is your burning question from today’s lecture?
28