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
Q

What is the runtime of:Explore Runtime

A

O(n+m)

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

What is the runtime of:BFS Runtime

A

O(n + m)

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

What is the runtime of:SCC Runtime

A

O( (m+n) log n)O(m log n) if strongly connected

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

What is the runtime of:Bellman Ford

A

O(nm)

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

What is the runtime of:Floyd Warshall

A

O(n^3)

30
Q

What is the runtime of:Kruskal’s

A

(m log n)

31
Q

What is the runtime of:Prims

A

O(m log n)

32
Q

What is the runtime of:2-SAT

A

O(n+m)

33
Q

What is the runtime of:Ford Fulkerson

A

O(C m)

34
Q

What is the runtime of:Edmonds-Karp

A

O(nm^2)

35
Q

What is the runtime of:Explore on an undirected graph

A

O(m+n) simplifies to O(m)

36
Q

What is the runtime of:DFS on a connected graph

A

O(m+n) simplifies to O(m)

37
Q

What is the runtime of:Explore on connected MST

A

O(m+n)

38
Q

What is the runtime of:DFS on unconnected MST

A

O(m+n)

39
Q

What is the runtime of:traversing a full graph

A

O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477

40
Q

What is the runtime of:reversing a full graph

A

O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477

41
Q

What is the runtime of:copying a full graph

A

O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477

42
Q

What is the runtime of:iterating, checking, reading, removing, working on all vertices (or subset)

A

O(n)Reference: https://edstem.org/us/courses/50892/discussion/4320477

43
Q

What is the runtime of:checking, reading, or removing one edge

A

O(n) or O(m)Reference: https://edstem.org/us/courses/50892/discussion/4320477

44
Q

What is the runtime of:iterating, checking, reading, removing, working on all edges

A

O(n+m)

45
Q

What is the runtime of:Running an O(m+n) black-box algorithm on a MST which is connected

A

O(m)

46
Q

What is the runtime of:Running an O(m+n) black-box algorithm on a Max Flow which is connected

A

O(m)

47
Q

What is the runtime of:Accessing an edge property such as a weight

A

O(1)

48
Q

Name graph algorithms that are used for:Traversing a Graph

A

DFS, Explore, BFS

49
Q

Name graph algorithms that are used for:Getting Components

A

SCC

50
Q

Name graph algorithms that are used for:Getting Shortest Paths

A

Dijkstra’s, Bellman Ford, Floyd Warshall

51
Q

Name graph algorithm that are used for:Finding MSTs

A

Kruskal’s, Prims

52
Q

Name graph algorithm that are used for:finding an existing path

A

2-SAT

53
Q

Name graph algorithms that are used for: Finding the Max Flow

A

Ford-FulkersonEdmonds-Karp

54
Q

What is the best algorithm for determining the shortest path of graph G that is weighted with positive weights?

A

Djikstra’s

55
Q

What are the best algorithms for determining the shortest path of graph G that is weighted with negative weights?

A

Bellman Ford or Floyd Warshall

56
Q

What are the best algorithms for determining the best capacity?

A

Ford-Fulkerson and Edmonds-Karp

57
Q

What is the best algorithm to convert a graph to a topologically sorted DAG?

A

SCC

58
Q

What is the best algorithm to find the shortest path from all vertices of a directed, weighted graph with negative weights?

A

Floyd Warshall

59
Q

What is the best algorithm to find the shortest path from a given vertex of a directed, weighted graph with negative weights?

A

Bellman Ford

60
Q

DFS: What is the input, output, and variables we have access to?

A

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
Q

Explore: What is the input, output, and variables we have access to?

A

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
Q

BFS: What is the input, output, and variables we have access to?

A

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
Q

Djikstra’s: What is the input, output, and variables we have access to?

A

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
Q

Bellman Ford: What is the input, output, and variables we have access to?

A

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
Q

Floyd-Warshall: What is the input, output, and variables we have access to?

A

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
Q

SCC: What is the input, output, and variables we have access to?

A

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
Q

Kruskal’s: What is the input, output, and variables we have access to?

A

Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the edges E

68
Q

Prim: What is the input, output, and variables we have access to?

A

Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the prev[] array

69
Q

2-SAT: What is the input, output, and variables we have access to?

A

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
Q

Ford-Fulkerson: What is the input, output, and variables we have access to?

A

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
Q

Edmonds-Karp: What is the input, output, and variables we have access to?

A

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.
© 2024 Bold Learning Solutions. Terms and Conditions