Brainscape's Knowledge GenomeTM

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


See full index

Algorithms > Key Concepts > Flashcards

Key Concepts 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 edges
n 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 black-box algorithms do 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.

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

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.

19
Q

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

A

No. They don’t work on directed graphs.

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.

21
Q

What is the Cut Property?

A

asserts if (and only if) an edge is of minimum weight on any cut, then the edge is part of some MST.

This property is used to include edges

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.

23
Q

What are the different types of graphs?

A
  • connected vs disconnected vs strongly connected
  • undirected vs directed
  • cycle vs acyclic
  • weighted vs unweighted
    * positive vs negative weights
24
Q

What is the Cycle Property?

A

states if e is the unique heaviest edge in any cycle of G, then e cannot be a part of any MST

This property is used to exclude edges.

25
Q

In an undirected graph, what are bridges?

A

An edge in an undirected connected graph is a bridge if removing it disconnects the graph.

26
Q

In an undirected graph, what are leaves?

A

A node in a graph is a leaf (or a leaf node) if it has degree one and the only edge associated to the node is either undirected or is directed to it.

In the example, 1, 2, 3, and 6 are leaves

27
Q

What assumptions can we make with flow networks?

A

They are connected, weighted, and directed graphs.

28
Q

What are the properties of a Tree?

A

Property 2: A tree on n nodes has n - 1 edges

Property 3: Any connected, undirected graph G = (V, E) with |E| = |V| - 1 is a tree

Property 4: An undirected graph is a tree if and only if there is a unique path between any pair of nodes

Reference: DPV book pg. 129 under section 5.1.1

29
Q

Which of the following graphs do SCC work on?

undirected graphs
directed graphs

A

directed graphs

30
Q

What does 2-SAT do differently from other algorithms?

A

While other problems involve reducing to a Graph, 2Sat involves reducing to a 2-satisfiability CNF into a graph.

31
Q

Both BFS and Dijkstra’s find the shortest path. What are the differences?

A

BFS tells us how many edges from s (does not consider edge weights). O(m+n)

Dijkstras considers edge weights. O(n+m) log n)

32
Q

What does BFS return if vertex s is unable to reach a vertex v?

A

inf

Reference: Joves Office Hour

33
Q

Which version of Dijkstra’s do we use in the lectures?

A

Dijkstra’s using binary heap.

Reference: Joves Office Hour

34
Q

What does Dijkstra’s return if vertex is unable to reach a vertex v?

A

inf

Reference: Joves Office Hour

35
Q

Do Kruskal’s and Prims work with negative edge weights? Or only positive edge weights?

A

They work with both negative and positive edge weights.

Reference: Joves Office Hour

Algorithms (14 decks)

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