part 2 Flashcards
What does Prim’s algorithm do?
Finds the minimum spanning tree of a graph
What does Kruskal’s algorithm do?
Finds the minimum spanning tree of a graph
What’s the difference between how Prims and Kruskal’s algorithm operate?
Both Prim’s and Kruskal’s algorithm start with the lowest cost edge (which obviously includes the two vertices that are attached by said edge). Prim’s algorithm goes on to select the lowest cost edge that is connected to the original vertices chosen in the first step, while Kruskal’s goes on to select the next lowest cost edge in the entire graph (irrespective of whether its connected to the original vertices or not)
How do we avoid resolving a subproblem for DP?
Memoization
Strongly Connected Component
every vertex is reachable from every other vertex
Transpose of a graph
A directed graph that has flipped the directions of all of its edges
Topological Sort
a linear ordering of nodes of a directed acyclic graph, such that a node follows all of its graph predecessors in the ordering.
What does the runtime for dynamic programming tell us?
When there are two variables/constants it will be much easier to use a lookup table than to try a top down approach
Whats the runtime of the Huffman coding algorithm?
O(nlogn)
Exchange Argument for Greedy Algorithms
1)Let Sg be items (or whatever) chosen by greedy
2)Let So be items chosen by another potentially optimal algorithm
3)Order (doesn’t have to be order, problem dependent) items in So the same way as greedy, let e be the first thing in So not in greedy
4)show towards contradiction that the greedy algorithm is correct, or show in a mathematical sense or otherwise explain in English that item e in So is equal or worse to item f in greedy
5)conclude we can exchange e for f
6) Repeat over and over until So is the same as greedy
What is the runtime of Kruskals algorithm?
O(ElogV)
What’s the runtime of Prim’s algorithm?
O(ElogV)
What does the shortest path by matrix multiplication do?
-You start with matrix A, which is a matrix of how to get from nodes i to nodes j in one step
-It tells you the shortest possible way to get from one node to another node in n-1 steps
-It does this by adding the row of i plus the column of j (one at a time) and takes the minimum of these sums
-Worth noting th
How long does matrix multiplication take?
O(n^3 logn)
What is the shortest path between two vertices that are on a negative length cycle?
negative infinity
What do we initialize all the values of bellman ford at?
All at infinity
What is a shortest path tree?
a shortest path tree rooted at vertex v is a spanning tree such that the distance from v to any root u is the shortest path from vertex v in the original graph
Proof By Contrapositive
Let S be a statement of the form that implies “if P then Q”. The Contrapositive of S is “if (not Q) then (not P)”
Proof by Contradiction
An indirect proof in which one assumes that the statement to be proved is false. One then uses logical reasoning to deduce a statement that contradicts a postulate, theorem, or one of the assumptions. Once a contradiction is obtained, one concludes that the statement assumed false must in fact be true.
Whats the runtime of DFS and BFS?
O( V + E)
An interesting tool that could be useful for graph algorithms
Add a new node to the graph and connect to every every node that has some specified thing we are trying to identify. Then run BFS from the new node in order to identify every node on the graph that has some specified thing
Minimum spanning tree
a tree that connects all nodes by edges such that the sum of the edges is as small as possible
Connected graph
it’s possible to get to any node from any node in the graph. But it is NOT a complete graph !
Cut Edge
The removal of this edge would disconnect a graph
