Brainscape's Knowledge GenomeTM

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


See full index

-TierI Interview Prep > More graph Algos > Flashcards

More graph Algos Flashcards

1
Q

Forest

A

is an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees

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

Kruskal’s algo for a connected (+ edge weighted + undirected) graph does what?

A

Finds a minimum spanning tree

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

Is kruskals greedy or Non greedy

A

Greedy

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

What is a spanning tree?

A

(Pertains to undirected graphs). a subgraph that is a tree which includes all of the vertices of The graph

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

Prim’s algo benefits vs other MST algos

A

for graphs that are sufficiently dense, Prim’s algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

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

List the three basic greedy algorithms to find an MST

A

Prim’s (Jarnik’s), Kruskal’s, Borůvka’s (Sollin’s) algorithms

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

Kruskals

A

create a forest F (a set of trees), where each vertex in the graph is a separate tree
create a set S containing all the edges in the graph
while S is nonempty and F is not yet spanning
remove an edge with minimum weight from S
if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree
At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

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

Topological sort definition

A

a linear ordering of a graph’s vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

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

Canonical use case of topological sort

A

in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer)

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

List names of Topological sort implementations - Kahn, Tarjan’s DFS solution, PRAM with adjacency matrix squaring, parallelized Khan with a distributed memory machine

A

Kahn, Tarjan (DFS), adjacency matrix squaring on a PRAM, parallelized Kahn on a distributed memory machine

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

High level how to quickly compute shortest path thru weighted directed a cyclic graph

A

Use topological sort

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

Low level implementation of finding shortest paths on directed acyclic weighted graph

A

…

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

When are topological ordering a impossible

A

When there are cycles

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

DAG

A

Directed acyclic graph

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

Known Time complexity of finding a topological sorting of a DAG

A

O(n)

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

FAS stands for

A

Feedback Arc Set

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

Feedback Arc set is aka

A

Feedback Edge Set

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

Feedback arc set

A

set of edges which, when removed from the graph, leaves an acyclic graph. Put another way, it is a set containing at least one edge of every cycle in the graph.

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

What algorithm do you use to find shortest path from a source to all vertices?

A

Djikstra’s

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

Algo name for shortest path from every vertex to every other vertex

A

Floyd Marshall

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

Memory complexity of sum of length of all adjacency lists for directed graph vs undirected graph

A

|E| vs 2|E|

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

For both directed and undirected graphs the memory complexity of the adjacency list representation is

A

O(V + E)

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

disadvantage of adjacency-list representation for edges

A

there is no quicker way to determine if a given edge (u, v) is present in the graph than to search for v in the adjacency list Adj[u]. which worst case could be O(V) if u is connected to all vertices

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

List and compare two alternatives to adjacency lists to represent edges

A

