Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS-6515 > Exam2-Discord > Flashcards

Exam2-Discord Flashcards

1
Q

What is a DAGs?

A

Directed, Acyclic Graphs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are Strongly Connected Components?

A

subsets of vertices in a directed graph such that there is a directed path from any vertex in the subset to every other vertex in the same subset.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are Sources?

A

In a directed graph, a source is a vertex in a directed graph that has no incoming edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are Sinks?

A

In a directed graph, a sink is a vertex in a directed graph that has no outgoing edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are Trees?

A

is a specific type of undirected graph that is connected and acyclic.In a directed graph, each vertex, except the root, has one incoming edge (from its parent) and may have multiple outgoing edges (to its children). The tree will be acyclic.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a MST?

A

MST is Minimum Spanning Tree. a connected, undirected graph is a tree that spans all the vertices of the graph, with the minimum possible total edge weight

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are Flow Networks?

A

is a directed graph in which each edge has a capacity and a flow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

In runtime, O(m+n), what does m signify and what does n signify?

A

m signify edgesn signify vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

In runtime O(C m), what does C signify?

A

Size of the max flow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What algorithm does Ford-Fulkerson use internally?

A

DFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What algorithm does SCC use internally?

A

2 DFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What algorithm does Edmond-Karp use internally?

A

BFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Why would use Djistra’s over Belman Ford and Floyd Warshall?

A

Dijkstra’s are more efficient for postive weights only.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Why would use Belman Ford and Floyd Warshall over Djikstra’s?

A

Bellman Ford and Floyd Warshall works on negative weights, whereas Djikstra’s does not.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Why would you use Floyd Warshall over Bellman Ford?

A

Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Why would you use Bellman Ford over Floyd Warshall ?

A

Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex to all other vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Why would you choose Kruskal’s over Prim or vice versa?

A

It does not matter which algorithm you use. Choose one which is easier to remember. Reference: https://edstem.org/us/courses/50892/discussion/4313106?comment=10048285

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Why would you use DFS over BFS or vice versa?

A

BFS is good for finding the shortest path for unweighted graphs from a starting vertex using dist(u). DFS is good at topologically sorting a DAG and finding connected components.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Do Kruskal’s and Prims algorithm work on directed and undirected graphs?

A

No. They don’t work on directed graphs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Why would you choose Explore over DFS?

A

Explore takes a starting vertex as an input. Explore only visits all reachable vertices from the starting vertex. We’ll get a visited array with reachable vertices marked as TRUE and non-reachable vertices marked as FALSE. whereas DFS explores all vertices regardless if they are reachable from the starting vertex. The visited array for DFS will always return TRUE for all vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the Cut Property?

A

if edges X are part of a minimum spanningtree of graph G, we can pick any subset of nodes S for which X doesnot cross between S and V-S, and let e be the lightest edge acrossthis partition. Then X U {e} is a part of some MST.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the difference between Ford-Fulkerson and Edmonds-Karp algorithm?

A

Edmonds-Karp only needs positive capacities whereas Ford-Fulkerson requires positive integer capacities.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are the different types of graphs?

A
  • connected vs disconnected* undirected vs directed* cycle vs acyclic* weighted vs unweighted * positive vs negative weights
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the runtime of:DFS Runtime

A

