Brainscape's Knowledge GenomeTM

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


See full index

Graduate Algorithms > Exam 2 - Graphs > Flashcards

Exam 2 - Graphs Flashcards

1
Q

What algorithm would I use to topologically sort a DAG?

A

DFS

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

What algorithm would I use to find all of the connected components in a graph?

A

DFS

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

Can DFS be used on directed graphs or undirected graphs?

A

It can be used on both

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

Can DFS be used on DAGs

A

Yes

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

What is the runtime of DFS?

A

O(n+m)

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

What are the inputs of DFS?

A

G = (V,E)

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

What are the outputs of DFS?

A

ccnum[] the array of connected component numbers
prev[] the previous array which can be used for backtracking to find a path
pre[] the preorder numbers for each vertex
post[] the postorder numbers for each vertex, which can be used for topological sorting

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

What algorithm can I use to find which nodes are reachable from S?

A

Explore subroutine

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

What are the inputs of the Explore subroutine?

A

G = (V,E)
Starting vertex v from V

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

What is the output of the Explore subroutine?

A

visited[]
array of vertices reached before a given vertex
true for all vertices reachable from v

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

What is the runtime of the Explore subroutine?

A

O(m+n)

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

Can you use BFS on a graph with edge weights?

A

No

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

What kind of graphs can BFS be used on?

A

Unweighted, both directed and undirected

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

What are the inputs of BFS?

A

G = (V,E)
Start vertex v from V

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

What does BFS do?

A

Performs a breadth-first search of the graph from a starting vertex, finding the number of edges from v to any other vertex

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

What are the outputs of BFS?

A

dist[] for all vertices u reachable from v, dist[u] is the length of the number of edges in the shortest path from v to u – infinite if unreachable

prev[] vertex preceding u in the shortest path from v to reachable vertex u

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

What is the runtime of BFS?

A

O(m+n)

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

What graph trait can Dijkstra’s algorithm not handle?

A

Negative edge weights

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

What algorithm would I use to find the shortest distance from a source vertex to all other vertices in a graph with nonnegative edge weights?

A

Dijkstra’s algorithm

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

What are the inputs to Dijkstra’s algorithm?

A

G = (V,E)
Start vertex v in V
w_e for e in E, non negative weights

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

What are the outputs of Dijkstra’s algorithm?

A

dist[] shortest distance between vertex v and reachable vertex u, or infinity if not reachable
prev[] vertex preceding u in the shortest path from v to reachable vertex u

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

What is the runtime of Dijkstra’s algorithm?

A

O((m+n) log n)

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

What algorithm would I use if I wanted to find the shortest distance from a source vertex to all other vertices in a graph that may contain negative edge weights?

A

Bellman-Ford

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

What are the inputs to the Bellman-Ford algorithm?

A

G = (V,E)
Start vertex s in V
w_e for e in E

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

What is the output of the Bellman-Ford algorithm?

A

Shortest path from vertex s to all other vertices

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

How does the Bellman-Ford algorithm detect negative weight cycles that can be reached from starting vertex s?

A

Comparing the last iteration T[n,] to T[n-1,] and seeing if any distances got shorter despite not exploring any further

27
Q

What is the runtime of the Bellman-Ford algorithm?

A

O(m*n)

28
Q

What algorithm would I use if I wanted to find the shortest path from all vertices to all other vertices in a graph?

A

Floyd-Warshall

29
Q

Does Floyd-Warshall allow negative weights?

A

Yes

30
Q

What are the inputs of the Floyd-Warshall algorithm?

A

G = (V,E)
w_e for e in E

31
Q

What is the output of the Floyd-Warshall algorithm?

A

The shortest path from all vertices to all other vertices

32
Q

How does the Floyd-Warshall algorithm detect negative weight cycles?

A

Checking the diagonals T[n, i, i] to see if any vertex has a path shorter than zero to itself

33
Q

What is the runtime of the Floyd-Warshall algorithm?

A

O(n^3)

