# Midterm 2 Flashcards Preview

## Csc 226 > Midterm 2 > Flashcards

Flashcards in Midterm 2 Deck (14)
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

1. For each node u in T, D[u] = d(u)
2. 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
1. Shortest path does not contain same vertex twice
2. If vertex is not on a shortest path from i to j with intermediate vertices then d^k(ij) = d^(k-1)(ij)
3. 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)