1) have Adj[u] be a hash table containing the vertices v for which (u, v) ∈ E. Expected time is O(1). Worst case time is O(V) (if you get a lot of hash collisions (but is that really even likely???)). 2) have Adj[u] be an array that you sort and then during look-up you perform binary search for an expected and worst case time of O(lg V)`

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

Djikstra binary heap implementation time complexity

A

Theta((|E|+|V|)log|V|) time complexity,

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

Djikstras does what?

A

Finds the shortest path to every node in the (weighted-edge) graph from a single source

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

Bellman Ford does what?

A

Similar to Dijkstra’s algorithm, the Bellman-Ford algorithm 1)works to find the shortest path between a given node and all other nodes in the graph. Though it is 2)slower than the former, Bellman-Ford makes up for its a disadvantage with its versatility. Unlike Dijkstra’s algorithm, Bellman-Ford is capable of 3) handling graphs in which some of the edge weights are negative.
4) It’s important to note that if there is a negative cycle – in which the edges sum to a negative value – in the graph, then there is no shortest or cheapest path. Meaning the algorithm is prevented from being able to find the correct route since it terminates on a negative cycle. 5)Bellman-Ford is able to detect negative cycles and report on their existence.

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

Floyd Marshal does what?

A

The Floyd-Warshall stands out in that unlike djikstra and bellman Ford it is not a single-source algorithm. Meaning, it calculates the shortest distance between every pair of nodes in the graph, rather than only calculating from a single node

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

What is Floyd marshal very useful for?

A

when it comes to generating routes for multi-stop trips as it calculates the shortest path between all the relevant nodes. For this reason, many route planning software’ will utilize this algorithm as it will provide you with the most optimized route from any given location. Therefore, no matter where you currently are, Floyd-Warshall will determine the fastest way to get to any other node on the graph.

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

Johnson’s algorithm works best when?

A

With sparse graphs

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

Can Floyd warshal detect the presence of a negative weight cycle ?

A

Yes

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

How does Floyd warshal detect the presence of a negative weight cycle?

A

…

33
Q

Floyd warshal time complexity

A

O(V^3)

34
Q

Johnson’s runtime complexity

A

O(V^2 * logV + |V||E|)

35
Q

How does Iohnsons work high level?

A

it uses two other shortest path algorithms as subroutines. It uses Bellman-Ford in order to reweight the input graph to eliminate negative edges and detect negative cycles. With this new, altered graph, it then uses Dijkstra’s shortest path algorithm to calculate the shortest path between all pairs of vertices. The output of the algorithm is then the set of shortest paths in the original graph.

36
Q

Bellman-Ford time complexity

A

O(VE)

37
Q

Djikstra Fibonacci heap time complexity

A

O(|E|+|V|log| V|)

38
Q

In graphs how does the time complexity w.r.t E relate to V

A

E in worst case is V^2

39
Q

What complexity class is determining whether a certain edge is in the MST?

A

P

40
Q

What complexity class is determining whether a total weight (of an MST) exceeds a certain value?

A

P

41
Q

MST

A

minimum spanning tree

42
Q

What is considered a dense graph?

A

|E|/|V| > log log log |V|

43
Q

what is the dynamic MST problem

A

concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex

44
Q

maximum spanning tree

A

a spanning tree with weight greater than or equal to the weight of every other spanning tree

45
Q

how to find a maximum spanning tree?

A

Such a tree can be found with algorithms such as Prim’s or Kruskal’s after multiplying the edge weights by -1 and solving the MST problem on the new grap

46
Q

The degree constrained minimum spanning tree

A

a minimum spanning tree in which each vertex is connected to no more than d other vertices, for some given number d.

47
Q

The capacitated minimum spanning tree

A

a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than a c nodes. c is called a tree capacity.

48
Q

Steiner tree problem

A

the problem of finding a minimum tree that spans the given subset of vertices (aka the terminals). this minimum tree may contain vertices that were not provided as terminals

49
Q

What does Tarjan’s algorithm do?

A

an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph

50
Q

SCCs

A

Strongly connected components

51
Q

Strongly connected meaning

A

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first (of course the path can be more than one edge long). Equivalently, a strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected.

52
Q

Daniel Larkin 2014

A

They concluded that d-ary heaps such as binary heaps are faster than all other heap implementations when the decrease-key operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when decrease-key is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like Fibonacci heaps that are theoretically more efficient. [is this conclusion just for djikstras? Or heaps in general?]

53
Q

Mo Chen 2007

A

examined priority queues specifically for use with Dijkstra’s algorithm and concluded that in normal cases using a d-ary heap without decrease-key (instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees.

54
Q

Djikstras implementation w PQ w decreaseKey

A

Djikstra(adj, s){ // s = sourceKey

Dist = new PQ()
keys = Object.keys(adj)
For (let i = 0; i < keys.length; i ++) {
 key = keys[i]
dist.insert(key, NUMBER.MAX_SAFE_INTEGER)
Unvisited.push(keys[i])
}

Dist.decreaseKey(s,0)
While(x = dist.extractMin()){

Neighbors = adj[x]
For(let i =0; I < neighbors.length;I++){
 n = neighbors[i]
 if (dist.get(x) + n.weight < dist[n.label]) {
dist[n.label] = dist[x] + n.weight
Path[n.label] = x
}
}
55
Q

Djiksyra with priority queue verbal explanation

A

You should use priority queue where the vertex with the shortest distance from the starting vertex will get the highest priority. Initially, all vertices will have the shortest distance of infinity and the starting vertex will have the shortest distance 0.

Start by inserting of all vertices (with its edges) from the graph inside the PQ. Remove vertex from the PQ and explore all its edges. Compare the shortest distances with all adjacent vertices and if any distance is less than the shortest distance on the current vertex, update adjacent vertex shortest distance inside the PQ. Continue while PQ is not empty. Vertices which have no edges will finish with the shortest distance of infinity because it is not possible ‘get to them’ from the starting vertex. However, they will be still removed from the PQ.

56
Q

What happens if you don’t relax the edges of the unvisited node that has the least distance of all the unvisited nodes?

A

I’m not sure. I think it breaks some loop invariant that the logic of djikstra depends on. I’m not sure of the exact nature of the incorrect output that would result, but i might test it out one of these days

57
Q

What is a simple way to emulate the behavior of the decrease-key operation of a priority queue without actually implementing such a method?

A

(Used in djikstra’s)

To decrease the key of a node, just insert that node again in the pq, such that there are now 2+ nodes with the same key in the queue, but such that the node with such key and the lowest value will now in the future be popped first from the queue

When popping (aka polling) nodes from the queue, when a node is polled, as part of preprocessing you add that key to a “visited” list, and in the future when polling nodes, if the polled node’s key already exists in the visited list, you skip processing that node and poll the next node to preprocess+process it

58
Q

Speed of prim’s vs kruskal’s vs Boruvka’s algorithm’s?

A

equally asymptotically fast for sparse graphs, but slower than algorithms; Prim’s can be made to run in linear time on dense graphs

59
Q

SoftHeap

A

a kind of priority queue that gives us an optimal

trade-off between accuracy and speed.

60
Q

Pettie’s “contractibility”

A

A subgraph C is said to be DJP-contractible with respect to G if after executing the DJP algorithm on G for some number of steps, with a suitable
start vertex in C, the tree that results is a spanning tree for C. [ https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf]

61
Q

How can one provably identify edges in the MSF? How can one provably identify edges NOT in the MSF?

A

by using the cut property; by using the cycle property

62
Q

The cut property states

A

that the lightest edge crossing any partition of the vertex set into two parts must belong to the MSF.

63
Q

the cycle property states

A

that the heaviest edge in any cycle in the graph cannot be in the MSF.

64
Q

contracting in graphs

A

https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf

65
Q

nominal density of a graph

A

(during contraction - e.g. in Pettie’s algorithm)

y is the ratio m/n’, where m, as usual, is the number of edges in the original graph, and n’ is the number of vertices in the current graph

[https://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf]

66
Q

How to find a cycle in a directed graph?

A

Technique 1 (using colors). Use enum WHITE|GRAY|BLACK or UNVISITED | VISITING | VISITED

Do DFS:

hasCycle(n, adj, nodes) {

visiting[n.label] = true // use separate data structure if you can’t just add properties on the node itself

for (let child of adj[n.label]) {
 if (visiting[child.label]) {
    return true // if the connection to this child itself forms a cycle return true 
 } else {
// or if any grandchildren+ forms a cycle
    if (hasCycle(nodes[sister.label], adj, nodes)) { //))
       return true
 }
}
return false
}

}

——-
Technique 2

//doesn’t check if this node forms a particular cycle, but rather if one of its neighbors or neighbors’ neighbors forms the cycle (I guess taking into account the history of the path we are doing)
function hasCycle(n, adj, path: SearchableStack) {

path.push(n.label)
for (let x of adj[n]) {
if (path.contains(n.label)) {

67
Q

SPFA aka

A

Shortest Path Faster Algorithm

68
Q

SPFA is an improvement of what algorithm

A

Bellman Ford; it is queue optimized Bellman Ford

69
Q

SPFA is believed to work well when?

A

random sparse graphs and is particularly suitable for graphs that contain negative-weight edges

70
Q

SPFA worst case running time

A

O(|V| |E|), same as Bellman Ford’s

71
Q

SPFA average runtime

A

Experiments suggest that the average running time is O(|E|) , and indeed this is true on random graphs, but it is possible to construct sparse graphs where SPFA runs in time Omega (|V|^{2})} like the usual Bellman-Ford algorithm

72
Q

Dual priority queue version of djikstra’s performance

A

has a significant overhead in the constant factor, and hence is quite slow in in-core execution, though it performs by far the best on sparse graphs out-of-core. [mo Chen 2007]

73
Q

IDM PQ

A

A priority queue that only supports insert and delete-min, as opposed to also supporting decrease-key

74
Q

A DK PQ

A

A priority queue that includes a decrease key operation

75
Q

A second alternative to a DK PQ

A

If there is no explicit decrease key operation, if you have access to a find operation you can find, remove, and then add again.

76
Q

How does djikstra algorithm work/perform correctly when it is used with a priority queue that doesn’t have a decrease key operation?

A

When you pop the min node x from the priority queue, you process it. Part of it is adding any of x’s neighbors to the priority queue if the path for that neighbor n thru x has a smaller weight (aka cost) than n used to have.

Now there are two categories of questions that you may have: 1) what if node C was added to the PQ with weight 10 ( A->C=10) but then was also added to the PQ again with (A->B=4, B->C=4) giving it a better candidate weight of 8. Since node C is now in the queue twice, is the algorithm still going to function correctly? Well, to make sure it still functions correctly, you need to mark nodes visited when they are removed from the priority queue, and never do the processing on a node being removed that has already been visited. This works because of the following lemma/loop invariant: The shortest path P from A to Z when using this algorithm will always be fully traversed (where traversed is as defined as Z being REMOVED from the priority queue with the weight corresponding to what it would be if Zs weight was calculated when visiting from Z.prev (in path P) before any other longer paths from A to Z get processed. That is because always the node with the least weight is getting removed from the queue, so paths with the least weight are always getting traversed first, meaning if a node has multiple partially traversed paths constructed for it (where partially traversed means node Z is in the queue but not yet removed), the first path that is fully traversed will be the one with the lowest weight.

77
Q

The important difference between Boruvka’s algorithm and Kruskal’s or Prim’s is that

A

with Boruvka’s you don’t need to presort the edges or maintain a priority queue.

78
Q

Both prims and boruvka are based on what observation?

A

the observation that if the edge costs are unique, the cheapest edge of any cut belongs to the spanning tree

-TierI Interview Prep (31 decks)

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