Midterm 2 Flashcards Preview

Csc 226 > Midterm 2 > Flashcards

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

  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)