O(n+m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is the runtime of:Explore Runtime
O(n+m)
26
What is the runtime of:BFS Runtime
O(n + m)
27
What is the runtime of:SCC Runtime
O( (m+n) log n)O(m log n) if strongly connected
28
What is the runtime of:Bellman Ford
O(nm)
29
What is the runtime of:Floyd Warshall
O(n^3)
30
What is the runtime of:Kruskal's
(m log n)
31
What is the runtime of:Prims
O(m log n)
32
What is the runtime of:2-SAT
O(n+m)
33
What is the runtime of:Ford Fulkerson
O(C m)
34
What is the runtime of:Edmonds-Karp
O(nm^2)
35
What is the runtime of:Explore on an undirected graph
O(m+n) simplifies to O(m)
36
What is the runtime of:DFS on a connected graph
O(m+n) simplifies to O(m)
37
What is the runtime of:Explore on connected MST
O(m+n)
38
What is the runtime of:DFS on unconnected MST
O(m+n)
39
What is the runtime of:traversing a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
40
What is the runtime of:reversing a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
41
What is the runtime of:copying a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
42
What is the runtime of:iterating, checking, reading, removing, working on all vertices (or subset)
O(n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
43
What is the runtime of:checking, reading, or removing one edge
O(n) or O(m)Reference: https://edstem.org/us/courses/50892/discussion/4320477
44
What is the runtime of:iterating, checking, reading, removing, working on all edges
O(n+m)
45
What is the runtime of:Running an O(m+n) black-box algorithm on a MST which is connected
O(m)
46
What is the runtime of:Running an O(m+n) black-box algorithm on a Max Flow which is connected
O(m)
47
What is the runtime of:Accessing an edge property such as a weight
O(1)
48
Name graph algorithms that are used for:Traversing a Graph
DFS, Explore, BFS
49
Name graph algorithms that are used for:Getting Components
SCC
50
Name graph algorithms that are used for:Getting Shortest Paths
Dijkstra's, Bellman Ford, Floyd Warshall
51
Name graph algorithm that are used for:Finding MSTs
Kruskal's, Prims
52
Name graph algorithm that are used for:finding an existing path
2-SAT
53
Name graph algorithms that are used for: Finding the Max Flow
Ford-FulkersonEdmonds-Karp
54
What is the best algorithm for determining the shortest path of graph G that is weighted with positive weights?
Djikstra's
55
What are the best algorithms for determining the shortest path of graph G that is weighted with negative weights?
Bellman Ford or Floyd Warshall
56
What are the best algorithms for determining the best capacity?
Ford-Fulkerson and Edmonds-Karp
57
What is the best algorithm to convert a graph to a topologically sorted DAG?
SCC
58
What is the best algorithm to find the shortest path from all vertices of a directed, weighted graph with negative weights?
Floyd Warshall
59
What is the best algorithm to find the shortest path from a given vertex of a directed, weighted graph with negative weights?
Bellman Ford
60
DFS: What is the input, output, and variables we have access to?
Input: G = (V, E) Output:* A topological sort on a DAG* undirected graph: ccnum (connected component number)* directed graph: a list of connected componentsAccess to:* prev array* pre array* post array
61
Explore: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* visited(u) - visited array which is set to TRUE for all vertices reachable from vAccess to:* ccnum array (ccnum[])* previously visited array (visited[]) * An array of vertices before a given vertex. * Used by Explore and required for DFS.
62
BFS: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u
63
Djikstra's: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u
64
Bellman Ford: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* The shortest path from vertex s to all other vertices.Access to:* Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *]. * We can only find negative weight cycles that can be reached from starting vertex s.
65
Floyd-Warshall: What is the input, output, and variables we have access to?
Input:* G = (V, E)Output:* The shortest path from all vertices to all other verticesAccess to:* We can detect negative weight cycles by checking the diagonals (T[n, i, i]).
66
SCC: What is the input, output, and variables we have access to?
Input:* G = (V, E)Output:* meta-graph (DAG) that contains the connected components* Topological sorting of the meta-graph * With a source SCC first and a sink SCC lastAccess to:* ccnum[] - strongly connected components produced from the 1st DFS run
67
Kruskal's: What is the input, output, and variables we have access to?
Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the edges E
68
Prim: What is the input, output, and variables we have access to?
Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the prev[] array
69
2-SAT: What is the input, output, and variables we have access to?
Input:* A Boolean formula in 2-CNF is represented as a set of clauses where each clause is a disjunction of exactly two literals.Output:* A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it is satisfiable, the algorithm may also provide a satisfying assignment of variables.
70
Ford-Fulkerson: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G
71
Edmonds-Karp: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G

CS-6515 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions