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
What’s the recurrence relation for the optimal static BST in English?
T(i,j) = average access time of an optimal BST over the keys {k_{i}, k_{i+1},…k_{j}}
more specifically/explicitly
T(i,j) = min possible left subtree + sum of probabilities of the left subtree + min possible right subtree + sum of probabilities of the right subtree + probability of the root node !
What is a O(logn) search algorithm that can only be used on a sorted array/list?
Binary Search
in terms of data structures utiilized how does DFS differ from BFS?
DFS uses a stack while BFS uses a queue
What is a tree edge of a graph?
Edge on which a new vertices are found
What is the back edge of a graph?
All other edges besides tree edges
keep in mind with their retarded notation that n = nodes, m = edges
What is the shortest path of a negative weighted cycle?
It will result in negative infinity, because the relaxing algorithm will just keep knocking the values lower and lower till it gets to negative infinity
What’s the runtime of the optimal static BST?
O(n^3)
Proof By Contradiction
1) To prove P we can prove if (not P) then C
a) C stands for contradiction
Heap Tree
- value of a parent is always less than value of a child
- the root is always the min
- as close to a complete binary tree as possible
-all heap operations take O(logn)
If we wanted to create a heap out of an array, what would be the runtime of heapify vs successively inserting each element into the heap?
Heapify takes O(n) time while sucessively inserting each element takes O(nlogn) time
Proof By Converse
Let S be a statement of the form that implies P -> Q. Then the Converse of this statement is Q -> P
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)”
In a balanced BST how would you store the size of the subtree rooted at d?
a) Anytime we add or delete a new node, we recursively add or subtract one from each of its parents
b) When rotating a tree, we can recalculate the size of the two changed nodes by summing the size of their unmodified children and adding one
Given an array, how do you know what the left and right child of a given index is in a heap?
left child is 2i, right child is 2i + 1
