Midterm 2 Flashcards
(14 cards)
1
Q
Disjoint set list implementation
A
O(n^2) union
O(1) makeset
2
Q
Union by rank
A
-rank(x) > rank(y) append y to x else x to y
Total cost: O(nlogn + m)
3
Q
Path compression
A
Improved cost: O(n+ m•alpha(n))
4
Q
Cycle property
A
- let C be any cycle in weighted graph G with distinct edge weights. Let e be the heaviest edge in the cycle
- then the min spanning tree for G does not include e
5
Q
Cut property
A
- let V’ be any proper subset of vertices in weighted graph G = (V,E) and e be the lighted edge that has exactly one endpoint in V’
- then the mst T for G contains e
6
Q
Prims algorithm
A
- greedy alg
- grow tree by finding lightest edge not yet in tree and expanding the tree, and connect it to the tree; repeat until all vertices are in the tree (cut property)
- uses priority queue
- Heap: takes O(mlogn)
- total: O(m+nlogn) or O(mlogn)
7
Q
Kruskals alg
A
- sort edges by weight, pick min weight edge and if it connects two different trees select it else discard it
- greedy
- sorting requires O(mlogm)
- disjoint set O(n+m•alpha(m))
- total O(mlogn)
8
Q
Boruvka alg
A
- assume every edge has a unique weight, initially each vertex is considered a separate component, alg merges disjoint components as follows; repeating the step until only one component exists, in each step, every component is merged with some other using the cheapest outgoing edge of the given component
- useful for parallelism and distributed computing
9
Q
Dijkstras alg
A
- find shortest path from one node to all others
- can use heaps to implement
- heap: O(n)
- remove vertex: O(logn)
- relax: O(deg(u)logn)
- total: O(mlogn)
- doesn’t work for neg
10
Q
Dijkstra invariants
A
Let d(u) = distance of u from v
- For each node u in T, D[u] = d(u)
- For each node u not in T, D[u]= length of shortest path from v to u without the use of other nodes outside of T
For all nodes u in T, D[u]>= d(u)
11
Q
Bellman Ford alg
A
- directed graphs with neg edges
- O(nm)
- every shortest path in a graph with no neg cycles has length no more than n-1, after n-1 phases if D’s continue to drop negative cycle
12
Q
All pairs shortest paths (greedy)
A
- dijkstras O(nmlogn)
- Bellman-Ford O(n^2m)
13
Q
APSP (dynamic programming)
A
- simplify into optimal sub problems where solutions overlaps
- O(n^4)
- using L^2m() then you get O(n^3logn)
14
Q
Floyd-warshall alg
A
- Shortest path does not contain same vertex twice
- If vertex is not on a shortest path from i to j with intermediate vertices then d^k(ij) = d^(k-1)(ij)
- If vertex k is on a shortest path from i to j with intermediate vertices then
d^k(ij) = d^(k-1)(ik) + d^(k-1)(kJ)
-shortest path = d^k(ij) = min{ d^(k-1)(ij), d^(k-1)(ik) + d^(k-1)(kJ)
-O(n^3)
