Midterm 2

Question 1

Disjoint set list implementation

Answer 1

O(n^2) union

O(1) makeset

Question 2

Union by rank

Answer 2

-rank(x) > rank(y) append y to x else x to y

Total cost: O(nlogn + m)

Question 3

Path compression

Answer 3

Improved cost: O(n+ m•alpha(n))

Question 4

Cycle property

Answer 4

• 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

Question 5

Cut property

Answer 5

• 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

Question 6

Prims algorithm

Answer 6

• 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)

Question 7

Kruskals alg

Answer 7

• 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)

Question 8

Boruvka alg

Answer 8

• 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

Question 9

Dijkstras alg

Answer 9

• 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

Question 10

Dijkstra invariants

Answer 10

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)

Question 11

Bellman Ford alg

Answer 11

• 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

Question 12

All pairs shortest paths (greedy)

Answer 12

• dijkstras O(nmlogn)

- Bellman-Ford O(n^2m)

Question 13

APSP (dynamic programming)

Answer 13

• simplify into optimal sub problems where solutions overlaps
• O(n^4)
• using L^2m() then you get O(n^3logn)

Question 14

Floyd-warshall alg

Answer 14

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)