34
Q

What is the output of the Strongly Connected Components algorithm?

A

Metagraph (DAG) containing the strongly connected components
A topological sorting of the metagraph, with source SCCs first, and sink SCCs last
Also the connected component number array from the first DFS run in the algorithm

35
Q

Can the SCC algorithm be used on undirected graphs?

A

No, directed graphs don’t have strongly connected components

36
Q

What is the runtime of the SCC algorithm?

A

O(m+n)

37
Q

What algorithm would I use to find an MST, using a union-find data structure?

A

Kruskal’s algorithm

38
Q

What algorithm would I use to find an MST, using a fibonacci heap?

A

Prim’s algorithm

39
Q

What are the inputs to Kruskal’s/Prim’s algorithms?

A

Connected, undirected graph G = (V,E)
w_e edge weight for each e in E

40
Q

What is the output of Kruskal’s algorithm?

A

An MST, defined by edges from E

41
Q

What is the output of Prim’s algorithm?

A

An MST, defined by the prev[] array

42
Q

What is the runtime of Kruskal’s/Prim’s algorithms?

A

O(m log n)

43
Q

What kinds of graphs can Kruskal’s/Prim’s algorithms be used on?

A

Connected, undirected, weighted graphs

44
Q

What does the 2-SAT algorithm do?

A

Takes a CNF with all clauses of size <= 2 and returns a satisfying assignment if it exists

45
Q

What is the input of the 2-SAT algorithm?

A

A 2-CNF boolean formula

46
Q

What is the output of the 2-SAT algorithm?

A

Whether the input formula can be satisfied, and if it can, what values satisfy it.

47
Q

How does the 2-SAT algorithm work?

A

It uses a directed graph to represent implications from the formula, and then checks the SCCs to see if there are any contradictions.

48
Q

What is the runtime of the 2-SAT algorithm?

A

O(m + n)
m is number of clauses
n is number of variables

49
Q

What algorithm would I use to find the max flow of a network with integer edge capacities?

A

Ford-Fulkerson

50
Q

Which algorithms have we covered that are greedy algorithms?

A

Ford-Fulkerson and Edmonds-Karp

51
Q

What are the inputs to the Ford-Fulkerson and Edmonds-Karp algorithms?

A

G = (V,E)
Flow capacity c for all edges
Source node s
Sink node t

52
Q

What are the outputs of the Ford-Fulkerson and Edmonds-Karp algorithms?

A

The maximum flow, and effectively the residual network because it can easily be recreated with G and the max flow

53
Q

What algorithm would I use to find the max flow of a network with noninteger edge capacities?

A

Edmonds-Karp

54
Q

How is Edmonds-Karp different from Ford-Fulkerson?

A

It uses BFS instead of DFS

55
Q

What is the runtime of Ford-Fulkerson?

A

O(C*m)
C is maximum flow of network
m is number of edges

56
Q

What is the runtime of Edmonds-Karp?

A

O(n * m ^ 2)
n is number of vertices
m is number of edges

57
Q

When should I choose Ford-Fulkerson over Edmonds-Karp?

A

When we know the weights are integers and we know the maximum weight size is limited

58
Q

What is the adjacency matrix representation of a graph?

A

An n x n matrix (where n is number of vertices) containing either true or false at each entry, where an entry at u,v represents whether there exists an edge from u to v

59
Q

What is the adjacency list representation of a graph?

A

A linked list for each vertex, holding the ids of the vertices that it has an outgoing edge to

60
Q

What is a tree edge?

A

An edge that was created when visiting an unexplored vertex

61
Q

What is a forward edge?

A

An edge that leads from a node to a nonchild descendant

62
Q

What is a back edge?

A

An edge that leads to an ancestor

63
Q

What is a cross edge?

A

An edge that leads to a previously completely explored node that is neither a descendant nor an ancestor

64
Q

Graph G has a cycle if its DFS tree has a ____ edge

A

back

Graduate Algorithms (6 decks)

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