Flashcards in Midterm 2 Deck (14)

Loading flashcards...

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)