CS6515_Exam2 Flashcards
1
Q
If you are given an UNDIRECTED graph you can only find ________ _________?
A
connected components
2
Q
If you are given a DIRECTED graph, you can only find ________ ________ _______?
A
strongly connected components
3
Q
When given an undirected graph, one of the best things to do first is look for strongly connected components? (T/F)
A
False. The concept of strongly connected components doesn’t exist for undirected graphs.
In the 06/15 Office Hours, Joves’ mentions big penalties will be applied for things like this.
4
Q
How do you find sources and sinks on an undirected graph?
A
Trick question. Sources and sinks don’t exist on undirected graphs. They only make sense in the context of directed graphs.
5
Q
What are some important properties/characteristics of Directed Acyclic Graphs (DAGs)?
Hint: DPV textbook mentions there are 3 of them
A
- A directed graph has a cycle if and only if its DFS reveals a back edge
- In a DAG, every edge leads to a vertex with a lower post number
- Every DAG has at least once source and at least one sink
6
Q
What is a source node?
A
A node with in-degree of 0, i.e. no incoming edges
7
Q
What is a sink node?
A
A node with out-degree of 0, i.e. no outgoing edges
8
Q
If your graph has no weights, then you can’t calculate a minimum spanning tree? (T/F) Why or why not?
A
This is really a trick question, the answer can be True or False, depending on perspective. In reality, MSTs only really make sense on a weighted graph. For an unweighted graph, the concept of “minimum” isn’t well-posed, so technically ANY spanning tree on an unweighted graph is minimal, but it’s essentially a useless definition (consider that it would also be a minimum spanning tree == maximal spanning tree in the unweighted case; a distinction without a difference).
9
Q
What are the 9 algorithms (at minimum) that we are allowed to use as black-boxes for HW/Exams?
A
- Dijkstra’s
- BFS
- DFS
- Explore (subroutine of DFS, but allowed to use as standalone algo)
- Strongly connected components (SCC) [Joves’ mentions this one as being especially important]
- 2SAT Algorithm
- Kruskal’s Algorithm
- Prim’s MST Algorithm
- Anything else mentioned in the Lectures and/or Textbook
Source: 06/15 Office Hours
10
Q
We should NEVER modify the black-box graph algorithms for the HW/Exam? (T/F)
A
True. Joves’ emphasizes this multiple times in 06/15 Office Hours.
11
Q
The strongly connected components algorithm is analogous to what other algorithm?
A
SCC uses multiple runs of DFS, with some modifications to the input and output variables.
12
Q
DFS/BFS do NOT consider edge weights? (T/F)
A
True.
13
Q
What is the runtime of DFS/BFS?
A
O(n + m), i.e. one of the fastest options we have, but with the caveat that if we need to consider edge weights, then that adds additional time complexity.
14
Q
What are the runtimes of all the key black-box graph algorithms?
A
- BFS: O(n + m)
- DFS: O(n + m)
- Dijkstra’s: O((n + m) * log n)
- Explore: O(m) if part of DFS; O(n + m) if standalone
- Topological Sort : O(n + m)
- SCC: O(n + m)
- 2-SAT: O(n + m)
- Kruskal’s MST Algo: O(m log n)
- Prim’s MST Algo: O(m log n)
- Ford-Fulkerson: O(mC)
- Edmonds-Karp: O(nm^2)
- Bellman-Ford: O(nm)
- Floyd-Warshall: O(n^3)
15
Q
We should ALWAYS use adjacency list representation for graphs in this class, and NEVER use adjacency matrices? (T/F)
A
True. Joves’ mentions in office hours that the gains from using the matrix form are minimal, and if implemented incorrectly can cause runtimes to massively explode.
16
Q
What is the runtime to index into a vertex in a graph?
A
For this class, we assume O(1)
17
Q
What is the runtime to find an edge in a graph? Why?
A
O(m). Because we have to scan over the edges in the adjacency list up to m edges.
18
Q
For exams, we need to explicitly define that n = |V| and/or that m = |E|? (T/F)
A
False. Joves’ says in 06/15 Office Hours we can just assume this as understood without explicitly writing down.
19
Q
To traverse a graph or find all edges, what is the runtime?
A
O(n + m)
20
Q
Why is traversing a graph or finding all the edges O(n + m) and not O(nm)?
A
Because if it was O(nm), that would imply that EVERY vertex is connected to EVERY edge. This is obviously not the case. Also, the runtime for BFS/DFS is O(n + m), which allows us to traverse all the edges in that amount of time.
Joves’ mentions a lot of students make this mistake.
21
Q
As mentioned in lectures/OH/textbook, what is “Property 1” of trees?
A
Removing a cycle edge cannot disconnect a graph.
22
Q
As mentioned in lectures/OH/textbook, what is “Property 2” of trees?
A
A tree on n nodes has n - 1 edges (i.e. the definition of a tree)
23
Q
As mentioned in lectures/OH/textbook, what is “Property 3” of trees?
A
Any connected, undirected graph G = (V, E) with m = n - 1 edges is a tree. (This is the converse of Property 2.)
24
Q
As mentioned in lectures/OH/textbook, what is “Property 4” of trees?
A
An undirected graph is a tree if any only if there is a unique path between any pair of nodes.
If there is more than one path between any pair of nodes, then there is a cycle
If there is no path between any pair of nodes, then it is not connected.
25
What is the "Cut Property"?
The Key Idea: Any edge which is minimum weight across a cut is going to be part of SOME MST.
More Precisely:
Considers UNDIRECTED graph G=(V,E)
1. Take a subset of edges X ⊂ E, where X ⊂ T, where T is a partial solution (i.e. it is part of some MST) that we assume is correct so far
2. Take a subset of vertices S ⊂ V where no edge is in the cut (S, S’)
3. Look at all edges of G in cut (S, S’)
4. Let e* be min weight edge in cut (S, S’)
5. Then: X ∪ e* ⊂ T’, where T’ is a new MST
See DPV 5.1.2, also lecture video GR3_9-10.
26
TODO: Finish office hours for 06/15
TODO: Start watching around the 1hr 15min mark.
27
What are some important abstract data types and their associated data structures?
Abstract Type ---> Data Structure
* Stack ---> Array, Linked List
* Queue ---> Array, Linked List
* Priority Queue ---> Heap
* Dictionary / Hashmap ---> Array
Source: Udemy Algorithms and Data Structures in Python lectures
28
What is the runtime of accessing the i'th element in an array/list?
O(1). This is because items are stored adjacent to one another in RAM.
29
What is a "Tree Edge"?
Anytime we visit a new vertex via an edge, we form a Tree Edge.
30
What is a "Forward Edge"?
An edge that goes from a node to a DESCENDANT in the tree.
31
What is a "Backward Edge"?
An edge that goes from a node to an ANCESTOR in the tree.
32
What is a "Cross Edge"?
Any other edge that isn't a Tree, Forward, or Backward edge, i.e. non-ancestry relationship.
(I think thinking of them as siblings or cousins is a helpful way of distinguishing, because neither of the nodes are descendants/ancestors of one another in a cross-edge relationship.)
33
You have a directed graph G and see an edge e=(zw), and that w is a direct child of z. You run DFS and see that the post(z) > post(w); what type of edge is this?
Tree edge (or Forest Edge, more generally)
34
You have a directed graph G and see an edge e=(zw). You run DFS and see that the post(z) < post(w), what type of edge is this?
Back edge
Note: This was actually one of our poll questions.
35
If the post order number is going DOWN, what type of edge(s) might this be?
Tree edge, forward edge, or a cross edge. If the post order number is going down and the relationship is a direct parent/child, then it's a tree edge. Otherwise it must be skipping down generations to a descendant, in which case it is a forward edge. If there's no ancestor relationship (i.e. the nodes are siblings or cousins), then it is a cross edge).
36
If the post order number is going UP, what type of edge(s) might this be?
Back edge
37
What is a tree?
A tree is an undirected graph that is connected and acyclic.
| See DPV pg. 129 for good info on tree properties.
38
If we have an undirected graph that is connected and acyclic, what is this called?
A tree.
| See DPV pg. 129 for good info on tree properties.
39
A tree on n nodes has how many edges?
n - 1
| See DPV pg. 129 for good info on tree properties.
40
If we have a connected, undirected graph G=(V,E) with |E| = |V| - 1, what type of graph is this?
A tree.
| See DPV pg. 129 for good info on tree properties.
41
An undirected graph is a tree i.f.f. there is a unique path between any pair of nodes? (T/F). Why or why not?
True. In a tree, any two nodes can only have one path between them; for if there were two paths, the union of these paths would contain a cycle.
42
We can tell whether a connected, undirected graph is a tree or not just by counting how many edges it has? (T/F)
True. If it has n - 1 edges, then this must be the case.
| See DPV pg. 129 for good info on tree properties.
43
When doing topological sort, we order the vertices by ________ _________ order number
decreasing; post
44
What is the main idea of Dijkstra's algorithm?
It's a greedy algorithm. It attempts to find the global optimum by with the aid of the local optimum. Given an input node, Dijkstra's algorithm initially assumes an infinite distance between other nodes, slowly iterates and updates each node with the local best path and the best path found so far.
45
Dijkstra's algorithm at start assumes an infinite distance between nodes? (True/False)
True
46
What is one of the principle advantages of the Bellman-Ford algorithm over Dijkstra's algorithm?
Bellman-Ford can handle positive and negative edge weights, whereas Dijkstra's can only handle positive edge weights.
47
What data structure is used for Dijkstra's algorithm?
A heap (in this class we typically assume min-heap)
48
Bellman-Ford algorithm is slower than Djikstra's algorithm? (T/F)
True
49
What is one of the key ideas of the Bellman-Ford algorithm?
The idea of "Relaxation" of edge weights. It does this for all edges in the graph at the same time for V - 1 iterations (and then it does one more iteration to detect negative cycles). This gives us a runtime complexity of O(n*m).
50
What is the runtime of the Bellman-Ford algorithm?
O(n*m), where n = |V| and m = |E|
51
When running the Bellman-Ford algorithm, if we've run V - 1 iterations, and then run a final V'th time and the cost DECREASES, what can we conclude?
There MUST be a negative weight cycle present.
52
Dijkstra's algorithm is a _______ approach, whereas Bellman-Ford algorithm is a _______ approach?
greedy; dynamic programming
53
How many iterations are there in the Bellman-Ford algorithm? How many are there if we include checking for negative weight cycles?
|V| - 1, i.e. m - 1 if we don't check for negative weight cycles. If we do check, then we simply perform one more iteration, so a total of |V| iterations.
54
Bellman-Ford's algorithm can only handle positive edge weights? (T/F)
False. It can also handle negative edge weights, which is one of it's principle advantages over Dijkstra's algorithm.
55
Dijkstra's algorithm can only handle positive edge weights? (T/F)
True
56
What are some algorithms for finding a path between two vertices in a graph such that the same of the edge weights are minimized (i.e. shortest path algorithms)?
1. Dijkstra's algorithm
2. Bellman-Ford algorithm
3 A* Search
4. Floyd-Warshall algorithm
Note: I don't think A* is mentioned in the lectures or textbook, so I don't think it is available as a black box to us.
57
What type of data structure does BFS use?
Queue, i.e. FIFO, like a line at Disney World
58
What type of data structure does DFS use?
Stack, i.e. LIFO, like a stack of dishes
59
What is the SPACE complexity of BFS vs. DFS?
BFS: O(n), because we have to use a queue that ends up upper bounded by the number of leaf nodes.
DFS: O(log n), because we use a stack data structure that only has to maintain up to the HEIGHT of the tree
60
In general, which type of graph search is preferred, DFS or BFS? Why? What are some exceptions?
Generally DFS, because it in general has better space complexity and has some other nice properties. This doesn’t mean we should avoid BFS; but I think for this class we’re likely to see more usage of DFS, whether on its own or under the hood of other algorithms (e.g. SCC, etc).
AI/robot motion is a good example of an exception to this where we might prefer BFS over DFS. This is because BFS goes layer-by-layer, so it can be better for discovering the LOCAL ENVIRONMENT.
61
What are the input(s) for BFS?
1. Graph G = (V, E), directed or undirected
| 2. Source vertex s in V
62
What are the output(s) for BFS?
1. dist[u]: array containing distance from source s to u IF s can reach u; inf otherwise
2. prev[z]: array containing the parent index of vertex z
Source: Joves' notes, HW4 practice problems
63
What is the runtime of BFS?
O(n + m), i.e. linear
64
In BFS, the dist array contains the sum of the weights on the path from source s to destination u? (T/F)
False. dist[u] is the given as the NUMBER OF EDGES from s to u, NOT the sum of the weights. Very important to remember this.
Source: Joves' notes
65
What are the input(s) to Dijkstra's Algorithm?
1. Graph G=(V, E), directed or undirected, with POSITIVE EDGE WEIGHTS c_e in E
2. Source vertex s in V
66
What are the output(s) of Dijkstra's Algorithm?
1. dist[u]: array containing distance from source s to u IF s can reach u; inf otherwise
2. prev[z]: array containing the parent index of vertex z (can be used to reconstruct the shortest path)
Source: Joves' notes, HW4 practice problems
67
What is the runtime of Dijkstra's algorithm?
O( (n + m)*log n)
68
BFS can be used to determine the weighted Single Source Shortest Path (SSSP)? (T/F). Why or why not?
False. Because the "shortest path" given by BFS is in terms of the NUMBER OF EDGES, and NOT the edge weights. We would need to use something like Dijkstra's algorithm for weighted edges (assuming the edge weights are positive).
69
Dijkstra's algorithm can be used for non-negative, weighted Single Source Shortest Path (SSSP)? (T/F)
True.
70
What is one connection between BFS and Dijkstra's algorithm?
They can both be used for Single Source Shortest Path (SSSP) determination. However, BFS ONLY works for unweighted graphs, whereas Dijkstra's can handle (positive) weighted edges.
71
If BFS and Dijkstra's Algorithm can both be used for SSSP determination, why is the runtime for BFS O(n + m), but the runtime for Dijkstra's Algorithm O( (n + m)*log n) ?
SSSP: Single Source Shortest Path
Because BFS can only handle SSSP for UNWEIGHTED graphs, whereas Dijkstra's handles graphs with (positive) edge weights. If you're doing extra work to process weights, then you can't achieve linear O(n + m) runtime, hence the difference between the two.
72
What are the input(s) for DFS?
1. Graph G=(V, E), directed or undirected
Source:
Joves' Notes
73
What are the output(s) of DFS?
Hint: there are 4, and they are all arrays
1. array prev[z]: the parent index of vertex z in the DFS visitation
2. array pre[z]: the pre-order number of vertex z in the DFS visitation
3. array post[z]: the post-order number of vertex z in the DFS visitation
4. array ccnum[z]: the connected components number of vertex z. Can also be the strongly connected component number (SCC) IF the vertices are passed in topologically sorted, i.e. as highest post number --> lowest post number AFTER running DFS on a REVERSED DIRECTED GRAPH. For a directed graph that is processed this way, the ccnum will also be the topological sort order in reverse.
Source:
Joves' Notes
74
What is the runtime of DFS?
O(n + m)
75
DFS can be used in an undirected graph to determine how many components there are? (T/F)
True. This would come from the max value for the ccnum
Source: Joves' Notes
76
DFS can be used in an directed graph to determine how many components there are? (T/F)
False. This only works for UNDIRECTED graphs. For a directed graph, you would need to use something like SCC to do this.
Source: Joves' Notes
77
How do pre/post order numbers behave on a DIRECTED graph?
They give information on how a graph COULD be explored. Some numbers might be interchangeable, others might not (see DPV 3.3(d) for a good example f this).
Source: Joves' Notes
78
How do pre/post order numbers behave on an UNDIRECTED graph?
They give information on how a graph WOULD be explored GIVEN a particular starting point. A different root node might give an entirely different pre/post order numbering.
Source: Joves' Notes
79
In DFS, the ccnum in a directed graph only works if you always explore from a sink vertex if all previous sink SCCs were removed? (T/F)
True. Keep in mind that a source vertex will be able to reach all connected vertices and will thus be more or less useless.
TODO: Need to review the SCC section again, as this still isn't totally clear to me.
80
A DAG will only have one valid topological ordering? (T/F).
False. See DPV 3.3(d) for a good example of why this is the case. TL;DR version: post order numbering on a DIRECTED graph provides information on how a graph COULD be explored; it might admit multiple valid topological orderings.
81
A DAG will have at least one valid topological ordering? (T/F)
True.
82
A DAG will have at least one valid topological ordering? (T/F)
True.
83
What are the input(s) to the Topological Sort Algorithm?
1. DAG
Source: Joves' Notes
84
What are the output(s) of the Topological Sort Algorithm?
1. array topo[i]: the vertex number of the i'th vertex in topological order from left to right, source to sink, (i.e. in DESCENDING post order number)
Source: Joves' Notes
85
What is the runtime of the Topological Sort Algorithm?
O(n + m)
Source: Joves' Notes
86
How does the Topological Sort Algorithm work?
It works by running DFS on a DAG and using the post order numbers to sort the vertices from highest to lowest.
87
What order will post order numbers be returned in from the Topological Sort algorithm?
In terms of decreasing post order number, i.e. from Source to Sink, which is equivalent to having all edges from left to right in the DAG.
88
The topological ordering comes along as a free ride when using the DFS algorithm? Does it need to be manually sorted or not if doing it this way?
True. No, it doesn't require manually sorting. Do an example by hand to see that this is true. (This is also part of why we can achieve an O(n + m) runtime, because if we had to sort that would be a minimum of O(nlogn) )
89
What are the input(s) to the Explore Algorithm?
1. Graph G = (V, E), directed or undirected
2. vertex v in V to explore from
Source: Joves' Notes
90
What are the outputs(s) of the Explore Algorithm?
1. array visited[u] is set to "True" for all nodes u reachable from v
2. Any other data structure that DFS has, if needed
Source: Joves' Notes
91
What is the runtime of the Explore Algorithm?
1. O(m) if run as part of DFS
2. O(n + m) if run by itself and visited[] array needs to be created
Source: Joves' Notes
92
The runtime of the Explore Algorithm is O(n + m)?
True, although not a comprehensive answer. This is True IF explore is run by itself which requires the visited[] array to be created. If run as part of DFS, then explore is O(m)
93
All of the outputs from DFS are available to the Explore algorithm as well? (T/F)
True. (The ccnum, prev, pre, and post, are all actually set in this subroutine; see DPV 3.2.2)
94
When might it be better to use Explore as our black-box algorithm rather than the full DFS algorithm?
If we only need information about a single source vertex, then it's going to be better to use explore since it provides us with all the same outputs as DFS, but can isolate to only the source vertex of interest instead of running over all vertices)
95
The explore algorithm runs on all of the vertices and edges that are reachable from the input vertex v? (T/F)
True.
Source: Joves' Notes
96
What is the runtime of the Floyd-Warshall algorithm?
O(n^3)
97
Compare Dijkstra vs. Bellman Ford vs. Floyd-Warshall Algorithm. When might we want to use each one? What are some of the pros and cons?
All of these are examples of algorithms for FINDING SHORTEST PATH(s)
1. Dijkstra: simple algorithm, and the fastest option at O( (n + m)*log(n)); however, can only use it IF all the edge weights are positive)
2. Bellman-Ford: Good to use if we have negative edge weights and are only interested in the Single Source Shortest Path (SSSP), which gives us a runtime of O(nm).
3. Floyd-Warshall: Good to use if we have negative edge weights and are interested in All Pair Shortest Path (APSP); the tradeoff is that this is the slowest order at O(n^3)
Joves' notes also mention that while Bellman-Ford and Floyd-Warshall are both algorithms available to us as black-boxes, they are technically DP solutions, so think twice about whether using them is really warranted before you go off writing a solution using them).
Source: Joves' Notes
98
What are the input(s) to the Strongly Connected Components (SCC) algorithm?
1. Graph G=(V, E), directed. (Crucial to remember that SCC is for DIRECTED graphs!!!)
Source: Joves' Notes
99
What are the output(s) of the Strongly Connected Components (SCC) algorithm?
1. 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
2. ccnum[.] comes from DFS used underneath the hood of this algorithm
3. V_scc will look like 1, 2, 3, 4... which are the ccnums
4. E_scc will look like (1, 2), (2, 3), (3, 4), ... which are edges between V_scc
Source: Joves' Notes
100
If we run SCC on some graph G, and we have two vertices u and v that we want to find which SCC u and v are in, how might we do this?
Look up ccnum[u] and ccnum[v]
Source: Joves' Notes
101
Your examining some code that uses the SCC algorithm, and you notice a line with the conditional statement "if ccnum[u] == ccnum[v]: ". What is this conditional statement checking for?
It is checking to see if u and v are part of the same strongly connected component.
102
What is the runtime of the SCC algorithm?
O(n + m)
103
What algorithm is used under the hood of SCC? How many times is it run? Why is it run multiple times?
DFS. Twice. Because we have to run on both G and the reverse of it G_r
104
Every directed graph is a DAG of its strongly connected components? (T/F)
True.
See property on DPV 3.4.1, pg. 92.
105
What is the proper conception of the idea of connectivity on a DIRECTED graph?
Two nodes u and v of a directed graph are connected if there is a path from u to v AND a path from v to u.
See DPV 3.4.1, pg. 91.
106
Describe how the SCC algorithm works?
1. Run DFS once with pre/post order numbering on reverse graph G_r
2. Sort V in descending post order number (This gives sink to source)
3. Run DFS again on G with V sorted
4. Output will have ccnum representing SCC with higest = source, lowest = sink
5. Use the ccnum to gather up vertices belonging to each SCC
6. Check all the original edges and their endpoints. If the endpoints are in different SCCs, and a corresponding E_scc between those SCCs does not already exist, we add a E_scc to represent the edge from one SCC to another.
Source: Joves' Notes
107
In the SCC algorithm, the output with the highest ccnum is a ______ and the lowest is a ______?
Source; Sink
108
What are the input(s) to the 2SAT algorithm?
1. Conjunctive normal form (CNF) formula f, which contains n variables (x1, x2, ... x_n), m clauses (x1 v x2) ^ (x3 v !x4)...
Each clause has at most two literals (and for this course, we can assume that it is EXACTLY two literals).
Source: Joves' Notes
109
For the 2SAT algorithm, any clause with one literal can be satisfied and removed leaving us with a CNF f' of only clauses with exactly two literals? (T/F)
True
110
For the 2SAT algorithm, we can assume that we are working with clauses that contain EXACTLY two literals? (T/F)
True
111
What are the output(s) of the 2SAT algorithm?
```
An assignment (T or F) for each variable in f if it can be satisfied.
Otherwise, 'NO' if it cannot be satisfied
```
Source: Joves' Notes
112
What are the input(s) to Kruskal's algorithm?
1. Graph G=(V, E), connected, undirected; edge weights w
113
What are the output(s) of Kruskal's algorithm?
1. A minimum spanning tree (MST) defined BY THE EDGES E_mst
114
What is the runtime of Kruskal's algorithm?
O(m log m) or simplified to O(m log n)
115
Describe how Kruskal's algorithm works?
1. Sort edges by weight
2. Grab lightest available edge THAT WONT CREATE A CYCLE. (If multiple edges with the same weight are available, it doesn't matter which one we pick, so long as it doesn't create a cycle.)
3. Keep doing this until all edges that will not create a cycle have been added (which will happen at exactly n - 1 edges)
116
At what point will we stop adding edges in Kruskal's algorithm
When we've added exactly n - 1 edges (which is the definition of a tree)
117
When might we want to use Kruskal's algorithm as one of our black-boxes?
It is one of the more common MST algorithms, so if we think we need MST, it's a good one to start with. The output gives us a set of edges which is useful to construct the next input for a black box, or to compare to the original G. Unlike Prim’s, it does not give us any path information.
118
What are the input(s) to Prim's algorithm?
1. Graph G=(V, E), connected, undirected; edge weights w
119
What are the output(s) of Prim's algorithm?
1. A minimum spanning tree (MST) defined BY THE ARRAY prev
120
What is the runtime of Prim's algorithm?
O(m log m) or simplified to O(m log n)
121
Describe how Prim's algorithm works?
1. Start with arbitrary vertex v and put it into a subtree S of included vertices
2. In each iteration, grow S by adding the LIGHTEST EDGE between a vertex in S and a vertex outside of S
3. Continue until all vertices are in S (this will happen at exactly n - 1 edges)
122
What other black-box algorithm is Prim's algorithm similar to? Why?
Dijkstra's algorithm. It's similar in that it can give us path information in the MST output.
123
What is one reason we might pick the less commonly used Prim's algorithm over Kruskal's algorithm?
Prim's algorithm gives us path information as part of the MST output, so if we need path information, that might be one reason to pick it over Kruskal's.
In general, if a problem is asking about MSTs, it's probably best to start by thinking about using Kruskal's; ask yourself if you REALLY need path information. If so, Prim's is a good option, but it's definitely the less common scenario.
124
Prim's algorithm provides us with edge information as part of the MST output? (T/F). Why or why not?
False. Because the output of Prim's algorithm is the array "prev" that contains the paths of the MST, whereas Kruskal's algorithms gives us the edges of the MST in the form of E_mst.
125
What is the difference in the output(s) between Kruskal's and Prim's algorithm for MSTs?
Kruskal's outputs the MST EDGES E_mst, whereas Prim's outputs the MST PATHS.
126
What are the input(s) to the 2-SAT algorithm?
1. Conjunctive Normal Form (CNF) formula "f" that contains:
n variables [x1, x2, ..., x_n]
m clauses (x1 v x2) ^ (x3 v !x4) ...
Each clause has at most 2 literals
127
For the 2-SAT algorithm, we can assume we will always be working with clauses with exactly two literals? (T/F) Why or why not?
True. Because any clause with one literal can be satisfied and removed leaving us with a CNF f' of only clauses with EXACTLY two literals
128
What are the output(s) of the 2-SAT algorithm?
```
An assignment (T or F) for each variable in f if it can be satisfied;
"NO" otherwise
```
129
What is the runtime of the 2-SAT algorithm?
O(n + m)
130
Each variable in the 2-SAT algorithm is made up of ____ literals: ____ and _____?
two; x and !x
131
If we're using the 2-SAT algorithm and we have some formula that contains 10 variables, how many literals will we have? Why?
There would be 20 literals, because if there are n boolean variables then there will be 2n literals, for example:
[x1, !x1, x2, !x2, ... x_n, !x_n]
132
In the 2-SAT algorithm, variables and literals are provided separately? (T/F) What is one important consequence of this?
False. They are part of the formula. The consequence is that finding all variables is O(m) because we have to look at all clauses and list them all.
133
What does the "k" in K-SAT mean?
It denotes the maximum number of literals in each clause (if there is no limit, then we simply call it a SAT problem)
134
FOR k-SAT problems, if k >= 3 then it is a(n) _________ problem?
NP-Complete
135
FOR k-SAT problems, if k=2 then it is a(n) _________ problem?
P (i.e. Polynomial)
136
At a high level, what is the 2-SAT algorithm doing?
It transforms a 2-SAT Conjunctive Normal Form(CNF) formula into a graph and solves it
137
How does the 2-SAT algorithm work?
Hint: there are 7 steps
1. Create a graph G from f by mapping the CNF to 2n vertices (one for each literal) and 2m edges (one for each implication)
2. Run the SCC algorithm on G
3. If for all x in X, x and !x are in DIFFERENT SCCs then the CNF is satisfiable, else return "NO"
4. Set all SOURCE literals to "FALSE" and remove the SOURCE SCC
5. Set all SINK literals to "TRUE" and remove the SINK SCC
6. Repeat steps 4 and 5 until all literals are set
7. Return the variable assignments
138
When creating the graph for a 2-SAT problem from the CNF, we use ____ number of vertices and ____ number of edges? Why is it this number?
2n vertices (one for each literal) and 2m edges (one for each implication).
139
What is the time complexity to ACCESS edge WEIGHTS in an (n x n) matrix?
O(1)
140
What is the time complexity to WRITE edge WEIGHTS in an (n x n) matrix?
O(1)
141
What is the time complexity to ITERATE over edge WEIGHTS in an (n x n) matrix? Why is this?
For this class, TAs have said we can assume O(m).
142
What sort of data structure can we use to store edge WEIGHTS in (given we already have an adjacency list representation of the graph G)? How do we do this?
An (n x n) matrix)
We do this by:
1. Initializing an (n x n) matrix # This is O(1) because cost is only incurred when actually writing values
2. Set each edge weight in the table # This is O(1) * O(m) = O(m)
By only setting values where there is an edge, we avoid the typical O(n^2) cost of working with an (n x n) table
143
What functions are required for the Union by Rank (Disjoint Sets) data structure? What are the runtimes of all of them?
1. makeset(x): create a singleton set containing just x # O(1)
2. find(x): to which set does x belong? # O(log n)
3. union(x, y): merge the sets containing x and y # O(log n)
144
What is the maximum height allowed of any tree in a Union by Rank (Disjoint Sets) data structure? What is one important consequence of this?
log(n). This fact means that it is also the upper bound on the running time of the "find" and "union" operations used by this data structure, i.e. O(log n)
145
If an element in a disjoint set has a parent pointer that has a self-loop, what can we conclude?
That that element is the root of the tree
146
How should we interpret the "rank" of a node in a disjoint data set?
It is the height of the subtree hanging from that node
147
Per the DPV textbook, what is "Property 1" of the Union by Rank (Disjoint Set) data structure?
For any x, the rank(x) < rank(pi(x))
where pi here should be interpreted as a function that returns the parent pointer of x.
A better way of looking at this is that the height of the subtree hanging beneath x (which is the definition of "rank") will always be strictly shorter than the height of the subtree hanging from the parent of x. (Which should be a pretty obvious statement - one rung higher up the ladder is, well... one rung higher up on the ladder.)
148
Per the DPV textbook, what is "Property 2" of the Union by Rank (Disjoint Set) data structure?
Any root node of rank k has at least 2^k nodes in its tree
149
For Union by Rank (Disjoint Set) data structures, if there is a root node with a rank of 3, then its tree will have AT LEAST how many nodes?
2^k = 2^3 = 8
This is from property 2 for this data structure (see DPV 5.1.4 and Joves' notes)
150
For Union by Rank (Disjoint Set) data structures, there is a root node with rank k, then what can we deduce?
Hint: use property 1
That it was created by the merger of two trees with roots of rank k - 1
151
Per the DPV textbook, what is "Property 3" of the Union by Rank (Disjoint Set) data structure?
If there are n elements overall, there can be at most n / 2^k nodes of rank k
Crucially, this implies that the max rank is log(n), therefore all the trees have height <= log(n), which is the upper bound on the running time of the "find" and "union" operations.
152
For Union by Rank (Disjoint Set) data structures, if we have n=16 elements in total, then there could be AT MOST how many nodes of rank 3?
Hint: use property 3
Since we're interested in how many nodes there could be with rank 3, this means k = 3. Using property 3, we know that n_k <= n / 2^k, i.e.:
16 / 2^3 = 16 / 8 = 2, therefore final answer is there could be at most 2 nodes with rank 3.
153
What is the runtime of the Bellman-Ford algorithm?
O(nm)
154
What is the runtime of the Floyd-Warshall algorithm?
O(n^3)
155
What are three shortest paths black box algorithms available to us? List some of the pros and cons of each.
1. Dijkstra's algorithm: If we need simple algorithm for non-negative, weighted SSSP
Pros: Fast, simple
Cons: Does NOT work for negative weights
2. Bellman-Ford: if we need to get the Single Source Shortest Path (SSSP) on a graph that includes negative weights
Pros: works with negative weights, faster than Floyd-Warshall [O(nm) vs O(n^3)]
Cons: only provides answer for single source
3. Floyd-Warshall: if we need to get the All Pair Shortest Path (APSP) on a graph that includes negative weights
Pros: works with negative weights, gives info for all vertices
Cons: slowest option of the three [O(n^3)]
156
Dijkstra's is an example of a ______ algorithm, whereas Bellman-Ford and Floyd-Warshall are examples of ______ algorithms?
Greedy; dynamic programming
157
The explore algorithm gives us a list of vertices reachable from source vertex s? (T/F)
True. This is specific to explore without any additional details. We (the TAs) know this is an output and we simply read it as such.
Source: Joves' notes
158
The DFS algorithm gives us a list of vertices reachable from source vertex s? (T/F) Why or why not?
False. Without additional details, this is NOT something that DFS gives us. The visited array DFS returns is going to be all 'True' by the end of each run.
VERY IMPORTANT TO REMEMBER THIS.
159
You can always rely on DFS to give you the vertices that are reachable from a source vertex s? (T/F) Why or why not?
False. Without additional details, this is NOT something that DFS gives us. The visited array DFS returns is going to be all 'True' by the end of each run.
VERY IMPORTANT TO REMEMBER THIS.
160
Explore and DFS can both get us a path from s? (T/F) How do we do this, or if not possible, why can't it be done?
True. For explore, we simply run 'explore(s)' For DFS, we "start" it from s by putting s at the head of the list, so we would run DFS(G, s)
161
How can we use DFS to find all reachable vertices from s?
for v in V, find all v with the same ccnum as s. These are reachable by s.
This is a detail you need to give, because it is NOT a free output of DFS!
Source: Joves' notes
162
In a DAG, every vertex leads to a vertex with a _____ post number?
lower
See DPV 3.3.2 pg. 90
163
What is property 1 of the SCC algorithm?
If the explore subroutine is started at node u, then it will terminate precisely when all nodes reachable from u have been visited
See DPV 3.4.2 pg. 92
164
What is property 2 of the SCC algorithm?
The node that receives the HIGHEST post number in a DFS must lie in a SOURCE SCC
See DPV 3.4.2 pg. 92
165
What is property 3 of the SCC algorithm?
If C and C' are SCCs, and there is an edge from a node in C to a node in C', then the HIGHEST post number in C is bigger than the HIGHEST post number in C'.
This can be restated as saying that the strongly connected components can be linearized by arranging them in DECREASING order of their highest post numbers.
See DPV 3.4.2 pg. 92
166
In a DAG, each node is a singleton strongly connected component? (T/F) Why or why not?
True. This about it: in a DAG, you can ONLY go one direction. You can never go backwards to a previous vertex, so each vertex must be its own SCC.
167
Back edges behave differently than all the other types of edges? (T/F) Why or why not?
True. With back edges, the post numbers go UP. For all other types of edges (tree, forward, cross), the post numbers go DOWN.
168
For tree edges, the post order number goes ____?
down (and the edge is part of the DFS tree)
169
For forward edges, the post order number goes ____?
down (and the edge points down to some non-child descendant in the tree)
170
For back edges, the post order number goes ____?
up
171
For cross edges, the post order number goes ____?
down (and the nodes are not descendants of each other, i.e. they are siblings or cousins)
172
If a directed graph G has no cycles in it, what is one thing that we can infer?
That there are no back edges in the graph (This comes from the cycle property - see GR1_9)
173
If a graph G has a back edge in it, what is one thing we can infer?
That a cycle is present in the graph.
174
A DAG might have back edges present? (T/F) Why or why not?
False. Because of the cycle property. If a back edge is present, then there MUST be a cycle in the graph. Since DAGs are by definition acyclic, a DAG will never have a back edge.
175
For topologically sorting a DAG, the time to sort the vertices in order of decreasing post number will take O(n log n) time? (T/F) Why or why not?
False. This is because when we run DFS for the topological sort algorithm, the clock starts at 1, so the minimum value the post number can take on will be one. The maximum value will be 2n. This means we just initialize an array of size 2n, and stick the vertices in the array as we see them, which just gives us the vertices in decreasing post number. This only takes linear time to do, i.e. O(n + m)
TODO: not 100% sure why the size is 2n and not just n
176
A DAG always has at least one ______ and at least one _____?
source; sink
177
What is one property that will always be true of the SOURCE vertex in a DAG?
It will always have the HIGHEST post number
178
What is one property that will always be true of the SINK vertex in a DAG?
It will always have the LOWEST post number
179
Define connectivity in a DIRECTED graph?
Two vertices v and w are connected if there is a path from v --> w AND a path from w --> v
180
What is the definition of an SCC? How does it differ from a regular CC?
An SCC is the maximal set of strongly connected vertices in a directed graph.
This differs from a CC on an undirected graph because a CC in that graph is just the maximal set of connected vertices (i.e. the 'strong' part doesn't make sense in the context of an undirected graph. In an undirected graph there is always a path from u --> v and v --> u (obviously by just traversing the same edge in forward/reverse)
181
What is one important property of a metagraph drawn on strongly connected components? Why is this the case?
It is a DAG.
Proof by Contradiction: Consider the alternative. If there was a path between an SCC S and another SCC S’ and also a path from S’ → S, then we would have a cycle, and it would mean that we could always get from anywhere in S to anywhere in S’, and vice-versa. This means that union(S, S’) would be an SCC, i.e. they would be in the same SCC, which obviously contradicts that they are in different SCCs.
182
Every directed graph is a DAG of it's SCCs? (T/F)
True. This is because you could never have a cycle between two SCCs S and S', because if there was, then they would actually be part of the same SCC.
183
What is the main idea of the SCC algorithm?
Hint: There are four key steps
1. Find a sink SCC S
2. Output it,
3. Remove it
4. Repeat
184
For the SCC algorithm, is it better to run it from source SCCs or sink SCCs? Why?
Sink SCCs. Because the explore algorithm when run from a sink SCC will ONLY explore the vertices in that SCC and NOTHING ELSE.
185
In a general directed graph G, the vertex with the LOWEST post number always lies in a SINK SCC? (T/F)
False. This has important implications for our SCC algorithm, namely it is why we reverse the graph G to invert sources and sinks.
186
In a general directed graph G, the vertex with the HIGHEST post number always lies in a SOURCE SCC? (T/F)
True. This has important implications for our SCC algorithm, namely it is why we reverse the graph G to invert sources and sinks.
187
A source SCC in G == sink SCC in G_r? (T/F)
True. This is what allows our SCC algorithm to work by inverting sources/sinks.
188
A sink SCC in G == source SCC in G_r? (T/F)
True. This is what allows our SCC algorithm to work by inverting sources/sinks.
189
What is the runtime of the SCC algorithm and why is this the case?
O(n + m). Because under the hood SCC is simply running DFS twice, so O(n + m) + O(n + m) = 2*O(n + m) --> O(n + m)
190
Why is the SCC algorithm correct?
The proof is based on the claim that the vertex with the highest post number always lies in a source SCC. We can prove this by making the simpler claim that for two SCCs S and S' if there is a path from vertex v in S to vertex w in S', then max(post(S)) > max(post(S')), therefore if we topologically sort by max post number, the highest number is guaranteed to be in the source SCC.
It's easier to think of this visually. If there is a path from SCC S to S' and we start DFS from some vertex z in S', then we would visit all of S' and none of S. Conversely, if we start DFS from S, then the subtree of vertex z would contain the union(S, S'). This is what forces the condition that max(post(S)) > max(post(S')),
191
In some case, there might be a path from an SCC S to an SCC S' and a path from S' --> S? (T/F)
False. If there was such a bidirectional path, then both S and S' would be in the same SCC, which is a contradiction! Remember: a metagraph drawn on strongly connected components will always be a DAG i.e. no cycles will exist.
192
What is the output of DIjkstra's algorithm?
for all v in V, it returns dist(v) = length of shortest path from s --> v
193
Say you have some undirected, non-weighted graph G=(V,E), and you run BFS on it for some vertex s in V, i.e. BFS(G, s). You're interested in the distance from s to some vertex u. Now a few questions:
(a) if you use a bit of pseudocode "dist(u)", what will this return?
(b) say you run the pseudocode "dist(u)" and it returns "inf". What does this mean?
(c) it would be valid to run the pseudocode "prev(u)"? (T/F). If True, what would it return?
(a) the min # of edges from s to u (or inf if a path doesn't exist)
(b) that there isn't a path from s to u
(c) True. It would return the previous vertex on the path from s to u.
194
What is the runtime of Dijkstra's algorithm (at least for this class) and what data structure do we use?
For this class we assume O((n + m)*log n) using the "min-heap" data structure
195
What are the logical symbols we use for AND and OR?
^ == AND (remember that it looks kind of like an "A"
| v == OR
196
For what value of k is k-SAT NP-Complete for?
For all k >= 3
197
There is no polynomial time algorithm for solving 2-SAT problems? (T/F)
False. There is indeed such a polynomial time algorithm. k-SAT problems are NP-Complete for all k >= 3
198
In the context of SAT problems, what is a "unit clause"? What is important about these types of clauses.
A clause with only one literal in it, e.g. (!x1) ^ (x1 v x4), the (!x1) is an example of a unit clause.
The important thing about these clauses is that for a unit clause in a CNF, a unit clause MUST be satisfied in order for a solution to the formula to exist. This means that the unit clause imposes a constraint. So in the above example of the unit clause (!x1), this means that it MUST be that x1=False in order for the unit clause to evaluate to True.
199
How can we simplify the inputs for a 2-SAT problem?
We can simplify by doing:
1. Take a unit clause, say literal a_i
2. Satisfy it (set a_i = T)
3. Remove clauses containing a_i and drop !a_i
4. Let f’ be the resulting formula
5. Repeat the process on f' until we get down to clauses of size=2
200
For a 2-SAT problem represented as a graph, how many vertices are there?
2n vertices, which correspond to all the literals x1, !x1, x2, !x2, ..., x_n, !x_n
201
For a 2-SAT problem represented as a graph, how many edges are there?
2m edges, which correspond to 2 "implications" per clause
202
For a 2-SAT problem, when representing it as a graph we use a directed or undirected graph? Why?
Directed. This is a somewhat hand-wavy answer, but we're using the SCC algorithm on the graph, which only makes sense in the context of directed graphs.
203
You have some CNF formula f that defines some 2-SAT problem. You draw the graph out, and discover there is a path from x1 --> !x1. What can you conclude from this? Why?
That f is not satisfiable. Because we end up with a contradiction where with have to set x1=True and x1=False, which obviously can't be done.
(It's easiest to see this by looking at one of the example problems from the lectures, like GR2_7)
204
You have some CNF formula f that defines some 2-SAT problem. You draw the graph out, and discover x1 and !x1 lie in the same SCC. What can you conclude from this? Why?
That f is not satisfiable. Because we end up with a contradiction where with have to set x1=True and x1=False, which obviously can't be done.
(It's easiest to see this by looking at one of the example problems from the lectures, like GR2_7)
205
You have some CNF formula f that contains the variables x1, x2, and x3. You draw the graph out and note that for all i in {1, 2, 3}, x_i and !x_i lie in DIFFERENT SCCs. A few questions:
(a) How many literals are there?
(b) Is f satisfiable? Why or why not?
(a) 2n = 2(3) = 6 total literals
| (b) Yes, it is satisfiable because all x_i and !x_i lie in different SCCs.
206
You have some CNF formula f that contains the variables x1, x2, and x3. You draw the graph out and note that for all i in {1, 2, 3} there is at least one value of i for which x_i and !x_i lie in the same SCC. Is f satisfiable? Why or why not?
No, it is not. In order for f to be satisfiable all the x_i and !x_i must lie in DIFFERENT SCCs.
207
In the context of 2-SAT problems we set the sink SCCs !S' = ______ and the source SCC S' (i.e. the complement) = _____?
True; False
208
In the context of 2-SAT problems we set the source SCC S' = ______ and the sink SCC !S' (i.e. the complement) = _____?
False; True
209
if for all i, x_i and !x_i are in DIFFERENT SCCs then what can we conclude?
That S is a sink SCC and !S is a source SCC (and vice-versa)
210
In the context of 2-SAT, if there is a path from alpha --> beta, then there is a path from !beta --> !alpha (and vice-versa)? (T/F)
True
211
We run the SCC algorithm on some CNF formula f, and the output returns variable assignments for all the variables in the formula? What can we conclude about the formula?
That for all x in X, x and !x lie in DIFFERENT SCCs.
212
We run the SCC algorithm on some CNF formula f, and the output simply returns 'NO'. What can we conclude about the formula and why is this the case?
We can conclude that f is not satisfiable. This must be because there is AT LEAST one x in X for which x and !x lie in the SAME SCC.
213
Say we have a graph that contains multiple subgraphs (i.e. a forest). How would the results of DFS differ from those of BFS on this graph?
DFS would restart the explore subroutine once it explored each of the different subgraphs. BFS, on the other hand, would simply ignore nodes that aren't reachable from the start vertex s (in other words, the distance to nodes that aren't reachable from s in the rest of the forest will all be inf).
214
BFS only works to find shortest paths on graphs whose edges have unit lengths? (T/F)
True.
215
What are the three important properties of trees?
1. Tree on n vertices has n - 1 edges
2. Exactly one path between every pair of vertices
3. Any connected graph G=(V,E) with |E|=|V| - 1 is a tree. (This one is especially important for the cut property)
216
What data structure is used in Kruskal's algorithm?
Disjoint Set (Union-by-Rank)
217
Kruskal's algorithm is an example of a ______ approach?
greedy
218
If a subgraph is connected and has n - 1 edges, what would we call that subgraph?
A tree
219
What is key idea we should take away from the PROOF of the Cut Property?
We can take a tree T and if we add an edge into that tree, e.g. T’ = T ∪ e* - e’, by first adding the edge e* that creates a cycle (because a tree always has n - 1 edges, so if I add an edge into an existing tree, we are guaranteed to get a cycle.) If we then remove any edge from that cycle, we get a new tree T’
220
What is the key idea we should take away from the STATEMENT of the Cut Property?
A minimum weight edge across the cut is part of a MST
221
You have a directed graph G and see an edge e=(zw), and that w is a non-child descendant of z. You run DFS and see that the post(z) > post(w); what type of edge is this?
Forward edge
222
You have a directed graph G and see an edge e=(zw), and you notice that z and w are not descendants or ancestors of each other. You run DFS and see that the post(z) > post(w); what type of edge is this?
Cross edge
223
Per Joves' comment on Ed, how should we view the output of the SCC algorithm?
"You should consider the output of SCC to be just another graph. But each vertex is a ccnum, and each edge uses ccnums."
Source: https://edstem.org/us/courses/22308/discussion/1589332?comment=3603438
224
For a max flow problem, the problem is not solvable if you have cycles present in your graph? (T/F)
False. This is in contrast to the shortest path problem, where having cycles were problematic (at least in the case of things like Dijkstra's algorithm).
225
When building the residual network for a max flow problem, it is important to remove anti-parallel edges first? (T/F)
True.
Source: MF1_13 at end of video
226
In the Ford-Fulkerson algorithm, how do we check if there is a path from s --> t in the residual graph for a max flow problem? If there is no such path, what happens?
Use DFS or BFS. If the path doesn't exist, then the algorithm just outputs the current flow f.
Source: MF1_14
227
What is assumption does the Ford-Fulkerson algorithm make of its inputs that allows it to achieve its specified runtime?
It assumes all capacities are integers. More sophisticated max-flow algorithms like Edmunds-Karp eliminate this requirement.
228
How does the assumption that all the capacities are integers allow the Ford-Fulkerson algorithm for max-flow allow it to achieve its running time?
If we assume that all capacities are integers, then that means flow increases by >= 1 unit per round. So if C = size of the max flow, then we know there will be <= C rounds of the algorithm run.
229
What step in the Ford-Fulkerson algorithm dominates the runtime? What does the final runtime end up being and why?
Finding a path from s --> t using DFS or BFS in each round of the algorithm. Since for Ford-Fulkerson we worst case run <= C rounds, where C=size of the max flow, we end up with a final runtime of O(mC)
230
The Ford-Fulkerson algorithm is a strictly polynomial time algorithm? (T/F) Why or why not?
False. It is pseudo polynomial. This is because the runtime is O(mC), where C=size of the max flow. Making the runtime dependent on the input value for C makes the problem pseudo-polynomial (like the knapsack problem).
231
When does the Ford-Fulkerson algorithm terminate?
When it can no longer augment the path in the residual graph G_f*, i.e. when there is no longer a path from s --> t
232
You are running the Ford-Fulkerson algorithm on a max-flow problem, and it suddenly terminates. What can we conclude? What do we know about the flow f* that it outputs?
That there is no longer an augmenting path in the residual graph G_f*. Based on this we know that f* is a max-flow.
Source: See MF2_2
233
What are the input(s) to the Ford-Fulkerson max-flow algorithm?
1. Flow network: directed graph G=(V,E), with start and end vertices s,t in V and with capacities c_e > 0
Note that for Ford-Fulkerson it requires that all capacities are integer values as well.
234
What are the output(s) to the Ford-Fulkerson max-flow algorithm?
1. Flow f* of max size.
235
In the context of max-flow, how is the SIZE of a flow f defined?
It's the amount of flow either out of start vertex s or in to end vertex t (which have to be equal because of conservation of flow, i.e. size(f) = f_out(s) = f_in(t) )
236
In the context of the "min-cut problem", what is an "st-cut"?
It is a cut that partitions the vertices V into two sets such that s is in L and t is in R
237
How is the capacity of an st-cut defined?
The capacity(L,R) = sum of the edge capacities from L--> R
238
When looking at the capacity of an st-cut, we sum the edge capacities from R --> L? (T/F)
False. We sum from L --> R
239
Checking that there is no path from s-->t in the residual flow network G_f* to find the max flow only works for the Ford-Fulkerson algorithm? (T/F)
False. Checking for the path is actually the second part of the proof for the max-flow = min-cut theorem, so any algorithm that uses this property is guaranteed to be correct because of that general theorem.
240
Compare and contrast the Ford-Fulkerson algorithm and Edmonds-Karp algorithm for max-flow.
Ford-Fullkerson:
1. Find augmenting paths using DFS or BFS
2. Runs in O(mC) time, where C is size of max flow
3. Assumes integer capacities
Edmonds-Karp:
1. Find augmenting paths using BFS
2. Runs in O(n*m^2) time
3. No assumptions on capacities
241
What is the main difference under the hood between the Ford-Fulkerson and Edmonds-Karp algorithm for max-flow?
Edmonds-Karp uses BFS to search for an st-path in the residual flow network graph, whereas Ford-Fulkerson can use DFS or BFS.
242
Say you've drawn a graph G' for a max flow problem that includes all the extra edges required to incorporate demand into the problem. A few questions:
(a) What could you conclusively say about the vertices s' and t' that we "hide" the original graph inside of?
(b) say the size of the flow f
We would know for certain that at a minimum, the max flow would be upper bounded by the flow OUT of s' or by the flow IN to t'.
243
When is a flow "saturated"? Why are saturating flows so important?
If we've fully capacitated all the edges out of s' and into t', then the flow is saturated.
They are important because if G' has a saturating flow, then G has a FEASIBLE flow, and VICE-VERSA.
244
Say you are looking at some flow network graph G'. You find a flow f' that fully capacitates the edges out of s'. What does this imply about the original flow network graph G?
What has happened is that you've found a saturating flow, which implies that G has a feasible flow.
245
Say you are looking at a homework problem of some flow network graph G and someone tells you that they know that G has a feasible flow. What does this imply about G' ?
That G' has a SATURATING flow.
246
What is the runtime of the Edmonds-Karp algorithm?
O(n*m^2) time
247
Max-flow algorithms always use a _________ graph?
directed
248
What are the input(s) to a max-flow problem?
G=(V,E), c, s, t
c: capacities such that c(u,v) > 0 for (u,v) in E
s: source vertex
t: sink vertex
249
What are the output(s) of the max-flow algorithms?
f*
f is a function or vector such that f(u, v) gives a flow of (u,v). It gets updated as the algorithm runs
f* is the MAX-FLOW across G such that sum[f*(..., t)] is maximized
size(f) is the numerical value of flow f calculated as sum[f*(..., t)]
250
You have the output f from some intermediate run of a max-flow algorithm. You lookup the flow across edge e=(A,B) that has a capacity c=6 by running f(A, B), and see that the flow across e at the current iteration is also 6. What can you say about the edge from A to B? Why is this the case?
Hint: Remember that f is a function or vector that returns the flow for some edge e=(u,v)
That is is saturated. Because the current flow across the line is equal to the max capacity of the line.
251
What do we mean (precisely speaking) when we say we are maximizing flow?
f* is the max flow across G such that ∑f*(., t) is maximized; f* is what gets returned from our max-flow algorithms.
Key Idea:
All this is saying is that this function of all flow into the sink vertex is what gets maximized.
252
For a max-flow problem, what does size(f) return?
tl;dr: size(f) = max-flow into the sink t, which is the overall capacity C of the flow network.
size(f) is numerical value of flow f calculated as ∑f*(., t);
equivalently, size(f) = C, i.e. we define the max-flow into the sink t as the overall capacity C of the flow network
253
Ford-Fulkerson algorithm for max-flow must always use DFS for checking for a path from s --> t? (T/F).
If DFS is the only valid choice, why is that? If not, what are the alternatives?
False. Ford-Fulkerson can be thought of as more of a template algorithm for solving max-flow problems, so how we check for that path is left undefined.
Options for path checking then could be: DFS, Explore, or BFS.
254
We're running a max-flow algorithm, and at the end of one of the iterations the algorithm finds that there is still a path from s --> t in the residual flow network G_f. What can we conclude about the residual network, and also about the original flow network G?
It means that there must still be SPARE CAPACITY along the path from s --> t. This means that our algorithm won't terminate yet, because as long as there is a path from s --> t, then we haven't yet found a max-flow for the original flow network G.
255
A graph may have multiple min st-cuts? What is one important result of this? (T/F)
True. As a result, there can be multiple valid solutions to a max-flow problem.
256
If you tried to run the Ford-Fulkerson algorithm on a flow network with non-integer capacities, what might happen?
The algorithm might not terminate.
257
For the Ford-Fulkerson algorithm, there might be rounds during the iterative runs of the algorithm where the flow does not increase? (T/F) What is the implication of the answer?
False. The flow is guaranteed to increase by >= 1 per round.
The implication then is there are at most C rounds, where C is the size of the max flow.
258
Why is the Ford-Fulkerson algorithm only pseudo-polynomial?
Because it runs in O(mC) time, but C (the size of the max flow) has NOTHING to do with the size of the input.
Think about it. The value for C is arbitrary; specifically it is a magnitude. But it doesn't have anything to do with the size of the input flow network G. Since the runtime isn't strictly a function of the input size then, we say it is pseudo-polynomial.
Source: OH Week #6, 1:03:30
259
Is the Ford-Fulkerson algorithm strictly slower than the Edmonds-Karp algorithm? (T/F) Why or why not?
False, because Ford-Fulkerson is pseudo-polynomial. One situation where it could be faster is if C is bounded by n or m. In that case you could argue that since C is at most n or m, then C=n=m, so instead of the usual runtime of O(mC), it would be O(mn) or O(m^2), as opposed to O(nm^2) for Edmonds-Karp.
This is one of those really subtle things that I suspect could be tested on an exam, so remember this one!
260
Between Ford-Fulkerson and Edmonds-Karp algorithm for max flow, which one is faster? Why?
It depends. Edmonds-Karp is generally considered faster, FOR UNBOUNDED CAPACITIES. This is because of the pseudo-polynomial nature of Ford-Fulkerson. In the case where C is bounded to be at most n or m, then Ford-Fulkerson could be faster.
261
You're given a max-flow problem, and some oracle tells you that they know for certain that Ford-Fulkerson will be faster on this problem than Edmonds-Karp. What can you deduce from this about the problem? Why?
That the size of the max flow C is bounded by n or m.
Because of the pseudo-polynomial nature of Ford-Fulkerson. In the case where C is bounded by n or m, we've fixed C so that it is no longer a magnitude and is instead directly bounded by the size of the input.
262
What is a "bridge" in a graph? What type of graphs do they apply to?
Any edge that disconnects the graph. They apply to undirected graphs.
263
What would be an equivalent way of running the topological sort algorithm on a DAG?
Run DFS on the graph and then order the post nums in DESCENDING order (i.e. largest to smallest).
Note: In practice, just say "Run topological sort on G". I really just created this question to reinforce the conceptual connection between topological sorting and post numbers from DFS runs.
264
The vertex with the highest post order number and lowest post order number are guaranteed to be the ONLY source and sink in a DAG? (T/F)
False. There may be multiple sources and sinks.
265
The 2SAT algorithm is O(n + m) for any number of literals? (T/F)
False. It is only O(n + m) if the problem can be reduced to where each clause has at most 2 literals.
266
You have a directed graph G and run the SCC algorithm. You find that the G_scc has the same number of vertices as the original graph G. What can we conclude about the graph?
If the number of SCCs = n in the original graph, then there must not have been any cycles present in the graph. Hence every vertex in the original graph has now become a singleton SCC in G_scc.
267
You have a directed graph G and run the SCC algorithm. You find that the G_scc has fewer vertices than the original graph G. What can we conclude about the graph?
There must have been at least one cycle present such that at least or more of the nodes were compressed into the same SCC.
268
After running the SCC algorithm, what would the runtime be to count how many SCCs you have? Why?
O(n). Because in the worst case if no cycles were present in the original graph then every vertex in G would become a singleton SCC in G_scc, so in worst case you would have to count n vertices.
269
You can use BFS to check if some vertex s can reach another vertex v? (T/F). If you can, how would you do this?
True. You would run, BFS(G, s) and then check if dist[v] = inf. If dist[v] != inf, then a path exists, otherwise False. (We check for inf because this is how the distances are initialized in BFS.)
270
At a high level, what is the "cycle property" of an MST?
The heaviest edge of any cycle can not be part of any MST.
