1
Q
Max flow algorithm inputs and outputs
A
Inputs
(this set of inputs is known as a flow network)
- G(V,E): a directed graph
- s, t: two vertices in V, s is a source and t is a sink
- c: capacities of each edge. c(u,v)>0 for all (u,v) in E.
- *Outputs**
- f: a function for flow such that f(u,v) gives how much is sent through edge (u,v)
- Sum f(*,t) is maximized. That is the flow from any vertex to t.
- C = Sum f(,t) (sometimes called f) is the size of the max flow.
2
Q
Max flow algorithm assumptions
A
- cycles are okay.
- anti-parallel edges are NOT okay. To remove an anti-parallel edge (edge that is parallel but going in opposite direction), you can add an extra vertex to the anti-parallel edge.
- the flow for each edge is non-negative and does not exceed capacity.
- For each vertex that is not s or t, the total flow into that vertex equals the total flow out.
- The total flow into s is equal to the total flow into t. Both are equal to C.
3
Q
Build a Residual Network inputs and outputs
A
- *Inputs:**
- G(V,E): a directed graph
- c: capacities of each edge. c(u,v)>0 for all (u,v) in E.
- f: a function for flow such that f(u,v) gives how much is sent through edge (u,v)
- *Outputs:**
- G^f = (V,E^f): the residual graph, with edges that point in the opposite direction as the edges in the original graph, between any two vertices
- c^f: the capacities show how much flow can be taken away from that edge in the original graph (i.e. flow in the other direction)
4
Q
Build a Residual Network runtime
A
O(n + m) but we assumes G is a connected graph and so m >= n-1 and so O(m)
5
Q
Ford-Fulkerson assumptions / implementation
A
- Uses the general max flow algorithm. See that algorithm for inputs and outputs.
- Assumes all capacities are positive integers
6
Q
Ford-Fulkerson runtime
A
- Rounds O(C): Flow increases by at least 1 per round, and there are C rounds (because C is the size of the max flow).
- Per round: O(m)
- Total: O(mC)
7
Q
Edmonds-Karp difference from Ford-Fulkerson
A
- Uses general max flow algorithm, like ford-fulkerson. However there is a modification - in step 3, instead of finding any path, we look for the shortest path in the residual graph G^f using BFS.
- Ford-Fulkerson runtime is O(mC) where C is the max-flow (i.e. Sum f(s,) == Sum f(,t)).
- Edmonds-Karp runtime is O(nm^2)
8
Q
Edmonds-Karp runtime
A
O(nm^2)
9
Q
Breadth First Search (BFS) Inputs, Outputs, and Runtime
A
- *Inputs:**
- Graph: G=(V,E), directed or undirected, starting vertex s in V.
- *Outputs:**
- dist[u]: distance from s to u if s can reach u, infinity otherwise.
- prev[z]: the parent index of vertex z.
Runtime:
O(n+m)
10
Q
When should you use BFS?
A
Use for unweighted single source shortest path problems.
11
Q
The BFS function outputs a distance-value for each edge. What does this represent?
A
d[u] gives the distance from u to the start vertex. This is the number of edges. It is NOT the sum of weights (in the case of a weighted graph). BFS does NOT consider weights.
12
Q
Dijkstra’s Algorithm Inputs, Outputs, and Runtime
A
- *Input:**
- Graph: G=(V,E), directed or undirected
- s: starting vertex s in V.
- w: positive edge weights.
- *Outputs:**
- dist[u]: distance from s to u if s can be reached from u. Infinity otherwise.
- prev[z]: the parent index of vertex z.
- *Runtime:**
- O( (n+m) logn)
- *remember the logn - this takes longer than BFS and DFS because weights are involved.
13
Q
Depth First Search (DFS) Inputs, Outputs, and Runtime
A
- *Inputs:**
- Graph: G=(V,E), directed or undirected
- *Outputs:**
- prev[z]: the parent index of vertex z in the DFS visitation
- pre[z]: the pre-order number in the DFS visitation
- post[z]: the post-order number in the DFS visitation
- ccnum[z]: the connected components number of the vertex z. Another card covers when this is the SCC number.
Runtime:
O(n+m)
14
Q
When is the ccnum[z] the strongly connected component number for z?
A
**Only relevant for directed graphs.
1) you have to run DFS on a reverse of the directed graph.
2) Then, run DFS, starting with the highest post order number from 1.
In this case, the ccnum is also the topological sort order in reverse.
15
Q
Strongly Connected Components (SCC) algorithm inputs, outputs
A
- *Inputs:**
- Graph: G=(V,E), directed
- *Outputs:**
- G^SCC = (V^SCC, E^SCC): where G^SCC is a meta graph (a DAG) with each SCC in G forming a vertex in V^SCC and each edge between SCCs in E^SCC
- ccnum[*]: comes from DFS, which is used the algorithm. Gives the SCC each vertex is a part of.
- V^SCC looks like 1, 2, 3, … which are ccnums for each SCC
- E^SCC: looks like (1,2), (2,3), … which are the edges between V^SCC
16
Q
Strongly Connected Components (SCC) runtime
A
O(n+m)
17
Q
How do you find the SCC of a vertex in a directed graph after running the SCC algorithm on it?
A
Use the ccnum value for a given vertex that the SCC algorithm returns. I.e. use ccnum[v] for v in the original graph’s vertices to find the SCC of v.
18
Q
2SAT algorithm inputs, outputs, and runtime
A
- *Input:**
- Conjunctive normal form (CNF) formula f
- *Outputs:**
- ‘No’ if f cannot be satisfied
- If f can be satisfied, an assignment (T or F) for each variable in f if it can be satisfied.
Runtime:
O(n+m) where n is the number of variables and m is the number of clauses.
19
Q
Conjunctive normal form
A
- n variables [x1, x2, … , xn]
- m clauses: (x1 or x2) and (x3 or ~x4) and …*
- each clause has at most 2 literals.
- Any clause with one literal can be satisfied and removed and so we assume we’re working with clauses with 2 literals.
*Note: xor = (x xor y) = (x or y) and (~x or ~y)
20
Q
How many literals are associated with n variables (i.e. [v1, v2, … , vn] used in 2SAT?
A
Each variable has 2 literals: v1 and ~v1 (~ = not). So n variables is associated with 2n literals.
21
Q
Is 2SAT NP complete?
A
No, kSAT for k>2 is NP complete. 2SAT is polynomial.
22
Q
Kruskal’s MST algorithm inputs, outputs, and runtime
A
- *Inputs:**
- Graph: G=(V,E), un-directed,
- edge weights: w
- *Outputs:**
- A minimum spanning tree defined by edges E^MST
- *Runtime**
- O(mlogm) which simplifies to O(mlogn)
23
Q
Prim’s inputs, outputs, and runtime
A
- *Inputs:**
- Graph: G=(V,E), connected, un-directed
- edge weights, w
- *Outputs:**
- A minimum spanning tree defined by the array prev.
- *Runtime:**
- O(mlogm) which simplifies to O(mlogn)
24
Q
True or false? In a DAG, every edge leads to a vertex with a lower post-order number.
A
True.
25
In a DAG, the vertex with the highest post-order number is a []. The vertex with the lowest post-order number is a [].
In a DAG, the vertex with the highest post-order number is a source. The vertex with the lowest post-order number is a sink.
26
True or False? Every DAG has at least once source and at least one sink.
True.
27
What is the distance between two nodes?
The length of the shortest path between them.
28
True of False? DFS creates a shortest path tree.
False. BFS returns a shortest path tree (assuming edges have unit lengths).
29
When building a residual graph, how are edges created and selected to get added to E^f (edges of the residual graph that are returned)?
Let E be the edges from the original graph.
```
**forward edges**
For (u,v) in E:
if f(u,v) < c(u,v):
add (u,v) to E^f
add c^f(u,v) = c(u,v) - f(u,v)
```
```
**backward edges**
For (u,v) in E:
if f(u,v) > 0:
add (v,u) to E^f
add c^f(v,u) = f(u,v)
```
30
What algorithms can you use to compute shortest path when graph weights are allowed to be negative?
Bellman-Ford and Floyd-Warshall
31
What are the differences between Bellman-Ford and Floyd-Warshall?
Bellman-Ford computes single-source shortest path in O(nm) time.
Floyd-Warshall computs all-pairs shortest path in O(n^3) time.
32
How does Bellman-Ford determine if there is a negative weight cycle in a graph?
Bellman-Ford creates a table as the algorithm runs keeping track of distance values from the starting vertex s to a given vertex z: T(i,z) = length of shortest path from s to z using <= i edges.
Bellman ford checks if T(n,z) < T(n-1,z) for any z. If so, there is a negative weight cycle.
33
How does Floyd-Warshall determine if there is a negative weight cycle in a graph?
Floyd-Warshall creates a table as the algorithm runs keeping track of distance values from the starting vertex s to a given vertex t using a subset of intermediate vertices:
T(i,s,t) = length of shortest path from s to t using a subset of {1, ... , i} intermediate vertices.
```
To detect a negative weight cycle, the algorithm checks:
If T(n,i,i) < 0 for any i, there is a cycle.
```
34
What is the cut property?
Suppose edges X are part of a minimum spanning tree G=(V,E). Pick any subset of nodes S for which X does not cross between S and V-S, and let e be the lightest edge across this partition. Then X union {e} is part of some MST.
35
Name three properties of trees
1) a tree on n nodes has n-1 edges
2) Any connected, undirected graph G=(V,E) with |E| = |V| -1 is a tree
3) An undirected graph is a tree if and only if there is a unique path between any pair of nodes (if there are two paths, this implies there is a cycle).
36
Properties of Union By Rank
Union by rank is a special data structure that makes the runtime of Kruskal's algorithm possible.
**Properties:**
1 ) for any x, rank(x) < rank(pi(x))
-- pi(x) is the set that contains x
2) Any root node of rank k has at least 2^k nodes in its tree
3) If there are n elements overall, there can be at most n/2^k nodes of rank k.
37
What data structure does Dijkstra's algorithm use to keep track of which node to visit next?
A priority queue, where the key of the queue for a given vertex is equal to the shortest distance (sum of edge-weights) found, thus far (i.e. while the algorithm is running) to a given node from the starting vertex, s.
38
How do you find the shortest path from a given vertex, s, in a DAG to any other vertex?
1) Find the topological ordering for the DAG
2) for each u in V in linearized order, for all edges (u,v) in E, update (u,v). Where "update()" looks for dist(v) = min{dist(v), dist(u) + l(u,v)}.
3) Set prev[u] to the previous node explored, for each node.
4) Use the dist-array to look up the length of the shortest path from the starting vertex to some vertex, t. Use the prev array to find the path. If dist[u] is infinity, u cannot be reached from s.
Note: edges do not have to be positive. We can use this to our advantage and negate all edge lengths to find the longest path.
39
What must be true for an undirected graph to be connected?
There is a path between any pair of vertices.
40
For any nodes u and v, the two intervals [pre(u), post(u)] and [pre(v), post(v)] are either what or what?
Disjoint, or one is contained within the other.
41
If the pre- and post-order numbers of a vertex, u are contained within those of another vertex, v, what type of edge is (u,v)?
A backward edge.
42
If the pre- and post-order numbers of a vertex, v are contained within those of another vertex, u, what type of edge is (u,v)?
Tree/forward edge
43
How can you tell if a directed graph has a cycle?
A directed graph has a cycle IFF its depth-first search reveals a back-edge.
44
Properties of a DAG
- In a dag, every edge leads to a vertex with a lower post number.
- Every dag has at least one source and at least one sink.
- A directed graph has a cycle if and only if its depth-first search reveals a back edge.
